謝 維，於慧琳，陳宇航，傅咔妮

（華南理工大學，廣東廣州 510641）

1 問題提出

隨著5G 技術的蓬勃發(fā)展，越來越多的行業(yè)接入5G 網(wǎng)絡并開始多領域的推廣及應用，我國基站建設及維護工作越顯重要。據(jù)工信部發(fā)布的《2020 年通信業(yè)統(tǒng)計公報》數(shù)據(jù)顯示，2020 年我國新建5G 基站超60 萬個，全部已開通5G 基站超71.8 萬個，其中中國鐵塔新建5G 基站超33 萬個，5G 網(wǎng)絡已覆蓋全國地級以上城市及重點縣市。5G 基站和現(xiàn)有基站大量共同建設，給基站的配套電力與運維任務帶來了極大的挑戰(zhàn)。

國內(nèi)移動通信基礎設計網(wǎng)絡的建設和維護均由中國鐵塔公司負責，其主要的工作包括規(guī)劃基站網(wǎng)絡的建設以及通過基站運行監(jiān)控系統(tǒng)時刻保持基站的正常運作?；具\作依靠電網(wǎng)的電力供應，而由于惡劣天氣、道路施工等因素導致基站的電力供應中斷（稱之為“掉線”），掉線后備用蓄電池將短暫地維持基站的電力供應。鐵塔公司收到報警信息后需在蓄電池電量耗盡前將柴油發(fā)電機送往基站，否則基站將停止服務，造成經(jīng)濟損失。如圖1 為齊齊哈爾地區(qū)單月掉線基站情況，每日掉線基站數(shù)量從幾個到幾十個不等。鐵塔公司每年的基站運維費用高昂，如何通過優(yōu)化理論和算法設計進行有效的運維工作、減少掉線成本，是當前亟待解決的重要問題。

圖1 齊齊哈爾地區(qū)基站單月掉線情況

基站運維的研究問題實際上是屬于取貨與配送問題（pick-up and delivery problem,PDP），應用場景主要集中在采購補貨等場景，要求車輛必須滿足所有顧客的需求且供給與需求必須相等。如Ting 等［1］根據(jù)現(xiàn)實情況提出了可選的取送貨問題（multi-vehicle selective pick-up and delivery problem,MVSPDP），車輛在若干個取貨點中選擇前往，對顧客節(jié)點進行時間約束，并利用啟發(fā)式算法求解了多車輛的配送路徑方案和取貨量決策；Al Chami 等［2］基于帶時間窗的取送貨問題提出了詞典方法進行求解，但該方法要求取貨點僅可訪問一次，不可多次訪問；Fleischmann 等［3］考慮顧客的需求會隨時產(chǎn)生，每個需求均有軟時間窗約束，決策目標是最小化服務延遲和運輸成本；Attanasio 等［4］基于動態(tài)取送貨問題（dynamic pick and delivery problem,DPDP）問題，綜合考慮顧客需求到來和行程時間的不確定性，提出能夠動態(tài)優(yōu)化客戶服務滿意度的實時系統(tǒng)；Gendreau 等［5］針對快遞服務問題設計了插入算法，將新舊需求一并重新優(yōu)化并求解當前最優(yōu)路線；Mitrovi?-Mini?［6］針對快速處理動態(tài)問題提出了根據(jù)滾動時間水平法，即將調(diào)度時間等分地分割成若干個小塊，每個小塊內(nèi)按靜態(tài)問題的方法求解，并通過啟發(fā)式算法求解問題；葛顯龍等［7］在研究動態(tài)需求的多配送中心問題時放松了車輛與單個配送中心捆綁的約束，并引入時間軸將動態(tài)需求轉(zhuǎn)換為時間軸上的靜態(tài)需求；張婷等［8］考慮需求量、需求點、突發(fā)狀況等的動態(tài)因素，通過引入虛擬節(jié)點的方法將問題轉(zhuǎn)化為靜態(tài)后利用遺傳算法求解；王仁民等［9］在處理動態(tài)車輛路徑規(guī)劃問題（dynamic vehicle routing problem,DVRP）時，將時間看成一個個小段，并對每個時間段進行規(guī)劃處理，并分別利用變鄰域搜索算法和遺傳算法進行局部搜索和全局搜索，尋找最佳的路線安排。目前在動態(tài)取送貨問題上的研究已有較多成果，但相關的研究在計算顧客節(jié)點間的距離僅考慮靜態(tài)的交通狀況，且以節(jié)點間的歐氏距離代替實際行駛距離，但該計算方式無法刻畫現(xiàn)實生活中多變的城市交通狀況。

