周 游，朱文斌

(華南理工大學(xué) 工商管理學(xué)院，廣東 廣州 510641)

隨著5G網(wǎng)絡(luò)的發(fā)展，其應(yīng)用將大大提升人們的生活水平，增強(qiáng)各行各業(yè)的發(fā)展?jié)摿ΑＴ?G網(wǎng)絡(luò)的建設(shè)中最重要的環(huán)節(jié)就是基站的覆蓋和維護(hù)，國(guó)內(nèi)移動(dòng)通信基礎(chǔ)設(shè)施網(wǎng)絡(luò)的建設(shè)與維護(hù)均由中國(guó)鐵塔公司負(fù)責(zé)。目前全國(guó)有約200萬(wàn)個(gè)基站，鐵塔公司建立了完備的基站狀態(tài)監(jiān)控系統(tǒng)。由于臺(tái)風(fēng)、暴雪或電網(wǎng)故障等原因，會(huì)出現(xiàn)大面積斷電情況，此時(shí)基站會(huì)切換到備用電池供電，并向系統(tǒng)發(fā)出斷電報(bào)警。每個(gè)基站的備用電池容量有限，運(yùn)維人員須在電池電量耗盡之前將給電池充電的柴油發(fā)電機(jī)(以下簡(jiǎn)稱為“油機(jī)”)配送到位，否則基站將會(huì)斷電，對(duì)鐵塔公司造成重大損失。同時(shí)，雇傭運(yùn)維人員、購(gòu)買和儲(chǔ)備車輛與油機(jī)也會(huì)產(chǎn)生相應(yīng)的成本。因此如何利用優(yōu)化理論和算法規(guī)劃車隊(duì)規(guī)模并優(yōu)化有限資源的分配與調(diào)度，提高服務(wù)保障率，并達(dá)到最小化總成本的目標(biāo)，成為運(yùn)維優(yōu)化中亟需解決的問題。

本文研究的優(yōu)化問題本質(zhì)上屬于取送貨問題(pick-up and delivery problem,PDP)。目前國(guó)內(nèi)外關(guān)于取送貨問題的研究非常豐富[1]，但大部分文獻(xiàn)都基于總的取貨量與送貨量相等這一條件，其所解決的問題一般集中于采購(gòu)補(bǔ)貨等場(chǎng)景，隱含了所有客戶點(diǎn)均需要被訪問的約束[2]。Ting等[3-4]提出了可選擇的取送貨問題，放松了訪問約束，加入了收貨點(diǎn)的時(shí)間窗口約束，并利用啟發(fā)式算法求解了多車輛的最優(yōu)取送路徑與取送貨量的決策。潘立軍等[5]利用基于時(shí)差的插入算法和遺傳算法的框架求解了帶時(shí)間窗口的問題。還有一類相似的問題是庫(kù)存路徑問題(inventory routing problem,IRP)，其典型的應(yīng)用是銀行ATM機(jī)的現(xiàn)金取鈔、加鈔的場(chǎng)景，但是這類文獻(xiàn)一般利用庫(kù)存理論計(jì)算出確定的需求量并轉(zhuǎn)化為確定性需求的問題進(jìn)行求解。Anholt等[6]使用分支定界算法求解了荷蘭ATM的提貨和補(bǔ)貨的庫(kù)存路徑問題。Larrain等[7]利用混合整數(shù)規(guī)劃對(duì)智利ATM網(wǎng)絡(luò)配送問題進(jìn)行建模，考慮多個(gè)車輛的路徑規(guī)劃，采用可變MIP鄰域下降算法進(jìn)行求解。這些研究基本屬于靜態(tài)問題，即假設(shè)需求已經(jīng)確定且通行時(shí)間等不發(fā)生變化[8]。

