基于CTDEA算法的車輛+UAV配送路徑優(yōu)化

韓 明,王亞彬，丁連永，王添幸

(1.陸軍工程大學(xué)石家莊校區(qū)，石家莊 050003；2.32653部隊，沈陽 110163;3.國防大學(xué)聯(lián)合作戰(zhàn)學(xué)院，石家莊 050084)

維修保障主要以搶救搶修為主[1]，在未來信息化精確打擊的對決下，武器裝備維修器材需求隨機(jī)性大、位置分散，這對配送的機(jī)動能力和時效性提出了更高要求。特別是中印邊境高寒山地地區(qū)，主戰(zhàn)場位于狹長通道，山高谷深、地形復(fù)雜；交通設(shè)施條件落后；冰凍、雪崩等多發(fā)惡劣天氣易阻斷投送路線；有效保障時間有限(下午4、5點至半夜持續(xù)風(fēng)沙不能進(jìn)行維修操作)；車輛性能下降(發(fā)動機(jī)功率下降30%，載重量下降25%)，故障高發(fā)；有生力量非戰(zhàn)斗減損嚴(yán)重，單兵力竭運動易產(chǎn)生急性腎損傷、炎癥反應(yīng)和雪盲。這導(dǎo)致高原山地車輛行速度緩慢，行駛范圍受限，基本依靠人力進(jìn)行“最后一公里”的末端配送，嚴(yán)重制約我軍維修器材的配送效率。

由Dantzig于1959年提出的車輛路徑優(yōu)化問題(Vehicle Routing Problem,VRP)是典型的NP難問題。其變體問題——帶時間窗的車輛路徑規(guī)劃問題(Vehicle Routing Problem with Time Window,VRPTW)是當(dāng)前物流領(lǐng)域研究的熱點和難點。廣泛學(xué)者主要圍繞著該問題模型完善和求解算法改進(jìn)進(jìn)行了深入研究。如關(guān)于擁堵情形下的城市配送和互聯(lián)網(wǎng)租車等一系列VRPTW模型的構(gòu)建[2,3]，以及多agent蟻群算法，改進(jìn)蝙蝠算法，改進(jìn)遺傳算法等VRPTW求解算法的設(shè)計[4-6]。但針對高原山地維修器材配送問題的VRPTW模型和算法成果較少。

針對上述問題，本文在前人研究的基礎(chǔ)上[7]，提出了高原山地“車輛+無人機(jī)”這一半無人化配送模式，構(gòu)建了對應(yīng)的VPRTW模型，并根據(jù)問題特征應(yīng)用CTDEA算法對該問題進(jìn)行了求解。

1 “車輛+無人機(jī)”配送模式

車輛配送是指對一系列卸(裝)貨點，組織適當(dāng)?shù)男熊嚲€路，在一定約束條件下(如貨物需求量、發(fā)貨量、交貨時間窗，車輛容量限制、時間限制等)的情況下，使車輛有序通過它們，以達(dá)到一定的目標(biāo)(如距離最短，成本最低，時間最短等)。其特點是規(guī)模經(jīng)濟(jì)性，但其單位配送成本高，載貨量較大，行駛范圍較廣但是受地形影響大[8,9]，如圖1。

圖1 車輛配送模式下的路徑規(guī)劃示意圖

無人機(jī)是(Unmanned Aerial Vehicle，UAV)一種無需人員駕駛的空中飛行器，其利用內(nèi)部配置的無線電遙控設(shè)備和預(yù)先編制好地控制程序?qū)崿F(xiàn)自主飛行、獨立完成作戰(zhàn)或保障任務(wù)[10]。UAV具有機(jī)動靈活，隱蔽高效，安全經(jīng)濟(jì)，受天氣、地形、道路交通影響小(見圖2)[11]，但載重量有限，飛行半徑較小的特點，見表1所示。

圖2 車輛不可通行地域的UAV配送示意圖

