基于油機與車輛共享調度的基站網絡運維研究

馮增琦，於慧琳，陳志堅，關嘉欣，謝 維

（1.華南理工大學，廣東廣州 510641；2.中國鐵塔股份有限公司，黑龍江哈爾濱 150010）

1 問題提出

隨著新型基礎設施網絡的加速規(guī)?；渴鸷?G業(yè)務的推廣，我國正在大力推進5G 通信基礎設施建設工作。5G 基站作為公共基礎設施，是5G 網絡的核心設備。目前中國鐵塔股份有限公司（以下簡稱“中國鐵塔”）負責5G 基站的建設與運維，在國內占據壟斷地位，也是全球最大的移動通信基礎設施網絡服務公司。工信部數據顯示，2020 年新建5G基站超60 萬座，全部已開通5G 基站超過71.8 萬座，其中中國鐵塔新建5G 基站超33 萬座，5G 網絡已覆蓋全國（未含港澳臺地區(qū)）地級以上城市及重點縣市［1］。5G 基站和現有基站大量共站建設，給基站的配套電力與運維任務帶來了極大的挑戰(zhàn)。深圳市國信通信技術有限公司［2］深度研究報告顯示，中國鐵塔2019 年基站共享率（站平均租戶數）僅為1.62，低于國外大多數鐵塔公司（例如，Crown Castle 為2.1、Bharti Infratel 為2.06、AMT 為1.9）。運維成本過高及共享率低是中國鐵塔毛利率水平低于國外鐵塔企業(yè)的兩大原因。因此，當前中國鐵塔面臨的問題是如何降低高居不下的運維成本以及深化資源共享，提高基站網絡的運維效率，以保障5G 網絡的快速規(guī)模部署。

為保障5G 基站網絡維持正常服務，中國鐵塔所屬各鐵塔公司（以下簡稱“鐵塔公司”）將基站的維護工作分區(qū)域外包給專業(yè)化的代維公司，其中最主要的維護工作是減少基站的掉線?；镜恼＿\轉需要依靠持續(xù)穩(wěn)定的電力作為保障，當城市電力供應中斷后，基站內部的備用蓄電池組繼續(xù)為其提供一段時間的電力，因此，需要由柴油發(fā)電機（油機）在蓄電池組電量耗盡前為其充電。斷電后，運維人員先從初始位置前往倉庫取油機，接著將油機運送至斷電基站處進行充電，如果運送不及時將導致基站斷電（掉線），掉線之后則會帶來高昂的損失。隨著5G 網絡的推廣，基站的數量及分布范圍大幅增加，提高了大面積斷電發(fā)生的概率，導致基站的掉線個數和掉線時間居高不下；同時，運維車輛行駛里程迅速增加，降低了運維車輛的利用率。針對此，在物流配送領域中會采取合作配送的方式，即不同區(qū)域的配送企業(yè)開展一定程度的合作配送，實現配送資源在企業(yè)間的共享［3］。例如，Liu 等［4］、Nadarajah 等［5］、Pérez-Bernabeu 等［6］和蔣興華等［7］的研究表明，交換部分離自身配送中心較遠而離對方配送中心較近的顧客，可以提高整體配送效率、優(yōu)化資源配置并降低配送成本，以實現資源共享和共贏發(fā)展。

考慮到目前基站的維護工作是由鐵塔公司分配至各代維公司，代維公司獨立完成自己負責區(qū)域的基站運維業(yè)務，相互之間缺少合作，為此，借鑒物流配送領域中合作配送的方式（見圖1）：在基站運維問題中，由于不同的代維公司負責區(qū)域鄰近，若其中一家代維公司的某處基站發(fā)出斷電告警，該基站離自身的配送中心較遠而離其他代維公司的配送中心較近，則從其他代維公司取出油機，通過油機和車輛資源的共享大大減少配送距離。通過這種方式降低掉線概率和掉線時間，增強配送的時效性。因此，是否能夠采取有效的合作策略，即代維公司通過共享運維資源（車輛和油機）的合作運維方式，在降低基站總掉線成本的同時提高各代維公司的收益、實現多方共贏是本研究的主要問題。

圖1 代維公司與鐵塔公司合作前后配送路徑對比