本文的研究問題與傳統(tǒng)靜態(tài)問題具有如下的差別。1）充電量的決策與路徑的規(guī)劃相互依賴，在本問題中，基站備用電池的電量決定了服務(wù)需求的時(shí)間窗口，電池電量的補(bǔ)充量又取決于油機(jī)實(shí)際到達(dá)和取走的時(shí)間差，而傳統(tǒng)問題中一般是在已知各點(diǎn)的供給和需求量的條件下進(jìn)行路徑規(guī)劃。2）取貨、送貨點(diǎn)的狀態(tài)會(huì)發(fā)生多次轉(zhuǎn)換。當(dāng)一個(gè)基站安裝油機(jī)進(jìn)行充電后，該基站就會(huì)從需求點(diǎn)變?yōu)楣┙o點(diǎn)，需要決策何時(shí)取走該點(diǎn)的油機(jī)送往其他需要充電的基站，而傳統(tǒng)問題中的取貨、送貨點(diǎn)是固定的。

同時(shí)國(guó)內(nèi)外越來(lái)越多的研究也開始關(guān)注動(dòng)態(tài)問題，其特點(diǎn)是問題中的相關(guān)信息會(huì)隨著時(shí)間不斷變化更新，更加符合實(shí)際需求[9]。其主要應(yīng)用場(chǎng)景為動(dòng)態(tài)乘車請(qǐng)求問題、快遞配送服務(wù)等[10-12]。Fleischmann等[13]研究了顧客請(qǐng)求不斷產(chǎn)生且通行時(shí)間不斷變化的動(dòng)態(tài)問題，目標(biāo)是最小化請(qǐng)求滿足的延遲和交通成本。Yang等[14]考慮了具有軟時(shí)間窗的多車輛動(dòng)態(tài)問題，但所有出現(xiàn)的顧客請(qǐng)求必須被服務(wù)。孫寶鳳等[15]使用禁忌搜索求解了基于實(shí)時(shí)信息的動(dòng)態(tài)取送貨問題。Attanasio等[16]提出了一個(gè)考慮需求動(dòng)態(tài)到達(dá)及行程時(shí)間隨機(jī)的實(shí)時(shí)系統(tǒng)，目標(biāo)是最大化客戶服務(wù)總體滿意度。這些研究中雖然需求點(diǎn)是不斷動(dòng)態(tài)產(chǎn)生的，但需求量仍然是互相獨(dú)立且固定的，無(wú)法解決本文的難點(diǎn)。

1 問題描述和建模

1.1 問題描述

在鐵塔公司接到基站斷電警報(bào)后，系統(tǒng)會(huì)迅速根據(jù)基站的位置信息、道路通行時(shí)間規(guī)劃運(yùn)維部門對(duì)于各基站的取送油機(jī)方案，即每一輛車應(yīng)按照什么順序訪問哪些基站。運(yùn)維部門擁有多輛裝備油機(jī)的車輛，每輛車有容量限制，車輛均從唯一的車庫(kù)出發(fā)，依照系統(tǒng)指示進(jìn)行順序服務(wù)。每輛車給需要充電的基站送油機(jī)，到正在充電的基站取油機(jī)，每個(gè)基站需要的油機(jī)均為1臺(tái)，車輛在取送油機(jī)過(guò)程中不得超過(guò)其容量限制。另外，車輛在裝卸和啟動(dòng)油機(jī)時(shí)均需要服務(wù)時(shí)間，本文假定取送油機(jī)服務(wù)時(shí)間相同且對(duì)于各個(gè)基站是固定的。一個(gè)完整的規(guī)劃周期從斷電開始直到電網(wǎng)電力恢復(fù)為止，一般持續(xù)數(shù)個(gè)小時(shí)，因此假定所有車輛均可一直行駛。同時(shí)作出如下定義。

定義1掉線。若油機(jī)送達(dá)基站開始充電時(shí)間晚于備用電池電量耗盡時(shí)間，基站無(wú)法正常工作，稱之為掉線。

定義2掉線時(shí)長(zhǎng)。發(fā)生基站掉線時(shí)，油機(jī)開始充電時(shí)間減去電池耗盡的時(shí)間即為該基站的掉線時(shí)長(zhǎng)。