表1 UAV特點性能

類別優(yōu)缺點可承受配送環(huán)境地形海拔/m天氣載重/kg1穩(wěn)定,不能懸停山地正常小雨52輕巧,受環(huán)境影響大平坦地域正常小雨、2級風(fēng)23穩(wěn)定、靈活,但是造價高,油耗大復(fù)雜地勢正常6級大風(fēng)臺風(fēng)、小雨104穩(wěn)定、靈活,成本低、可懸停復(fù)雜地勢4 000雨天105穩(wěn)定、靈活,成本低、防水,懸停更高垂復(fù)雜地勢4 0006級大風(fēng)臺風(fēng)、雨天15

注意：1為固定翼UAV，2為無尾翼UAV,3為無人直升機(jī),4為四旋翼UAV,5為六旋翼UAV。

UAV配送模式在軍用和民用領(lǐng)域取得了長足發(fā)展。早在阿富汗戰(zhàn)爭，美軍無人運輸機(jī)K-MAX就出色完成了從后勤基地到偏遠(yuǎn)山區(qū)前線陣地的配送任務(wù)，標(biāo)志著UAV以“空中挑夫”身份正式出現(xiàn)在戰(zhàn)時配送領(lǐng)域。當(dāng)前，軍用UAV配送了切合未來戰(zhàn)爭的信息化、網(wǎng)絡(luò)化、無人化的需求。在民用領(lǐng)域，UAV配送技術(shù)迅速風(fēng)靡國內(nèi)外。在國外，Reykjavik實現(xiàn)UAV送貨上門；ZIPLINE公司實現(xiàn)UAV以高達(dá)100 km/h的時速向診所運送血液。在國內(nèi)，順豐建立了大型物流UAV基地，并提出“大型有人運輸機(jī)+支線大型UAV+末端小型UAV”的三段式空運網(wǎng)實現(xiàn)36 h通達(dá)全國的設(shè)想；京東研發(fā)出了能夠全自動化配送貨的六旋翼UAV；餓了么，美團(tuán)外賣獲準(zhǔn)開辟UAV即時配送航線，實現(xiàn)了UAV外賣配送的合法化,大幅提高了配送效率。

高原山地維修器材需求呈群落分布，群內(nèi)需求量小、時效性強、位置分散且多位于車輛不可通行地域。傳統(tǒng)“車輛+人力”配送模式效率不高的問題亟待解決。當(dāng)前UAV性能已可以勝任惡劣天氣下的高原山地配送任務(wù)(見表1)。車輛與UAV配送特點如表2，本研究通過UAV與車輛的優(yōu)勢互補，用UAV取代傳統(tǒng)人力搬運作為直達(dá)作戰(zhàn)單元的配送方式，提出了一種“車輛+UAV”的高原山地維修器材配送模式。

表2 車輛與UAV配送特點

該模式的具體配送過程如下：配送中心對所獲取的作戰(zhàn)單元的需求利用諸如細(xì)菌搜索算法(Bacterial Foraging Algorithm,BFA)、K-means等聚類算法，對需求進(jìn)行預(yù)處理，然后通過任務(wù)匹配確定執(zhí)行任務(wù)的倉庫。按照車輛通行良好地域由車輛進(jìn)行配送，車輛通行受限地域由車載UAV進(jìn)行配送的原則，進(jìn)行配送路徑規(guī)劃以實現(xiàn)總配送時間最短，如圖3所示。

圖3 車輛+UAV配送路徑宏觀示意圖

“車輛+UAV”配送模式在配送過程中3種運動形式：① 同時啟用車輛和無人機(jī)均處于動態(tài)配送；② 受通行范圍限制，車輛在某一集散點等待，啟用無人機(jī)赴附近作戰(zhàn)單元進(jìn)行配送，配送完后返回車輛所在位置；③ 車輛通行條件良好，啟用車輛配送，無人機(jī)暫不啟用。如圖4所示，此處考慮高原山地配送實務(wù)的特點，對如圖4(b)所示的情形進(jìn)行研究。