基于上述問題，考慮代維企業(yè)之間的橫向合作，合作策略一方面可以使得代維企業(yè)通過資源的共享來優(yōu)化油機配送路徑，通過減少配送距離來減少配送時間，實現油機配送時效性的提升，降低掉線概率的掉線時間；另一方面，可以緩解大面積斷電帶來的資源調配數量不足的問題，增加資源調配的靈活性。隨著代維公司基站掉線概率下降，總掉線成本降低，鐵塔公司將節(jié)約的成本按照合理的分配規(guī)則分配給各代維公司，因此，代維公司參與合作的前提條件就是每家公司參與合作能獲得比原先更多的收益。這需要一種快速有效的成本分攤方法，但是，現有的成本分攤方法計算復雜度很高，不適用于鐵塔運維問題中的隨機需求環(huán)境，因此，本研究采用一種簡潔有效的成本分攤方法，將合作企業(yè)的貢獻刻畫進成本函數中，以快速及時地應對實時到來的需求。

近幾年來針對合作運輸的研究分為兩種關鍵類型——縱向合作和橫向合作?？v向合作運輸主要是指在不同貨運層級之間開展協(xié)作，如Perea 等［8］研究了包含多個需求點、供應點及中轉點的供應鏈分銷網絡的協(xié)作運輸問題；Hernandez 等［9］研究了非卡車運輸行業(yè)中一個依賴時間的集中式協(xié)作運輸問題。而本研究中代維企業(yè)協(xié)作配送油機問題屬于橫向合作（指處于供應鏈同一層級之間的貨運企業(yè)之間開展協(xié)作）。關于橫向合作，部分研究如Verdonck 等［10］、Groothedde 等［11］提出建立資源整合中心來共享倉庫和配送中心等固定資產，部分研究如Nadarajah 等［5］、Ozhan 等［12］、Dahl 等［13］考慮聯(lián)合配送路徑，還有部分研究如Sherali 等［14］、Hernandez 等［15］、朱莉等［16］考慮共享車輛容量的方式，將空車作為一種共享資源匯集起來在不同公司之間進行共享和協(xié)作運輸；而賓厚等［17］提出了一種三角模糊數與模糊綜合評價相結合的協(xié)作配送風險評價方法。協(xié)作運輸中的一個關鍵問題是如何分配收益和成本。關于這個問題，許多學者進行了研究和論證，如Frisk 等［18］在協(xié)同森林運輸規(guī)劃問題中采用了帶回程運輸路線的生產模型來估計每個合作場景的運輸成本，在此基礎上研究了3 種成本分配方法：比例分配法、Shapley 值法和核仁法；Krajewska 等［19］首先分析了集中協(xié)作規(guī)劃中各公司的利潤率，之后采用 Shapley 值法來確定公平的利潤率分配；饒衛(wèi)振等［20-22］提出了在線組建協(xié)作配送聯(lián)盟中企業(yè)成本節(jié)約相對量估算方法，并設計了兩種算法（核仁解近似迭代算法和B-T Shapley 算法）來解決協(xié)作配送中的成本分攤問題。

以上已有研究對本研究具有一定的啟發(fā)價值，但與其不同的是，本研究是在隨機需求環(huán)境下考慮代維公司通過共享資源（油機和車輛）的橫向合作配送問題。首先，當前絕大多數研究聚焦傳統(tǒng)物流配送問題，而本研究考慮的運維問題在求解配送成本時要求解帶有取貨和送貨的車輛路徑優(yōu)化問題；其次，目前大多數關于合作配送的研究是假設具有足夠的時間進行成本分攤計算，如Guajardo 等［23］的研究，很少考慮成本分攤方法的計算速度，不適用于大量需求實時到來的鐵塔運維問題，針對此，本研究設計了簡潔有效的成本分攤方法來刻畫運維資源共享中各合作成員所作出的貢獻；最后，以上研究的問題大多數是單目標問題，而本研究考慮的基站運維問題的目標除了要降低掉線成本，還要考慮降低基站的掉線時長和掉線次數的目標，因此，本研究中的問題是一個多目標合作問題。此外，目前國內關于基站運維優(yōu)化問題的研究比較少，本研究可為基站運維優(yōu)化的新方向提供參考。

2 問題描述和模型

2.1 問題描述

鐵塔公司A 將某市的基站運維業(yè)務外包給兩家代維公司B 和C 負責，并支付一定的外包費用；兩家代維公司擁有一定數量的運維配送中心，包括一定數量的倉庫、車輛和油機，并根據鐵塔公司A 運維系統(tǒng)生成的配送路徑完成實際配送，負責一定區(qū)域的基站的運維工作。鐵塔公司A 引導兩家代維公司通過共享油機和車輛資源的方式進行協(xié)作運維，并將合作后降低的運維成本（即合作的收益）按照一定的分配規(guī)則（根據各代維公司在共享資源中所作出的貢獻）再分配給這兩家代維公司，以激勵代維公司的合作動機。

2.2 成本函數