基站掉線將會(huì)對(duì)基站服務(wù)覆蓋范圍內(nèi)的用戶產(chǎn)生巨大影響。掉線基站的個(gè)數(shù)越多且掉線時(shí)長(zhǎng)越長(zhǎng)，帶給鐵塔公司的損失就越大，同時(shí)使用更多的車輛和油機(jī)也會(huì)產(chǎn)生更多的成本。因此，公司的目標(biāo)是最小化一個(gè)周期內(nèi)出現(xiàn)掉線的基站數(shù)目、基站掉線時(shí)長(zhǎng)及車輛交通時(shí)間的加權(quán)總和。

1.2 問題建模

雖然原問題是一個(gè)需求確定的問題，但由于其充電量決策與路徑規(guī)劃的相互依賴性以及取貨、送貨點(diǎn)狀態(tài)的轉(zhuǎn)換性，對(duì)于實(shí)際問題不能按照簡(jiǎn)單靜態(tài)問題進(jìn)行建模。本文通過(guò)轉(zhuǎn)化為多階段動(dòng)態(tài)決策問題進(jìn)行處理，對(duì)于每一階段的決策建立混合整數(shù)規(guī)劃模型。

1.2.1 符號(hào)含義

對(duì)于t時(shí)刻的決策，問題已知的常量如下。

K：車輛的集合；

V：基站點(diǎn)、車輛位置點(diǎn)的集合；

P：該次決策可取油機(jī)的點(diǎn)集；

D：該次決策需要送油機(jī)的點(diǎn)集；

Δti：點(diǎn)i裝卸油機(jī)的服務(wù)時(shí)間；

Tij：點(diǎn)i到點(diǎn)j的通行時(shí)間；

Ck：車輛k的最大容量；

Nk：車量k的初始油機(jī)數(shù)量；

Ei：點(diǎn)i電池電量耗盡的時(shí)間，i∈D；

M：一個(gè)足夠大的正數(shù)；

w1：基站掉線個(gè)數(shù)在目標(biāo)中的權(quán)重系數(shù)；

w2：基站掉線總時(shí)長(zhǎng)在目標(biāo)中的權(quán)重系數(shù)；

w3：車輛交通總時(shí)長(zhǎng)在目標(biāo)中的權(quán)重系數(shù)。

模型中的決策變量如下。

xkij：車輛k經(jīng)過(guò)邊(i,j)則取1，否則為0；

rki≥0：車輛k到達(dá)點(diǎn)i的時(shí)間；

nki∈Z ：車輛k離開點(diǎn)i時(shí)的油機(jī)數(shù)量，為整數(shù)變量；

fi：點(diǎn)i發(fā)生掉線則取1，否則為0，i∈D；

σki≥0：若點(diǎn)i發(fā)生掉線則表示掉線時(shí)長(zhǎng)，否則為0。

1.2.2 模型建立

模型的目標(biāo)為在該階段決策中最小化基站掉線個(gè)數(shù)、掉線時(shí)長(zhǎng)和所有車輛的交通時(shí)間的加權(quán)之和。其中，權(quán)重參數(shù)由鐵塔公司提前確定。

使用圖論模型對(duì)路徑規(guī)劃問題建模，圖上的流量需要保持均衡。

約束(1)確保所有出發(fā)的車輛最終都會(huì)抵達(dá)該階段的終止位置；約束(2)表示每個(gè)送貨點(diǎn)在該次決策有且僅有一輛車服務(wù)；約束(3)表示取貨點(diǎn)是可選的；約束(4)表示每個(gè)中間節(jié)點(diǎn)的流入車輛和流出車輛均衡。

同時(shí)，基站送貨的到達(dá)時(shí)間由于時(shí)間窗口約束，基站掉線會(huì)在目標(biāo)函數(shù)中產(chǎn)生懲罰，利用開關(guān)變量法將約束均寫為線性約束。