2 車輛+UAV配送模式的模型設(shè)計

本文研究圖4(b)下的“車輛+UAV”路徑問題，可以看成嵌套的兩級帶時間窗的車輛路徑規(guī)劃(Vehicle Routing Problem with Time Windows,VRPTW)問題，車輛路徑規(guī)劃為Ι級VRPTW問題，UAV配送為ΙΙ級(即Ι級問題的子級問題)VRPTW問題。建模思路為，首先按車輛通行情況和距離對提出維修器材需求的作戰(zhàn)單元進(jìn)行聚類分析，處理為作戰(zhàn)單元需求群，將每個需求群組視為1個Ι級需求點對車輛路徑進(jìn)行優(yōu)化。車輛通行受限的需求點，由車輛進(jìn)行配送，車輛通行范圍受限需求群組啟用車輛+UAV配送模式，由車輛行駛至集散點，由無人機(jī)進(jìn)行配送，其實質(zhì)為一個局部VRPTW問題。故，車輛與UAV均遵循以下模型。

圖4 車輛+UAV配送路徑局部示意圖

2.1 符號說明

f(x):軍事效能；E：軍事效益

C1：電耗成本；C2：時間成本；C3：懲罰成本

w1w1,w2,w31：C1,C2,C3所對應(yīng)的權(quán)重

θ1：運輸工具空載時單位距離耗油/電成本

θ2：運輸工具滿載時單位距離耗油/電成本

qg：需求點的需求量

cfk：每動用每一運輸工具的固定成本

Rk：所啟用的每一運輸工具數(shù)量

[ETi,LTi]：作戰(zhàn)單元的時間窗

M1(ti)：早到的懲罰成本函數(shù)

M2(ti)：[ETi,LTi]內(nèi)到的懲罰成本函數(shù)

M3(ti)：晚到的懲罰成本函數(shù)

Vj：需求器材的容積；bj：需求器材的尺寸

2.2 模型構(gòu)建

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

twait,i,k=max(ETi,k-ti,k,0)

(10)

(11)

tj,k=ti,k+twait,i,k+Tunload,i,k+tij,i,k

(12)

(13)

(14)

(15)

根據(jù)高原山地軍用維修器材配送任務(wù)的特點，本研究將軍事效能最大化作為目標(biāo)函數(shù)，見式(1)。由于指定配送任務(wù)對應(yīng)的軍事效益E為定值，所以上述目標(biāo)即可轉(zhuǎn)化為油/電耗成本、時間成本和懲罰成本最小化，見式(2)。結(jié)合高原山地配送中道路彎多坡陡，車輛故障高發(fā)，車速受路況影響較大，且油耗成本大的實際，引入了距離修正因子hij和速度修正因子gij和基于車輛實載率核算的單位油耗成本(對于不受上述因素影響的UAV，其對應(yīng)參數(shù)hij,gij可取1)。上述模型中的hij,gij可由信息平臺根據(jù)所獲取各節(jié)點間路段i→j的實時道路信息進(jìn)行賦值，θ1,θ2根據(jù)信息平臺記錄的車輛油耗歷史數(shù)據(jù)得到。由于實際情況下作戰(zhàn)單元的時間窗為無時間窗、軟時間窗、硬時間窗、混合時間窗共存，故本文通過設(shè)置不同時段的懲罰函數(shù)來描繪不同時間窗下的懲罰成本。其中，無時間窗情況下，M(ti)均取0；硬時間窗下，令M1(ti),M3(ti)→∞，M2(ti)取1；軟時間窗和混時間窗下根據(jù)作戰(zhàn)單元需求規(guī)律設(shè)置懲罰函數(shù)表達(dá)式。式(3)表示多目標(biāo)處理為單一目標(biāo)函數(shù)時各子目標(biāo)的權(quán)重約束。由于維修器材裝載不同傳統(tǒng)物資裝載，所以其裝載除了車輛載荷和容量約束外，還要考慮裝貨尺寸的約束，見式(4)～式(6)。式(7)～式(9)分別表示每個作戰(zhàn)單元最多有且只有一輛運輸工具為其服務(wù);運輸工具訪問每個節(jié)點后必須從該節(jié)點駛離，然后進(jìn)行下一個作戰(zhàn)單元的配送或返回配送中轉(zhuǎn)點(起始點)；運輸工具必須從起始點出發(fā)最終返回起始點，并且運輸工具數(shù)量不能超過可用運輸工具總數(shù)K。式(10)～式(12)分別表示在作戰(zhàn)單元處i的等待時間，卸貨時間和到達(dá)作戰(zhàn)單元處j的時間，其中卸貨時間由器材卸貨量和器材的卸貨速度決定。式(13)～式(15)均為0-1決策變量。