由上述問題描述，我們需要考察合作策略是否能夠實現鐵塔公司A 與兩家代維公司的共贏。目前大多數關于合作配送的研究是假設具有足夠的時間進行成本分攤計算，很少考慮成本分攤方法的計算速度，不適用于大量需求實時到來的鐵塔運維問題，針對此，本研究設計了簡潔有效的成本分攤方法，即采用資源的使用比例來刻畫運維資源共享中各合作成員所作出的貢獻。

模型建立如下：若鐵塔公司A 采取非合作策略時，代維公司B 和代維公司C 分別獨立完成各自負責區(qū)域的代維工作，兩家代維公司的成本函數，即油機配送成本F由車輛行駛成本P和油機使用成本Q組成：

對于鐵塔公司A，每年的基站運維成本包括因基站掉線所產生的基站掉線成本以及分別支付給兩家代維公司的代維服務費和，則其成本函數為：

若鐵塔公司A 采取合作策略時，代維公司B 和C 將擁有的車輛和油機彼此共享進行協(xié)作配送。令合作策略下油機配送成本分別為和，代維公司B和C 的成本函數表示如下：

而鐵塔公司A 的成本函數為：

式（7）（8）表示鐵塔公司A 給兩家代維公司的激勵為，將通過采取合作策略所節(jié)約的掉線成本以一定的比例再分配，其中和分別為在合作策略中代維公司B 和代維公司C 的資源使用比例，即B公司的車輛服務C 的基站數目和C 公司的車輛服務B的基站數目之比，刻畫了合作企業(yè)在合作中的貢獻。

2.3 問題建模

2.3.1 基本假設掉線成本和車輛及油機使用成本的計算需要解決一類動態(tài)取貨和送貨問題［24］。在每一次規(guī)劃中，新的送貨需求產生，所有車輛有未執(zhí)行的取貨任務、送貨任務，取貨量為決策變量，當需求實時到來，對車輛新到來的需求、尚未執(zhí)行的需求進行整合，并重新進行優(yōu)化；如果沒有新的送貨需求產生，運維車輛則返回到初始出發(fā)位置。每個需求點基站都有最晚服務時間（掉線時間），若油機送達時間超過該需求點的最晚服務時間時，在目標函數中給予一定的懲罰。

2.3.2 參數和變量定義

目標函數（最小化由于延遲配送所產生的基站掉線成本和運維車輛及油機使用成本之和）模型構建如下：

約束條件：

其中：式（10）表示每輛車可出發(fā)也可不出發(fā)，出發(fā)的車輛送完油機后要回到車庫；式（11）為路線平衡約束；式（12）表示避免每個需求點有多輛車為其服務；式（13）表示取貨點不一定用于服務，即某個取貨點可到達也可不到達；式（14）表示相鄰的兩個服務點的到達時間約束；式（15）（16）為油機數量平衡的約束；式（17）（18）表示車輛送貨前后承載油機數量的變化；式（19）表示拿取的油機數量不應超過該倉庫的油機總量；式（20）表示車輛在初始位置時車上的油機數量及容量限制；式（21）記錄車輛到達需求點時是否遲到；式（22）（23）表示計算晚到需求點的時間；式（24）（25）為變量的約束條件。

3 基站網絡運維車輛調度的仿真研究

3.1 動態(tài)算法設計

本研究與中國鐵塔公司開展產學研合作，所有實驗數據均來自鐵塔公司A 提供的真實數據，順應了產學研合作為企業(yè)解決技術問題、推動地方經濟產業(yè)發(fā)展效益的充分發(fā)揮的要求［25］。采用變鄰域搜索算法求解上述模型，利用小規(guī)模的算例進行對比實驗，以驗證算法的有效性和模型的正確性，結果如表1 所示。

表1 基站網絡運維車輛調度算例實驗結果

根據小規(guī)模的真實數據實驗，可以發(fā)現，隨著油機位置個數以及報警基站個數增加，算法復雜度增加，數字優(yōu)化技術（CPLEX）求解時間大幅增加，無法投入實際應用，但采用變鄰域搜索算法（VNS）可求解，算法流程如圖2 所示。

圖2 基站網絡運維車輛調度的變鄰域算法流程

此外，由于本研究問題為多目標優(yōu)化，算法搜索范圍大，容易跳出局部最優(yōu)解，因此，設計遷移算子（將一輛車的需求分配給另一輛車去服務）和交換算子（交換兩輛車所服務的需求）兩種算子得到解的鄰域，采用改進的變鄰域搜索算法（以下簡稱“改進算法”）擴大解的搜索空間，如圖3 所示。

圖3 改進的變鄰域搜索算法算子示意