由于基站密集地分布在城市的各個角落，基站運維人員前往存放柴油發(fā)電機的節(jié)點取貨后送往各個報警基站點。在配送過程中，行駛時間也隨著時空的改變而發(fā)生劇烈的變化，圖2 為廣州市2021 年6 月全市的交通情況，由于早晚高峰以及突發(fā)事故等影響，一天不同時間段下的路網(wǎng)平均速度相差甚遠。在隨時間變化的交通狀況下，傳統(tǒng)路徑規(guī)劃方案的優(yōu)化效果將受影響，于是越來越多學者開始研究具有時間依賴性的車輛路徑問題（time-dependent vehicle routing problem,TDVRP）。時間依賴性指的是隨著時間推移而發(fā)生變化的交通狀況，而TDVRP則是考慮隨著時間變化的交通狀況的車輛路徑規(guī)劃問題。如Malandraki 等［10］將時間分割為多段，每一段均有不同的行駛時間，但該理論不符合“先進先出（first in first out,FIFO）”原則；Ichoua［11］通過分段刻畫行駛速度，通過路徑長度和行駛速度來計算時間，該模型符合FIFO 原則，后續(xù)很多研究在此研究基礎上開展；Eglese 等［12］基于真實的路網(wǎng)結(jié)構(gòu)和對應的車輛行駛數(shù)據(jù)，刻畫出隨時間變化的最短路徑表；Maden 等［13］在解決英國西南部電力運營的車隊運作時，考慮了早晚高峰的交通擁堵，目標是最小化總行駛時間，他們提出禁忌搜索的啟發(fā)式算法來求解問題，實證分析后發(fā)現(xiàn)考慮時變網(wǎng)絡下的規(guī)劃方案能減少7%的二氧化碳排放；馬華偉等［14］就時間依賴性的路徑規(guī)劃問題的求解提出了兩階段啟發(fā)式算法，考慮采用分階段的策略來設計模擬退火算法，并通過算例驗證了該算法性能較好；Kok等［15］首先構(gòu)建隨時間變化的最短路徑，之后利用啟發(fā)式算法求解出配送方案，并證實考慮時變網(wǎng)絡對行程時間的減少是顯著的；Jabali 等［16］在研究車輛的二氧化碳排放時，由于汽車的行駛速度將影響二氧化碳的排放，文中根據(jù)這一特性將車速的限制作為優(yōu)化的一部分，并構(gòu)建碳排放與車輛行駛速度的函數(shù)，進而通過實證分析證明該方法對于控制成本是有效的；吳瑤等［17］針對易腐品集配問題的生產(chǎn)與配送環(huán)節(jié)設計了一種混合遺傳算法進行問題求解，該模型的優(yōu)化目標是總配送成本最??；劉長石等［18］考慮時變路網(wǎng)的配送問題時，放松了出發(fā)時間、車輛必須返回駐點等約束，根據(jù)油耗、碳排放等建立起與時間關聯(lián)的目標函數(shù)，并設計了蟻群算法求解問題；范厚明等［19］考采用三角函數(shù)近似表示行駛速度的方法來刻畫動態(tài)的交通狀況，并使用動態(tài)調(diào)整和周期調(diào)整兩種策略來處理動態(tài)需求，最后設計了遺傳算法來求解問題。

圖2 廣州市6 月城市路網(wǎng)交通狀況

以上的文獻均是利用顧客節(jié)點刻畫出節(jié)點網(wǎng)絡，每條節(jié)點弧線代表一條道路，簡單地刻畫在該弧線上的交通狀況變化，然而這種刻畫方式僅僅考慮了交通網(wǎng)絡的動態(tài)變化性，并沒有達到躲避交通擁堵、提升配送效率的目的。因為在實際的交通網(wǎng)絡中，兩顧客節(jié)點間可存在多種行駛路線，不同路線由于具有時空性，花費的時間也不盡相同，通常司機會采用不同路線來躲避交通擁堵。若能夠在路徑規(guī)劃中考慮決策多種路線以躲避交通擁堵路段，可以實現(xiàn)減少行駛時間，提高配送效率的目的。