3 求解算法

無人機(jī)配送路徑規(guī)劃問題的實質(zhì)仍為VRPTW問題，二者均屬于NP-hard問題，一般采用啟發(fā)式算法來進(jìn)行求解。以GA算法為代表的進(jìn)化算法因具有較高的魯棒性、高效率和廣泛適用性的全局優(yōu)化特點，被廣泛用于上述大規(guī)模復(fù)雜組合優(yōu)化的求解。但是傳統(tǒng)演化算法普遍存在由于種群多樣性下降而導(dǎo)致過早收斂，陷入局部最優(yōu)的局限。針對這一問題，譚陽等[12]提出了基于染色體異位的動態(tài)進(jìn)化算法(Chromosomal Translocation-based Dynamic Evolutionary Algorithm,CTDEA)，該算法在維護(hù)種群多樣性、求解速度、解的精度、和穩(wěn)定性上較遺傳算法(GA)均由明顯改進(jìn)。故此處選取該算法對上述VRPTW+UAVRPTW問題進(jìn)行求解。

3.1 算法步驟

步驟1 初始化種群P0;

步驟2 互斥操作：對Pt進(jìn)行互斥操作(去除差個體i,j間差異度d(ai,aj)相同的個體)并根據(jù)目標(biāo)適應(yīng)度Fit(f(ai))按降序排列。

(16)

其中，Div(ai)為個體在種群中的差異度。

步驟3 判斷是否滿足終止條件，滿足即跳出循環(huán)，否則繼續(xù)執(zhí)行步驟4。

步驟4 精英策略：篩選Fit(f(ai))排序為前m的個體構(gòu)成精英群，并計算Div(ai)

步驟5 交叉操作：其余n-m個體，根據(jù)式(17)在步驟4的精英群中選擇一個精英個體，按式(18)進(jìn)行交叉操作

(17)

(18)

其中，ai,l表示個體ai在其種群中的第l個編碼位。

步驟6 多樣性度量。計算當(dāng)前基因矩陣所有列的多樣性度量Div(j)，將結(jié)果按降序排列存入Div_column，按式(19)求基因矩陣多樣性度量Div(At)；

(19)

其中，Div(At)=0,1,2,…,n×L,且其值越逼近0，種群多樣性越高。

步驟7 易位操作：根據(jù)式(20)對比多樣性Div(At)，根據(jù)K值，按式(21)對Div_column中的前K列進(jìn)行反置易位操作，之后執(zhí)行步驟2。

(20)

(21)

3.2 算法流程

CTDEA算法流程如圖5所示。

圖5 CTDEA算法流程框圖

4 算例分析

4.1 背景案例

假設(shè)配送中心收到高原山地作戰(zhàn)單元維修器材需求信息見表3。

表3 作戰(zhàn)單元需求信息