約束(5)表示如果車輛k經(jīng)過(guò)邊(i,j)，則到達(dá)點(diǎn)j的時(shí)間至少等于到達(dá)點(diǎn)i的時(shí)間加上在點(diǎn)i的服務(wù)時(shí)間；若不經(jīng)過(guò)該邊，則約束失效。同理，約束(6)為軟時(shí)間窗約束，表示車輛k在送貨點(diǎn)i安裝油機(jī)完畢的時(shí)間應(yīng)不晚于該基站電池耗盡時(shí)間，否則會(huì)出現(xiàn)懲罰。約束(7)和(8)為一組，表示若掉線，則掉線時(shí)長(zhǎng)等于安裝油機(jī)完畢的時(shí)間減去電池耗盡的時(shí)間。

最后關(guān)于車輛運(yùn)輸油機(jī)的容量約束為

約束(9)～(12)確保了車輛在取送油機(jī)時(shí)車上油機(jī)數(shù)量的增減，約束(13)表示車輛所攜帶的油機(jī)數(shù)量必須符合容量限制，且初始位置時(shí)的數(shù)量已知。

2 模型求解

雖然上述模型是線性的整數(shù)規(guī)劃模型，可以使用Cplex、Gurobi等商業(yè)規(guī)劃器直接求解，但其為NP難問題，實(shí)際應(yīng)用中問題規(guī)模較大且具有嚴(yán)格的時(shí)間要求。因此本文設(shè)計(jì)了一種高效的啟發(fā)式算法架構(gòu)進(jìn)行求解，在短時(shí)間內(nèi)得到滿意的解決方案。

由于每當(dāng)車輛在一個(gè)基站取、送油機(jī)后，原問題的取貨、送貨點(diǎn)集合將發(fā)生變化，因此需要重新進(jìn)行規(guī)劃。

2.1 時(shí)間窗口的計(jì)算

雖然充電量由油機(jī)送達(dá)和取走的時(shí)間差決定，但是其可以通過(guò)時(shí)間窗口約束對(duì)路徑規(guī)劃的調(diào)控來(lái)保證其充電量符合預(yù)計(jì)的規(guī)劃量。在人工決策中一般將電池耗盡的時(shí)間作為送油機(jī)的最遲時(shí)間窗口，且對(duì)于取油機(jī)點(diǎn)沒有時(shí)間約束。但是由于采用軟時(shí)間窗口的約束，會(huì)導(dǎo)致有較大風(fēng)險(xiǎn)出現(xiàn)基站掉線的損失。如果出現(xiàn)基站電量已滿但油機(jī)仍在該基站充電的情況，由于油機(jī)對(duì)于基站是稀缺的，這樣的過(guò)充現(xiàn)象會(huì)對(duì)全局目標(biāo)產(chǎn)生損失。因此考慮引入庫(kù)存理論對(duì)于基站取送油機(jī)的最遲時(shí)間窗口進(jìn)行修正。

不同于傳統(tǒng)的庫(kù)存問題，本模型不僅需要計(jì)算電量的下限，還需要計(jì)算防止過(guò)充的電量上限。對(duì)于電量的取、送油機(jī)問題，電池電量的消耗和補(bǔ)充速度即需求是恒定的，而車輛來(lái)取、送油機(jī)的提前期是不確定的。因此，設(shè)顯著性水平α，一般取0.05，安全電量的計(jì)算公式為SS=，其中，Z取1.65，即為充放電的速率，而提前期(lead time,LT)的分布用該基站和全部其他基站的通行時(shí)間近似代替。對(duì)于每個(gè)基站，令schar表示充電速度且scon表示耗電速度，均用單位時(shí)間百分比表示。提前計(jì)算出其取油機(jī)的電量上限(UB)和送油機(jī)的電量下限(LB)，并根據(jù)t時(shí)刻的電量ct分別計(jì)算其時(shí)間窗口

2.2 動(dòng)態(tài)算法框架