綜上所述，交通狀況會影響車輛路徑規(guī)劃方案的質(zhì)量，然而現(xiàn)有研究大多采用顧客節(jié)點構(gòu)成的弧線來代表道路，此方法無法達到躲避交通擁堵、提高配送效率的目的。本文根據(jù)真實的城市路網(wǎng)構(gòu)建兩兩節(jié)點間的道路，對顧客節(jié)點網(wǎng)絡與交通路網(wǎng)進行分別刻畫并建立模型，節(jié)點間存在多種路線組合，模型除了決策車輛服務順序、取貨量等傳統(tǒng)路徑規(guī)劃因素外，增加使用何種路徑來構(gòu)成最佳的路線方案的決策，以此達到躲避交通擁堵、減少行駛時間的目的。另外，基站運維屬于企業(yè)實際面臨的問題，本文需要設計高效的算法以保證路徑規(guī)劃問題的求解速度。本研究可為基站運維管理提供參考，對于當前車輛路徑規(guī)劃問題以及考慮時變網(wǎng)絡的車輛路徑規(guī)劃問題也有一定的借鑒意義。

2 問題描述和模型

2.1 問題描述

現(xiàn)鐵塔基站運維公司有一支車隊負責G 地區(qū)的基站運維工作，該車隊擁有數(shù)臺同質(zhì)的車輛，分布在該地區(qū)的各個駐點?；景l(fā)出報警信息時，車輛需從駐點出發(fā)，前往存放著油機的地點取油機，每次取貨需決策取油機數(shù)量，同一個取油機點可以被多次訪問，車輛取油機后再配送至報警基站，每個報警基站的油機需求均為1。車輛按服務順序配送完所有的報警基站后，返回駐點待命。由于基站報警的隨機性，車輛需動態(tài)地規(guī)劃實時到來的新報警信息。對于正在執(zhí)行任務的車輛，當新的報警產(chǎn)生時，車輛即將服務的報警基站與新產(chǎn)生的報警基站需要合并重新優(yōu)化，同時取油機點也需要被重新優(yōu)化，決策出新的服務路線方案。

車輛行駛在城市路網(wǎng)中，交通狀況隨著時空發(fā)生變化，車輛在決策服務基站及順序時，也需要決策何時行駛何種路線。而基站的備用蓄電池電量各異，每個報警基站都有不同的最晚服務時間，若車輛到達報警基站并完成裝卸貨工作后晚于報警基站的最晚服務時間，則會因斷電產(chǎn)生懲罰成本。本文的優(yōu)化目標是最小化基站掉線的個數(shù)以及基站總掉線時間。

2.2 參數(shù)描述

為了讀者方便理解，表1 匯總了本文所涉及到的符號。

表1 符號

2.3 問題建模

2.3.1 模型預處理

如何建立函數(shù)描述不同時間段下的行程時間是時變網(wǎng)絡的研究中的難點，學者們針對該難點開展了很多研究，如Hill 等［20］、Malandraki 等［10］均不滿足FIFO 原則。直至Ichoua 提出通過速度構(gòu)造分段函數(shù)描述旅行時間，F(xiàn)IFO 才被滿足。本節(jié)將參考Gendreau 等［21］提及的方法對時變網(wǎng)絡下的行駛時間進行建模。

2.3.2 模型建立

目標函數(shù)（由掉線基站個數(shù)和基站的總掉線時間組成）模型構(gòu)建如式（1）至（27）。