經(jīng)過任務(wù)匹配，倉庫A負(fù)責(zé)此次配送任務(wù)?？紤]由于該次配送任務(wù)所屬地域地形復(fù)雜，車輛通行范圍受限，故調(diào)用車輛+六旋翼UVA執(zhí)行此次任務(wù),該UAV性能見表1，飛行半徑20 km，平均航行速度為15 m/s。配送流程為車輛裝載UVA直達(dá)中轉(zhuǎn)集散點0，然后啟用UAV進(jìn)行“最后一公里”末端配送。車輛至0的路程為20 km,平均車速為60 km/h，最載重1.6 t，該車隊于9點從A出發(fā)。要求對UAV配送路徑進(jìn)行規(guī)劃，使得在動用UAV架次最少的基礎(chǔ)上實現(xiàn)配送時間最短。

4.2 CTDEA算法和GA算法運行結(jié)果

由于車輛均是從A到0，距離均為20 km，用時20 min,抵達(dá)中轉(zhuǎn)點0的時刻為9∶20≤ETi,故該背景案例中的VRPTW+UAVRPTW問題，僅需要對UAVRPTW進(jìn)行處理即可。利用CTDEA算法和GA算法同時求解，Matlab的運行結(jié)果如表4、表5所示。

圖6 CTDEA算法和GA算法下的UAV配送路徑圖

表4 CTDEA算法求解結(jié)果

編號配送路徑任務(wù)里程/km配送用時UAV10→12→6→9→7→8→14→022.616 15025 min26 sUAV20→5→10→11→2→1→024.914 53827 min56 sUAV30→13→3→4→026.522 75129 min37 s合計74.053 43929 min37 s

表5 GA算法求解結(jié)果

如表4、表5所示，CTDEA算法求解結(jié)果為UAV動用架次為3，總?cè)蝿?wù)里程為74.053 4 km，由于UAV并行執(zhí)行任務(wù)，總?cè)蝿?wù)耗時29 min37 s，GA算法求解結(jié)果為UAV動用架次為4，總?cè)蝿?wù)里程為83.415 4 km，總?cè)蝿?wù)耗時29 min40 s,如圖6所示。

通過對高原山地維修器材配送實際的背景案例的仿真分析，發(fā)現(xiàn)CTDEA算法在求解質(zhì)量和收斂代數(shù)方面均好于GA算法(見圖7)，有效解決了傳統(tǒng)進(jìn)化算法因種群多樣性下降導(dǎo)致早熟問題。其中，GA算法在進(jìn)入較少代數(shù)后由于受目標(biāo)函數(shù)極小值吸引速喪失種群多樣性，陷入局部最優(yōu)，全局搜索能力較差。相比于GA算法，CTDEA算法能夠通過染色體異位保障了種群多樣性，從而使得算法可以跳出陷入局部最優(yōu)的困境，避免算法過早進(jìn)入早熟，提高了算法的全局搜索能力和求解質(zhì)量；同時從收斂代數(shù)上來看，CTDEA算法具有較好局部尋優(yōu)能力和收斂速度。

圖7 CTDEA算法與GA算法下迭代次數(shù)與最優(yōu)值關(guān)系

4.3 “車輛+UAV”和“車輛+人力搬運”

根據(jù)高原山地單兵負(fù)重研究，海拔3 700 m人力搬運速度為4 km/h,4.5 km/h,5 km/h分別對應(yīng)基準(zhǔn)適宜負(fù)重為20.5 kg,18.0 kg,15.0 kg。鑒于配送任務(wù)的時效性，選取5 km/h,15.0 kg這一數(shù)組用于對比，Tunload取1 min/單元。通過求解，得該模式需3名單兵，總里程74.053 4 km，合計用時5 h21 min,配送效率為“車輛+UAV”的1/10.84，且難以滿足時間窗需求。

5 結(jié)論

本文提出了一種“車輛+UAV”的半自主配送模式。通過仿真實驗驗證了“車輛+UAV”配送方式較傳統(tǒng)配送方式在配送效率和時效性方面的優(yōu)越性以及CTDEA算法的有效性。