對(duì)于每一次規(guī)劃，保持正在執(zhí)行的當(dāng)前任務(wù)不變，同時(shí)更新取、送貨點(diǎn)集和各基站的時(shí)間窗口，然后再利用變鄰域搜索(variable neighborhood search，VNS)搜索本階段的較優(yōu)解，直到電力恢復(fù)。具體框架如圖1所示。

圖1 動(dòng)態(tài)算法框架圖Figure 1 Dynamic algorithm framework

2.2.1 初始解生成

步驟1對(duì)于該階段的取、送貨集合和各基站的時(shí)間窗口，將基站按照時(shí)間窗口排序，按前后順序插入。

步驟2對(duì)于每個(gè)待插入基站，遍歷車輛集合，計(jì)算插入隊(duì)尾的到達(dá)時(shí)間，選擇最早到達(dá)且油機(jī)數(shù)量符合要求的車輛插入。

步驟3若沒有車輛符合油機(jī)數(shù)量要求，則選擇時(shí)間窗口最早的相反狀態(tài)的基站插入。

步驟4重復(fù)步驟1～3，直到所有基站均被插入，生成初始解。

2.2.2 VNS優(yōu)化

將初始解S0按照一定規(guī)則操作得到的全部合法解稱為S0的鄰域，對(duì)應(yīng)的操作稱為算子。本文主要使用交換和遷移2種算子，如圖2所示。

圖2 交換和遷移算子示意圖Figure 2 Diagram of exchange and relocate operators

步驟1對(duì)于當(dāng)前解，利用交換算子找到所有合法的鄰域，記錄最優(yōu)局部解并將其與全局最優(yōu)解比較，若改善則轉(zhuǎn)到步驟2，若沒有改善則轉(zhuǎn)到步驟3。

步驟2將最優(yōu)的交換操作應(yīng)用于當(dāng)前解，得到新的解并更新全局最優(yōu)解，若迭代次數(shù)超過(guò)上限則轉(zhuǎn)到步驟4，否則重復(fù)步驟1。

步驟3利用遷移算子找到所有合法的鄰域，記錄最優(yōu)局部解并將其與全局最優(yōu)解比較，若改善則轉(zhuǎn)到步驟2，若沒有改善則轉(zhuǎn)到步驟4。

步驟4輸出當(dāng)前決策階段的全局最優(yōu)解。

3 數(shù)值實(shí)驗(yàn)

利用鐵塔公司真實(shí)數(shù)據(jù)進(jìn)行數(shù)值實(shí)驗(yàn)。從2018年1～8月份的數(shù)據(jù)中隨機(jī)生成不同規(guī)模的數(shù)據(jù)集，并與公司現(xiàn)有系統(tǒng)的安排結(jié)果比較。每輛車均從唯一的車庫(kù)出發(fā)，車輛容量均為3臺(tái)油機(jī)，每階段迭代上限為200。為方便對(duì)比，數(shù)據(jù)集的停電時(shí)間均設(shè)為4 h。所有算例目標(biāo)函數(shù)權(quán)重參數(shù)均與鐵塔公司協(xié)商后確定，為w1=0.7，w2=0.2，w3=0.1，其衡量的目的如下。1) 對(duì)于公司運(yùn)維成本影響最大的為基站掉線個(gè)數(shù)，無(wú)論時(shí)間長(zhǎng)短均會(huì)帶來(lái)重大損失，因此在目標(biāo)中占較大比重；2) 在掉線個(gè)數(shù)相同的情況下，公司希望掉線的總時(shí)長(zhǎng)更小，可使基站掉線產(chǎn)生的持續(xù)影響較??；3) 公司也需要考慮車輛通行成本，在目標(biāo)函數(shù)中需要一定比重的體現(xiàn)。

3.1 實(shí)驗(yàn)結(jié)果