實驗表明，隨著數據規(guī)模的增長，改進算法的求解時間仍然在秒級以內，能夠實現對實時到來的需求進行及時有效地處理，且與最優(yōu)解的差距較小。目前，該算法已經在中國鐵塔公司上線運行，應用于代維企業(yè)日常的基站運維中。

3.2 數據實驗與結果分析

本研究的實驗部分根據鐵塔公司A 基站報警歷史數據構造出30 個算例，參數設置如下：代維公司B 和C 各有50 個油機；公司B 有3 輛車，公司C 有4 輛車；單位掉線成本為5 000 元/h；單位車輛交通成本為500 元/min；單位油機使用成本與基站掉線時間有關，為11 500 元/h。采用改進算法計算出兩家代維公司在合作前后的基站掉線時間和車輛交通時間，再計算基站在合作前后的掉線成本，鐵塔公司A 的成本為基站總掉線成本與支付給兩家代維公司的代理費用之和，代維公司B 和C 的成本為各自的車輛使用成本和油機使用成本之和，加上各自為另一家代維公司共享出資源完成合作代維公司油機調配任務所產生的車輛行駛和油機使用成本。鐵塔公司A 根據兩家代維公司共享合作后貢獻資源的比例來對代維公司進行補貼激勵，共享合作后獲得補貼的代維公司的成本如表2 所示。

表2 算例代維公司與鐵塔公司合作前后的成本

表2（續(xù)）

表2 算例數據表明，代維公司B 在合作后每日總成本與合作前對比均有明顯降低，總成本平均降低83.78%；而代維公司C 在合作后有一些運維配送中心的掉線成本有所增加，但合作后平均降低成本較多，總成本平均降低了195.91%。其中，代維公司C 有些地方掉線成本有所增加是由于C 公司的車輛比較多，在采取合作共享策略下，較多的C 公司車輛被調去服務B 公司的基站，這使得C 公司的掉線成本反而有所增加，而鐵塔公司A 得到的降低掉線成本對C 的補償不夠，造成了C 公司在某些情況下成本增加的現象；代維公司C 的總成本降低是由于，總體而言，雖然合作策略使得C 公司投入運維資源的數量占比大，但也因為C 公司在合作中的貢獻較大，鐵塔公司A 對C 公司的補償較高，該補貼超過了C 公司額外投入的成本，提升了代維收益，使得C 公司有動機參與到合作共享策略中來。根據算例可得，合作策略實現了兩家代維公司平均收益的增加。鐵塔公司A 在合作前后的掉線時間和成本如表3 所示，可知代維企業(yè)間的合作共享策略使鐵塔公司A 總的基站掉線成本平均降低24.30%，表明鐵塔公司A 也在合作共享策略中受益。

表3 算例鐵塔公司與代維公司合作前后的掉線時間和成本

表3（續(xù)）

通過上述考察期為30 天的實例，我們得到代維公司之間的合作共享策略能夠有效地降低基站的掉線率，從而降低鐵塔公司的基站掉線總成本，同時可以為代維公司增加收益。綜上，本研究設計的運維資源共享的合作策略及其簡潔有效的成本分攤方法，不但求解時間保持在秒級以內，而且能夠實現多方共贏的局面，已經在鐵塔公司上線運行，并實現了在不增加資源的條件下提高鐵塔公司運維服務效率的目標。

4 結論

隨著5G 通信基礎設施建設工作的加速推進，如何降低基站高居不下的運維成本、深化運維資源共享是企業(yè)當前亟待解決的重要問題。本文研究隨機需求環(huán)境下代維公司通過共享資源（油機和車輛）的多目標橫向合作配送問題，提出了基于資源共享的合作運維策略，并設計簡潔有效的成本分攤方法來刻畫運維資源共享中各合作成員所作出的貢獻，實現對實時到來的需求進行及時處理。我們采用改進變鄰域搜索算法來求解鐵塔運維場景中帶有取貨和送貨的車輛路徑規(guī)劃問題，根據鐵塔公司的歷史數據構造出大量算例進行實驗，實驗結果表明了所提出的合作策略和算法能夠降低基站掉線總成本并提高代維公司的收益，在不增加資源的條件下提高鐵塔公司運維服務效率，實現多方共贏。

本研究所提出的改進算法已經在鐵塔公司上線運行，并應用于企業(yè)日常的基站維護，在基站運維優(yōu)化方面具有一定實踐意義。本研究在考慮合作策略的時候，為了適用于鐵塔公司實際運維工作，將重點放在成本分攤計算的速度，因此用投入資源數量的比例來刻畫合作成員的貢獻，未來的研究可以在算法上進一步提升分本分攤計算的質量。