其中，式（1）為目標函數(shù)，其中第一部分是掉線基站個數(shù)，第二部分是基站的總掉線時間；式（2）表示并非所有車輛都需要被使用；式（3）表示車輛從駐點出發(fā)后必須回到駐點；式（4）表示可使用車輛數(shù)量約束；式（5）表示需求點必須被服務，且僅能被一輛車服務；式（6）表示車輛服務完一個需求點后必須離開；式（7）表示車輛行駛在節(jié)點間時，僅可選擇某一條路線；式（8）和式（9）共同規(guī)定了車輛從i點前往j點的離開時間有且僅有一個；式（10）和式（11）表示車輛的實際行駛時間計算；式（12）節(jié)點的離開時間需大于前一個服務節(jié)點離開時間加上行駛時間再加上節(jié)點服務時間；式（13）表示車輛在服務節(jié)點時是否延誤；式（14）和式（15）表示若車輛在服務節(jié)點時的延誤時長；式（16）和式（17）表示車輛經(jīng)過服務節(jié)點后的載貨量變化；式（18）表示任何時候車輛的載貨量不得超過載荷；式（19）表示取貨點并非必須前往的；式（19）表示取貨量不得超過取貨點的總貨物數(shù)量；式（21）至（27）是變量約束。

3 基站網(wǎng)絡運維路徑優(yōu)化的仿真研究

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

一天內(nèi)交通網(wǎng)絡與基站的運行狀態(tài)會動態(tài)地發(fā)生變化，我們將通過切割時間，將動態(tài)問題轉(zhuǎn)換為一個個的靜態(tài)問題進行求解。每當新的報警基站出現(xiàn)時，所有車輛或在駐點待命，或在城市路網(wǎng)的某一處，均有若干個即將執(zhí)行的服務需求，這些需求與新的報警基站共同組成了一個該時刻下的需求集合，本節(jié)的算法將結(jié)合車輛所處的位置以及當時的路網(wǎng)狀況，對該時刻下的進行優(yōu)化，重新安排該t時刻下的服務路線。

3.1.1 最短路算法

Dijkstra 算法是求解最短路的經(jīng)典方法之一，其中心思想是從中心點出發(fā)，層層向外迭代，探索最短路。原始的Dijkstra 算法僅考慮在某時刻出發(fā)的最短路，并不適用于本文的時變網(wǎng)絡，因此本文基于Dijkstra 算法進行了一定的改進，求解出每個m時間段下的最短路，改進的Dijkstra算法偽代碼如表2所示。

表2 改進的最短路算法偽代碼

通過上述的Dijkstra 算法，我們可以根據(jù)車輛的行駛進程以及路網(wǎng)的實時交通狀況，找到t時刻下的最佳路線，使車輛能以最短的時間行駛至服務節(jié)點。Dijkstra 算法將穿插在算法優(yōu)化的每一個計算環(huán)節(jié)中，當出現(xiàn)新的報警基站時，車輛需決策服務節(jié)點的分配以及服務順序，此時決策的依據(jù)是Dijkstra 算法根據(jù)實時t時刻下的交通狀況計算出最佳路線的行駛時間。

3.1.2 遍歷插入算法

當新的報警基站出現(xiàn)時，需要動態(tài)地規(guī)劃新的路徑，將新的報警基站安排進服務計劃內(nèi)。我們考慮在加權目標值最小增量的情況下，基于報警基站的斷電時間窗遍歷插入。遍歷插入算法如表3所示。

表3 遍歷插入算法偽代碼

遍歷插入算法可以在較短時間內(nèi)獲得針對新出現(xiàn)的報警基站的初始解，該初始解是基于新報警基站的位置、時間窗信息進行簡單的插入，尋找使目標函數(shù)增量最小的方案。該插入算法是基于貪心原則的，其構(gòu)成的解空間有限，容易陷入局部最優(yōu)解。需要進一步優(yōu)化。

3.1.3 變鄰域搜索算法

變鄰域搜索（variable neighborhood search,VNS）屬于一種元啟發(fā)式算法，其核心的思路是設計若干個具有不同結(jié)構(gòu)的算子應用于求解過程中，具有不同結(jié)構(gòu)的算子能使解空間變大，算法在若干個算子中循環(huán)，在單個算子構(gòu)成的解空間中尋找到最優(yōu)解后，鄰域被重新構(gòu)造，算法進一步探索新的解空間，幫助算法跳出局部最優(yōu)解一步步逼近最優(yōu)解。