為了比較了不同規(guī)模的問題，基站數(shù)量設(shè)定為50～300個(gè)，同時(shí)為了方便鐵塔公司確定運(yùn)維車隊(duì)的規(guī)模，車輛數(shù)設(shè)定為10～30輛。比較結(jié)果如表1所示。

由表1可知，本文算法的結(jié)果顯著優(yōu)于鐵塔公司目前系統(tǒng)得到的方案，除11號(hào)外，優(yōu)化率＞0。通過(guò)觀察還可以發(fā)現(xiàn)：1) 當(dāng)車輛數(shù)遠(yuǎn)小于基站數(shù)時(shí)，由于服務(wù)能力過(guò)低，必然導(dǎo)致很多掉線損失，2個(gè)方案的效果無(wú)明顯差異；2) 算例規(guī)模變大且車輛數(shù)量合理時(shí)，本文算法優(yōu)勢(shì)很大，優(yōu)化率＞10%，如，序號(hào)14、15；3) 車輛數(shù)并非越多越好，在中小規(guī)模算例中，反而出現(xiàn)目標(biāo)值變差的情況，公司應(yīng)根據(jù)各種規(guī)模問題出現(xiàn)的概率進(jìn)行規(guī)劃。

表1 數(shù)值實(shí)驗(yàn)結(jié)果Table 1 Numerical experiment results

3.2 算法特性分析

本文主要從最優(yōu)解的搜索能力和收斂速度來(lái)分析算法的有效性。通過(guò)對(duì)比單個(gè)階段算法求解結(jié)果與Cplex直接求解整數(shù)規(guī)劃模型最優(yōu)解來(lái)驗(yàn)證算法的最優(yōu)性。由于問題的復(fù)雜性，Cplex在5 min內(nèi)僅能求得基站數(shù)為10以內(nèi)的問題最優(yōu)解。從表2可以看出，在小規(guī)模的算例中，本文算法用時(shí)均為毫秒級(jí)，且隨問題規(guī)模的增長(zhǎng)，求解時(shí)間變化較小，而Cplex求解時(shí)間隨問題規(guī)模增長(zhǎng)而迅速增加。同時(shí)，本文算法的目標(biāo)值與最優(yōu)解差距平均＜20%，說(shuō)明算法符合實(shí)時(shí)決策要求下依然具有較好的最優(yōu)解搜索能力。本文用算法目標(biāo)值及總通行時(shí)間隨迭代次數(shù)的改變情況表示算法搜索的收斂速度。圖3展示了基站數(shù)為200、車輛數(shù)為30的單個(gè)階段算法的目標(biāo)值隨迭代次數(shù)的變化。在100次迭代內(nèi)，算法目標(biāo)值先迅速降低，隨后趨于平緩，同時(shí)，算法優(yōu)先減少掉線基站個(gè)數(shù)，隨后優(yōu)化掉線時(shí)間和通行時(shí)間，符合目標(biāo)函數(shù)各部分的權(quán)重分配。

圖3 目標(biāo)函數(shù)迭代變化圖Figure 3 Diagram of objective function change with iteration

表2 算法最優(yōu)性對(duì)比分析Table 2 Comparative analysis of algorithm optimality

4 結(jié)語(yǔ)

本文以中國(guó)鐵塔公司基站運(yùn)維問題為背景，深入分析了該問題與傳統(tǒng)取送貨問題的差異性，將靜態(tài)問題轉(zhuǎn)化為動(dòng)態(tài)多階段決策，并利用圖論模型建立整數(shù)規(guī)劃模型，利用庫(kù)存理論修正各基站取送油機(jī)電量的上下限，設(shè)計(jì)了基于VNS的動(dòng)態(tài)算法進(jìn)行求解。通過(guò)公司實(shí)際數(shù)據(jù)生成的算例驗(yàn)證了本文的算法的優(yōu)越性。該模型可以輔助公司決策運(yùn)維車隊(duì)的規(guī)模。進(jìn)一步的研究將尋找更精準(zhǔn)的充電量決策方式和車輛之間任務(wù)均衡性的優(yōu)化。