時(shí)變路網(wǎng)下動(dòng)態(tài)可選路線可重復(fù)取送貨基站運(yùn)維路徑優(yōu)化

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

（華南理工大學(xué)，廣東廣州 510641）

1 問題提出

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

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

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

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

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

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

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

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

2 問題描述和模型

2.1 問題描述

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

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

2.2 參數(shù)描述

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

表1 符號(hào)

2.3 問題建模

2.3.1 模型預(yù)處理

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

2.3.2 模型建立

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

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

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

3.1 動(dòng)態(tài)算法設(shè)計(jì)

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

3.1.1 最短路算法

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

表2 改進(jìn)的最短路算法偽代碼

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

3.1.2 遍歷插入算法

當(dāng)新的報(bào)警基站出現(xiàn)時(shí)，需要?jiǎng)討B(tài)地規(guī)劃新的路徑，將新的報(bào)警基站安排進(jìn)服務(wù)計(jì)劃內(nèi)。我們考慮在加權(quán)目標(biāo)值最小增量的情況下，基于報(bào)警基站的斷電時(shí)間窗遍歷插入。遍歷插入算法如表3所示。

表3 遍歷插入算法偽代碼

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

3.1.3 變鄰域搜索算法

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

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

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

（1）Two_option_swap: 交換兩條服務(wù)路線的某個(gè)需求；

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

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

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

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

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

3.2.1 算例生成

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

表5 報(bào)警基站信息

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

3.2.2 參數(shù)設(shè)置

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

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

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

表6 算例總體效果

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

表7 算例具體效果

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

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

表8 算法效果對(duì)比

結(jié)果顯示，當(dāng)考慮了時(shí)間依賴性進(jìn)行車輛路徑規(guī)劃的求解時(shí)，求解生成的優(yōu)化方案與傳統(tǒng)CVRP方法相比，在服務(wù)需求分配、需求服務(wù)順序以及節(jié)點(diǎn)間路線選擇都會(huì)有不同程度的差異，這些差異使得兩種方法在掉線個(gè)數(shù)與掉線時(shí)間上有不同的表現(xiàn)。摘取TDVRP-PF 和CVRP 優(yōu)化方案中部分的路線規(guī)劃如表9 和表10 所示。對(duì)08、42、63 需求節(jié)點(diǎn)，TDVRP-PF與CVRP的需求分配、需求服務(wù)順序一致，出發(fā)時(shí)間均為08:05:21。然而，在TDVRP-PF 方法下，車輛選擇了不同的行駛路線。對(duì)于需求節(jié)點(diǎn)08，08號(hào)節(jié)點(diǎn)在08:06:56 發(fā)出報(bào)警，由于基站內(nèi)蓄電池?zé)o電量?jī)?chǔ)備，基站立即斷線，需要基站運(yùn)維人員盡快趕到并安裝好柴油發(fā)電機(jī)。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)到達(dá)08 號(hào)節(jié)點(diǎn)，基站總計(jì)斷電12 分鐘。而CVRP 方案中，車輛在08:24:55 到達(dá)08 號(hào)節(jié)點(diǎn)，基站斷電18 分鐘，較TDVRP-PF 方案晚了6 分鐘。原因在于二者采用了不同的行駛路線，如圖4 黑色的線表示車輛服務(wù)第一個(gè)需求節(jié)點(diǎn)08 的行駛路線，雖然CVRP 方案下選擇的路線長(zhǎng)度比TDVRP-PF 方案下選擇的路線長(zhǎng)度短了2 600 米，但是62-63-64-08 路段屬于一級(jí)公路，行駛速度較快，而8 點(diǎn)正值早高峰時(shí)期，56-57 路段的行駛速度較正常緩慢25%，56-55 路段的行駛速度較正常緩慢55%，而62-63、63-64 路段的行駛速度僅較非高峰下降了5%～10%。以距離最短為原則的CVRP 下優(yōu)化方案忽略了交通的因素，花費(fèi)了更多的時(shí)間。而考慮時(shí)間依賴性的TDVPR-PF 下，充分考慮到不同道路類型的通行速度差異以及早高峰帶來的行駛速度上的影響，選擇了時(shí)間最短的道路，最大程度減少基站斷電時(shí)間。

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

表11 TDVRP-PF 與CVRP 方案到達(dá)節(jié)點(diǎn)的時(shí)間對(duì)比

4 結(jié)論

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