變鄰域搜索算法的關鍵在于算子的設計，算子構(gòu)成的鄰域越大，越有可能逼近全局最優(yōu)解。算子需要根據(jù)問題的特性進行設計，否則可能影響算法的運行速度，進而影響求解效率。如表4 所示，本節(jié)根據(jù)問題設計了以下5 個算子：

表4 變鄰域搜索算法偽代碼

（1）Two_option_swap: 交換兩條服務路線的某個需求；

（2）Transfer: 將某路線的某個需求遷移至另一條路線上；

（3）Two_exchange_one: 選取A 路線上的兩個相鄰服務節(jié)點，將其與B 路線上的某個節(jié)點交換；

（4）Reverse: 選取某條路線，將相鄰的兩個服務節(jié)點的服務順序調(diào)換；

（5）Three_exchange_one: 選取某三條路線，相互交換路線中某個需求。

3.2 數(shù)據(jù)實驗與結(jié)果分析

3.2.1 算例生成

圖3 交通路網(wǎng)示意

表5 報警基站信息

在基站運維工作中，工作人員的運維流程是先開車前往取油機地點取貨，然后將油機送至報警基站為其充電，最后開車返回駐點。在實際運維中，由于服務的隨機性，工作人員可能會在服務完最后一個節(jié)點后，將車輛駕駛至家中，由此導致工作車輛并非全部在倉庫點待命。為了更貼近現(xiàn)實，在設計算例時，車輛的位置將隨機產(chǎn)生，車輛位置可能是任意節(jié)點。

3.2.2 參數(shù)設置

現(xiàn)該地區(qū)共有三輛負責基站運維的車輛，每輛車的最大載貨量是3 臺柴油機。油機個數(shù)共有50個，分布在倉庫與部分基站站點中?；镜艟€個數(shù)的權重值，基站總掉線時間的權重值（參數(shù)設定從鐵塔公司獲得）。算法采用Java 編程，計算機設備為16 GB 內(nèi)存，處理器為AMD Ryzen 54 600U 2.10 GHz。所有程序的運行時間均不超過1 min，所有算例都能在1 s 內(nèi)完成并輸出結(jié)果。為了更好判斷本文提出的方法的有效性，本文基于CVRP 模型設計了對比實驗。對比實驗是基于距離的傳統(tǒng)VRP 模型，距離矩陣通過基站間的歐氏距離與城區(qū)的平均速度 相除得到，城區(qū)的平均速度設定依據(jù)廣州市交通運輸局提供的《交通運輸月報》。

3.2.3 算法實施效果總結(jié)

為了保證真實性與可復現(xiàn)性，本文共生成100個算例，實驗組（TDVRP-PF）與對比組（CVRP）在同一個情景下，即在相同的報警基站、相同的運維車輛、相同的取油機信息下進行。運行結(jié)果如表6 所示。

表6 算例總體效果

對100 個算例匯總分析的結(jié)果如下。在考慮時變網(wǎng)絡下，可選路段地進行車輛路徑優(yōu)化所得的效果要遠好于以往不考慮時變網(wǎng)絡的模型?？偧訖嗄繕酥堤嵘?1.47%，平均掉線基站個數(shù)減少63.38%，平均每個算例減少約3 個掉線基站，同時均掉線時間減少了72.22%，本文提出的方法對基站運維的效率和效果都有較大的提升。表7 的算例具體效果顯示本文提出的方法在各種算例中表現(xiàn)穩(wěn)定且均好于對比組。

表7 算例具體效果

3.2.4 優(yōu)化方法效果分析

為了更好探究本文提出的優(yōu)化方法是否可以達到躲避交通擁堵的目的，我們選取共有16 個報警基站的算例，將油機和車輛均設置在點57 處。使用本文優(yōu)化方法（以下簡稱“TDVRP-PF”）的實驗組掉線基站個數(shù)為4 個，掉線時間為82.53 分鐘，而傳統(tǒng)的以CVRP 為基礎的對照組掉線基站個數(shù)為8 個，掉線時間為177.73 分鐘。具體數(shù)值表現(xiàn)如表8 所示。

表8 算法效果對比

結(jié)果顯示，當考慮了時間依賴性進行車輛路徑規(guī)劃的求解時，求解生成的優(yōu)化方案與傳統(tǒng)CVRP方法相比，在服務需求分配、需求服務順序以及節(jié)點間路線選擇都會有不同程度的差異，這些差異使得兩種方法在掉線個數(shù)與掉線時間上有不同的表現(xiàn)。摘取TDVRP-PF 和CVRP 優(yōu)化方案中部分的路線規(guī)劃如表9 和表10 所示。對08、42、63 需求節(jié)點，TDVRP-PF與CVRP的需求分配、需求服務順序一致，出發(fā)時間均為08:05:21。然而，在TDVRP-PF 方法下，車輛選擇了不同的行駛路線。對于需求節(jié)點08，08號節(jié)點在08:06:56 發(fā)出報警，由于基站內(nèi)蓄電池無電量儲備，基站立即斷線，需要基站運維人員盡快趕到并安裝好柴油發(fā)電機。TDVRP-PF 的行駛路線如 圖4，為57 →62 →63 →64 →08，而CVRP 的行駛路線如圖為57 →56 →55 →07 →08。

表9 TDVRP-PF 優(yōu)化方案路線

表10 CVRP 優(yōu)化方案路線

圖4 TDVRP-PF 與CVRP 方案的車輛路徑規(guī)劃

從結(jié)果來看，TDVRP-PF 方案中，車輛在08:19:03 就已經(jīng)到達08 號節(jié)點，基站總計斷電12 分鐘。而CVRP 方案中，車輛在08:24:55 到達08 號節(jié)點，基站斷電18 分鐘，較TDVRP-PF 方案晚了6 分鐘。原因在于二者采用了不同的行駛路線，如圖4 黑色的線表示車輛服務第一個需求節(jié)點08 的行駛路線，雖然CVRP 方案下選擇的路線長度比TDVRP-PF 方案下選擇的路線長度短了2 600 米，但是62-63-64-08 路段屬于一級公路，行駛速度較快，而8 點正值早高峰時期，56-57 路段的行駛速度較正常緩慢25%，56-55 路段的行駛速度較正常緩慢55%，而62-63、63-64 路段的行駛速度僅較非高峰下降了5%～10%。以距離最短為原則的CVRP 下優(yōu)化方案忽略了交通的因素，花費了更多的時間。而考慮時間依賴性的TDVPR-PF 下，充分考慮到不同道路類型的通行速度差異以及早高峰帶來的行駛速度上的影響，選擇了時間最短的道路，最大程度減少基站斷電時間。

相同的情況也發(fā)生在42 節(jié)點上，雖然二者所選的道路均為三級公路，道路基本情況相似，但是由于53-56 路段的交通長期處于高壓狀態(tài)，在早高峰擁堵情況則更為嚴重。而服務前序節(jié)點08 時進入了擁堵路段，耽誤了時間，使得CVRP 方案下42節(jié)點基站斷，斷電時間達21 分鐘。相較之下，在TDVPR-PF 的方案中，42 節(jié)點在基站斷電前9 分鐘即完成任務。綜上所述，本文所提方法能夠根據(jù)變化的交通狀況決策最佳的行駛路線來躲避交通擁堵，以更短的時間到達目的地，并且隨著服務進程的推移和交通擁堵的加劇，該方案的優(yōu)勢將更加顯著，如表11 所示。

表11 TDVRP-PF 與CVRP 方案到達節(jié)點的時間對比

4 結(jié)論

本文針對中國鐵塔公司基站運維管理成本較高和效率低下的困境，提煉出基站運維問題屬于動態(tài)的帶軟時間窗約束的多車輛可重復取貨和配送問題。在此基礎上，針對基站運維工作中城市交通路網(wǎng)的動態(tài)性，創(chuàng)新地將時間依賴性考慮進基站運維車輛路徑規(guī)劃中，通過分段刻畫城市交通路網(wǎng)，考慮取貨點、取貨量、車輛分配與容量約束，采用速度來計算行駛時間，構(gòu)造出發(fā)時間與總行駛時間的關系，構(gòu)建速度-行程時間函數(shù)用于決策行駛路線、取貨量和服務路線，設計了改進的最短路算法與變鄰域搜索算法相結(jié)合的混合算法來求解問題，數(shù)值試驗結(jié)果表明本文所提出的方法可以實現(xiàn)基站運維的成本降低和效率提升。