劉正元, 王清華

(陸軍勤務(wù)學(xué)院軍事物流系, 重慶 401331)

0 引 言

無(wú)人機(jī)在農(nóng)業(yè)、監(jiān)測(cè)等民用領(lǐng)域已廣泛運(yùn)用,而如今無(wú)人機(jī)在配送領(lǐng)域的研究也逐漸成熟。2013年,亞馬遜首次宣布實(shí)施無(wú)人機(jī)配送項(xiàng)目,并宣布于2017年正式進(jìn)入實(shí)際應(yīng)用階段。2014年,谷歌實(shí)施代號(hào)為“Wing”的無(wú)人機(jī)配送項(xiàng)目,實(shí)現(xiàn)了配送無(wú)人機(jī)直達(dá)目的地并自動(dòng)完成卸貨的功能。德國(guó)DHL(Dalsey, Hillblom, Lynn)于2013年12月在公司總部完成了無(wú)人機(jī)投遞的室外測(cè)試。2014年9月,第2代無(wú)人機(jī)獲得德國(guó)聯(lián)邦運(yùn)輸部和航空管理局許可,飛越北海提取藥品,于2016年3月完成第3代無(wú)人機(jī)試飛[1]。谷歌、亞馬遜和DHL等都已經(jīng)將無(wú)人機(jī)運(yùn)用到配送領(lǐng)域,其開(kāi)發(fā)的大多數(shù)無(wú)人機(jī)以每小時(shí)48～64 km的速度飛行,飛行距離為16～48 km,有效載荷一般為5 kg左右[2]。由于無(wú)人機(jī)在大多數(shù)場(chǎng)景中可采取直線(xiàn)飛行,相比于車(chē)輛配送有配送距離短、飛行速度快等優(yōu)勢(shì),然而無(wú)人機(jī)又有著有效載荷低、續(xù)航能力差的特點(diǎn),單獨(dú)使用無(wú)人機(jī)只適用于小批量多批次的配送。

2014年,Wohlsen[3]首次提出無(wú)人機(jī)與運(yùn)輸車(chē)協(xié)同配送的想法,其構(gòu)思的未來(lái)物流配送是無(wú)人機(jī)與運(yùn)輸車(chē)可同時(shí)進(jìn)行獨(dú)立送貨,無(wú)人機(jī)在完成配送任務(wù)后需返回運(yùn)輸車(chē)。在此基礎(chǔ)上,無(wú)人機(jī)和車(chē)輛協(xié)同配送的研究近年來(lái)開(kāi)始興起,部分企業(yè)也對(duì)此進(jìn)行了嘗試,如輕浮自主無(wú)人駕駛飛機(jī)交付、多米諾無(wú)人駕駛飛機(jī)交付和HorseFly無(wú)人駕駛飛機(jī)交付,其中無(wú)人駕駛飛機(jī)從交付車(chē)輛發(fā)射,在一個(gè)位置進(jìn)行包裹交付,而車(chē)輛同時(shí)進(jìn)行另一次交付[4]。

任新惠等[5]對(duì)現(xiàn)有無(wú)人機(jī)和車(chē)輛組合配送的相關(guān)文獻(xiàn)進(jìn)行綜述,總結(jié)出無(wú)人機(jī)和車(chē)輛協(xié)同配送的4種模式:車(chē)輛協(xié)助無(wú)人機(jī)配送模式,無(wú)人機(jī)協(xié)助車(chē)輛配送模式,無(wú)人機(jī)與車(chē)輛獨(dú)立配送模式,無(wú)人機(jī)和車(chē)輛同步配送模式。雖然任新惠總結(jié)出了無(wú)人機(jī)和車(chē)輛組合物流配送的方式,但在實(shí)際場(chǎng)景中往往可能存在多種模式,而不是運(yùn)用單一模式。本文將從車(chē)輛和無(wú)人機(jī)映射關(guān)系的角度入手,分析無(wú)人機(jī)和車(chē)輛協(xié)同配送的映射模式,討論相關(guān)變體、參數(shù)和約束條件,總結(jié)目標(biāo)及相關(guān)算法,最后對(duì)未來(lái)研究方向提出展望。

本文第1節(jié)在單車(chē)單機(jī)映射模式(traveling salesman problem with drone，TSP-D)中主要總結(jié)了無(wú)人機(jī)和車(chē)輛協(xié)同配送的4種模式，包括無(wú)人機(jī)和車(chē)輛同步配送模式(flying sidekick traveling salesman problem, FSTSP)、無(wú)人機(jī)和車(chē)輛并行配送模式(parallel drone scheduling traveling salesman problem, PDSTSP)、車(chē)輛保障無(wú)人機(jī)配送模式(vehicle guarantee drone traveling salesman problem, VGDTSP)和無(wú)人機(jī)保障車(chē)輛配送模式(drone guarantee vehicle traveling salesman problem, DGVTSP)。第2節(jié)主要總結(jié)了單車(chē)多機(jī)映射模式(traveling salesman problem with multiple drones，TSP-mD)和多車(chē)多機(jī)映射模式(multiple traveling salesman problem with drones，MTSPD)的相關(guān)文獻(xiàn)。第3節(jié)從3個(gè)方面總結(jié)討論了3種映射模式:首先,討論了3種映射模式下變體的相同處和不同處;其次,總結(jié)了目前無(wú)人機(jī)和車(chē)輛協(xié)同配送映射模式中研究的目標(biāo)和算法,進(jìn)而討論了無(wú)人機(jī)和車(chē)輛協(xié)同配送映射模式所涉及的相關(guān)參數(shù);最后,討論了無(wú)人機(jī)和車(chē)輛協(xié)同配送映射模式面對(duì)實(shí)際問(wèn)題所涉及的約束條件。第4節(jié)在對(duì)無(wú)人機(jī)和車(chē)輛協(xié)同配送映射模式的未來(lái)展望中考慮了實(shí)際性能分析和異構(gòu)無(wú)人機(jī)優(yōu)化。

1 TSP-D

對(duì)TSP-D的分析可基于任新惠提出的無(wú)人機(jī)和車(chē)輛組合配送模式。

1.1 FSTSP

2015年,Murray和Chu[6]引入了一種新型的旅行商問(wèn)題,稱(chēng)為FSTSP,提出了在車(chē)輛頂部安裝一架無(wú)人機(jī)的想法,該無(wú)人機(jī)可以在車(chē)輛進(jìn)行一項(xiàng)交付任務(wù)的同時(shí)進(jìn)行另一項(xiàng)交付任務(wù)。一旦無(wú)人機(jī)完成交付,就需要在當(dāng)前交付位置或沿其路線(xiàn)返回車(chē)輛,到下一個(gè)交付位置。由于問(wèn)題復(fù)雜,FSTSP只考慮一輛車(chē)輛和一架無(wú)人機(jī)的情形,如圖1所示。

圖1 FSTSP拓?fù)鋱DFig.1 FSTSP topology

Agatz等[7]提出的無(wú)人機(jī)旅行推銷(xiāo)員問(wèn)題是獨(dú)立于FSTSP提出的,但仍然共享大多數(shù)常見(jiàn)的假設(shè)。在這個(gè)問(wèn)題上,FSTSP的一個(gè)關(guān)鍵區(qū)別是無(wú)人機(jī)可以在車(chē)輛發(fā)射的相同位置被找回,并且無(wú)人機(jī)的操作受到飛行距離而不是時(shí)間的限制,然后采用局部搜索與動(dòng)態(tài)規(guī)劃相結(jié)合的算法求解模型。

Bouman等[8]基于貝爾曼-霍爾德-卡普(Bellman-Held-Karp)動(dòng)態(tài)規(guī)劃算法介紹了一種求解FSTSP的三步精確式方法,并將該方法的最后一步推廣到A*算法。此外,文獻(xiàn)[8]嘗試將這種精確式算法應(yīng)用于限制車(chē)輛在與無(wú)人機(jī)分離時(shí)可能訪(fǎng)問(wèn)的位置數(shù)量的問(wèn)題,這個(gè)限制縮短了計(jì)算時(shí)間,但代價(jià)是可能從解空間中移除最優(yōu)解。Ha等[9]提出了兩種啟發(fā)式方法——貪婪隨機(jī)自適應(yīng)搜索問(wèn)題(greedy random adaptive search problem, GRASP)和旅行商問(wèn)題-局部搜索(traveling salesman problem-local search, TSP-LS)，用于啟發(fā)式求解FSTSP。GRASP元啟發(fā)式算法首先使用3種不同的啟發(fā)式算法對(duì)車(chē)輛旅行推銷(xiāo)員問(wèn)題生成旅行,然后使用分割算法將一些客戶(hù)從車(chē)輛旅行中移除,并將其分配給無(wú)人機(jī)。TSP-LS啟發(fā)式算法改編自Murray和Chu提出的啟發(fā)式算法,但在算法的每次迭代過(guò)程中,在無(wú)人機(jī)和車(chē)輛路線(xiàn)之間重新定位客戶(hù)所節(jié)省的成本計(jì)算方面存在差異。在擁有100個(gè)客戶(hù)的問(wèn)題實(shí)例上的實(shí)驗(yàn)結(jié)果表明,GRASP啟發(fā)式算法在求解質(zhì)量上優(yōu)于TSP-LS啟發(fā)式算法,盡管其需要更多的計(jì)算時(shí)間。Es和Ozmutlu[10]開(kāi)發(fā)了一種基于兩階段分解的算法來(lái)求解FSTSP。在第一階段,使用貪婪啟發(fā)式方法將客戶(hù)分配到車(chē)輛和無(wú)人機(jī)上。在第二階段,求解一個(gè)數(shù)學(xué)規(guī)劃模型,得到無(wú)人機(jī)的行程,使無(wú)人機(jī)在交會(huì)點(diǎn)的等待時(shí)間最少。Pedro等[11]對(duì)FSTSP模型進(jìn)行了擴(kuò)展,允許無(wú)人機(jī)在與車(chē)輛的兩次連續(xù)會(huì)合之間每次訪(fǎng)問(wèn)幾個(gè)客戶(hù)。除了多點(diǎn)假設(shè),其模型的其他特點(diǎn)是沒(méi)有為車(chē)輛和無(wú)人機(jī)預(yù)先建立路線(xiàn),并且將每個(gè)位置視為其潛在同步點(diǎn),然后通過(guò)模擬退火算法的全局優(yōu)化方案,求解了大規(guī)模的場(chǎng)景。

綜上所述,在FSTSP模式中,車(chē)輛一般配送至離供應(yīng)點(diǎn)較近的需求點(diǎn),而無(wú)人機(jī)輔助車(chē)輛進(jìn)行末端配送,以有效節(jié)省總的配送時(shí)間和成本。然而,由于無(wú)人機(jī)在配送過(guò)程中依賴(lài)于車(chē)輛,所以需要考慮無(wú)人機(jī)和車(chē)輛在何處對(duì)接,因此對(duì)協(xié)同性的要求很高,這可以參考傳統(tǒng)的拖掛運(yùn)輸問(wèn)題(truck and trailer routing problem, TTRP)。目前,針對(duì)FSTSP模式的研究還停留在基礎(chǔ)階段,較少考慮無(wú)人機(jī)和車(chē)輛對(duì)接時(shí)存在的實(shí)際問(wèn)題,并且在其問(wèn)題求解算法中通?；趧?dòng)態(tài)規(guī)劃的思想分階段求解無(wú)人機(jī)和車(chē)輛的任務(wù)目標(biāo),未來(lái)需要耦合無(wú)人機(jī)和車(chē)輛的協(xié)同任務(wù)目標(biāo)。

1.2 PDSTSP

2015年,Murray和Chu[6]除了提出FSTSP,在文獻(xiàn)中還提出PDSTSP,即車(chē)輛和無(wú)人機(jī)從倉(cāng)庫(kù)出發(fā)獨(dú)立進(jìn)行交付,如圖2所示。

圖2 PDSTSP拓?fù)鋱DFig.2 PDSTSP topology

無(wú)人機(jī)和車(chē)輛數(shù)量的不同不會(huì)對(duì)PDSTSP的模式運(yùn)用帶來(lái)任何變化,所以本節(jié)不只基于TSP-D進(jìn)行文獻(xiàn)回顧,還回顧了單車(chē)多機(jī)、多車(chē)多機(jī)模式的文獻(xiàn)。Ham[12]對(duì)PDSTSP問(wèn)題進(jìn)行了拓展,其中無(wú)人機(jī)可以實(shí)施連續(xù)多階段的取件和配送任務(wù),解決了多車(chē)多機(jī)保障多需求點(diǎn)的配送任務(wù)分配。Kim和Moon[13]擴(kuò)展PDSTSP并構(gòu)建了單無(wú)人機(jī)站臺(tái)的旅行商問(wèn)題(traveling salesman problem with a drone station, TSP-DS)的混合整數(shù)線(xiàn)性規(guī)劃(mixed integer linear programming, MILP)模型,考慮了一輛車(chē)和多架無(wú)人機(jī),以允許無(wú)人機(jī)獨(dú)立于車(chē)輛,從倉(cāng)庫(kù)以及從預(yù)先指定的無(wú)人機(jī)站進(jìn)行調(diào)度,最后發(fā)現(xiàn)TSP-DS比PDSTSP更為高效。Chauhan等[14]針對(duì)PDSTSP問(wèn)題的特點(diǎn),構(gòu)建了以配送無(wú)人機(jī)最大航程為直徑、以最大范圍覆蓋用戶(hù)為目標(biāo)的倉(cāng)庫(kù)選址模型,并以三階段貪婪算法求解。

由此看出,PDSTSP問(wèn)題可以分解為兩個(gè)經(jīng)典的運(yùn)籌學(xué)問(wèn)題: TSP和并行機(jī)調(diào)度問(wèn)題(parallel machine scheduling problem, PMS)。PDSTSP模式只需要基于上述兩個(gè)問(wèn)題考慮如何合理分配客戶(hù)以實(shí)現(xiàn)完工時(shí)間最小化,求解難度較小,但其重點(diǎn)是如何判斷先進(jìn)行TSP問(wèn)題求解或是先進(jìn)行PMS問(wèn)題求解,這將會(huì)極大影響PSDTSP問(wèn)題的求解質(zhì)量。

1.3 VGDTSP

Mathew等[15]在研究多種運(yùn)輸工具配送問(wèn)題(heterogeneous delivery problem, HDP)時(shí)，首次提出車(chē)輛只負(fù)責(zé)裝載配送無(wú)人機(jī)與需求物資,對(duì)所有需求點(diǎn)的配送都由無(wú)人機(jī)完成,但其在模型約束中事先設(shè)定了無(wú)人機(jī)配送的任務(wù)點(diǎn),因此該問(wèn)題是傳統(tǒng)的旅行商問(wèn)題。

Savuran和Karakaya[16]提出了VGDTSP,其目標(biāo)是通過(guò)找到車(chē)輛?？奎c(diǎn)來(lái)發(fā)射一架無(wú)人機(jī),從而在為所有客戶(hù)提供服務(wù)的同時(shí),最大限度地縮減無(wú)人機(jī)的行駛距離。這個(gè)問(wèn)題可稱(chēng)為“倉(cāng)庫(kù)機(jī)動(dòng)性問(wèn)題”,因?yàn)檐?chē)輛是無(wú)人機(jī)的移動(dòng)倉(cāng)庫(kù)。文獻(xiàn)[16]開(kāi)發(fā)了一種遺傳算法,用一輛車(chē)輛和一架無(wú)人機(jī)來(lái)解決一些問(wèn)題實(shí)例,并用最近鄰和爬山算法來(lái)評(píng)估和比較所獲得的結(jié)果。Othma等[17]基于VGDTSP證明了單車(chē)輛和單無(wú)人機(jī)的多式聯(lián)運(yùn)是NP(non-deterministic polynomial)-hard問(wèn)題,并提出了求解該問(wèn)題的近似算法。

Luo等[18]在TSP-D的模型構(gòu)建中,允許無(wú)人機(jī)單次發(fā)射實(shí)施多個(gè)客戶(hù)的配送,并考慮了無(wú)人機(jī)與車(chē)輛同時(shí)在時(shí)間和空間上的協(xié)同約束。該問(wèn)題被公式化為一個(gè)MILP模型,描述了一個(gè)兩級(jí)位置路由問(wèn)題。為了解決這個(gè)問(wèn)題,開(kāi)發(fā)了兩種啟發(fā)式方法,首先構(gòu)建一個(gè)車(chē)輛旅行,然后將其分成幾個(gè)子旅行,將每個(gè)子旅行分配給一個(gè)無(wú)人機(jī)。Carlsson和Song[19]考慮將一輛貨車(chē)攜帶一架無(wú)人機(jī),拓展提出無(wú)人機(jī)配送的始發(fā)點(diǎn)與回收點(diǎn)可在車(chē)輛路線(xiàn)上的任一位置,通過(guò)連續(xù)逼近法找到車(chē)輛保障無(wú)人機(jī)的最佳路線(xiàn)。文獻(xiàn)[19]的一個(gè)關(guān)鍵發(fā)現(xiàn)是無(wú)人機(jī)與車(chē)輛協(xié)同使用的潛在收益(提高效率)與無(wú)人機(jī)和車(chē)輛之間的相對(duì)速度的平方根相關(guān)。

本文將上述這種無(wú)人機(jī)和車(chē)輛組合配送的方式稱(chēng)為VGDTSP,如圖3所示。這種模式屬于給定車(chē)輛路線(xiàn)的無(wú)人機(jī)調(diào)度問(wèn)題(drone scheduling problem for given truck route,DSP)的拓展,并且包括DSP。這一模式適用于車(chē)輛無(wú)法直達(dá)客戶(hù)地點(diǎn)的城市場(chǎng)景,也適合客戶(hù)點(diǎn)分散、單位面積物流需求量小、道路條件較差的農(nóng)村地區(qū)配送。

圖3 VGDTSP拓?fù)鋱DFig.3 VGDTSP topology

1.4 DGVTSP

DGVTSP是指車(chē)輛執(zhí)行配送任務(wù),由無(wú)人機(jī)作為輔助為車(chē)輛補(bǔ)貨,這種配送模式主要適用于車(chē)輛的途中補(bǔ)貨。Dayarian等[20]關(guān)注的是無(wú)人機(jī)補(bǔ)給的同一天交付問(wèn)題,其中由車(chē)輛監(jiān)督交付訂單,無(wú)人機(jī)的作用是向車(chē)輛提供補(bǔ)給,最后提出了一種啟發(fā)式方法來(lái)解決該問(wèn)題。但為了簡(jiǎn)化研究模型,考慮了僅有一個(gè)配送中心、一輛貨車(chē)和一架無(wú)人機(jī)的情況。McCunney和Cauwenberghe[21]假設(shè)無(wú)人機(jī)為車(chē)輛提供包裹補(bǔ)給,以實(shí)現(xiàn)當(dāng)天交付服務(wù):無(wú)人駕駛飛機(jī)將包裹運(yùn)送到一組預(yù)先指定的轉(zhuǎn)運(yùn)點(diǎn),每輛車(chē)輛從專(zhuān)用轉(zhuǎn)運(yùn)點(diǎn)提取包裹,為客戶(hù)所在地的特定區(qū)域提供配送服務(wù),根據(jù)訂單到達(dá)間隔時(shí)間、轉(zhuǎn)運(yùn)點(diǎn)數(shù)量、車(chē)輛數(shù)量和無(wú)人機(jī)數(shù)量的不同數(shù)值進(jìn)行綜合分析。

由于無(wú)人機(jī)配送剛剛興起,相應(yīng)的配套政策還不夠健全,短期內(nèi)可能無(wú)法實(shí)現(xiàn)大規(guī)模無(wú)人機(jī)配送。加之受無(wú)人機(jī)載重能力弱的限制,DGVTSP的運(yùn)用場(chǎng)景受限,所以相關(guān)研究很少,后文不予以討論。

2 TSP-mD和MTSPD

TSP-mD和MTSPD這兩類(lèi)研究?jī)?nèi)容和問(wèn)題基本一致,所以歸為一節(jié)進(jìn)行綜述。但這兩種映射模式與TSP-D有很大區(qū)別:這兩種映射模式能實(shí)施多種無(wú)人機(jī)和車(chē)輛組合模式。由于MTSPD是TSP-mD的更NP-hard問(wèn)題,目前大部分文獻(xiàn)已開(kāi)始研究基于FSTSP的MTSPD,而基于VGDTSP的研究仍主要停留于研究TSP-mD。

2.1 基于單一模式

2.1.1 基于FSTSP的MTSPD

Campbell等[22]對(duì)MTSPD問(wèn)題提出了連續(xù)近似(continuous approximation,CA)模型,以獲得每條路線(xiàn)上車(chē)輛和無(wú)人機(jī)的最佳交付數(shù)量、每輛車(chē)輛上無(wú)人機(jī)的最佳數(shù)量以及車(chē)輛-無(wú)人機(jī)混合交付問(wèn)題中的總運(yùn)營(yíng)成本。Wang等[23]通過(guò)研究發(fā)現(xiàn)無(wú)人駕駛飛機(jī)可以從倉(cāng)庫(kù)或任何客戶(hù)位置的車(chē)輛上發(fā)射,也可以由不同客戶(hù)位置的車(chē)輛取回(或在倉(cāng)庫(kù)結(jié)束其旅程),并建立了MTSPD模型。文獻(xiàn)[22]對(duì)使用無(wú)人機(jī)可以節(jié)省的時(shí)間提出了幾個(gè)上限,上限是通過(guò)研究最優(yōu)解的結(jié)構(gòu)獲得的,取決于無(wú)人機(jī)與車(chē)輛的相對(duì)速度以及每輛車(chē)輛的無(wú)人機(jī)數(shù)量。Poikonen等[24]對(duì)Wang等的工作進(jìn)行了改進(jìn),提出了從任意位置發(fā)射和回收無(wú)人機(jī)的可能性(同車(chē)輛),而不是僅限于客戶(hù)位置。Daknama和Kraus[25]提出了無(wú)人機(jī)車(chē)輛路徑問(wèn)題,該問(wèn)題具有Wang等無(wú)人機(jī)路徑問(wèn)題的大部分特征,不同的是文獻(xiàn)[25]允許無(wú)人機(jī)由不同的車(chē)輛發(fā)射和回收。Wang和She[26]基于無(wú)人機(jī)可由不同的車(chē)輛發(fā)射和回收,通過(guò)一個(gè)分支定價(jià)(branch and price, B&P)算法求解了MTSPD。在該算法的定界子問(wèn)題中,設(shè)計(jì)了一個(gè)特殊的網(wǎng)絡(luò)來(lái)區(qū)分不同類(lèi)型的路徑和節(jié)點(diǎn),并通過(guò)剪枝和擴(kuò)展策略提出了一種改進(jìn)的脈沖算法。

Sacramento等[27]進(jìn)一步擴(kuò)展了FSTSP模型,考慮了車(chē)輛的容量限制,并提出了一種自適應(yīng)大鄰域搜索元啟發(fā)式算法來(lái)解決MTSPD。Daniel等[28]基于MILP,同時(shí)考慮了無(wú)人機(jī)可循環(huán)操作和不可循環(huán)操作,即車(chē)輛既可以在無(wú)人機(jī)發(fā)射點(diǎn)等待無(wú)人機(jī)返回,也可以執(zhí)行配送任務(wù),在下一需求點(diǎn)與無(wú)人機(jī)匯合;其次,文獻(xiàn)[28]還對(duì)無(wú)人機(jī)參數(shù)進(jìn)行了靈敏度分析,如有限時(shí)間、有限距離等情況;最后,提出混合無(wú)人機(jī)編隊(duì)下無(wú)人機(jī)存在速度和耐久性的不同。Euchi和Sadok[29]也研究了MTSPD問(wèn)題,但假設(shè)每輛車(chē)只攜帶一架無(wú)人機(jī),設(shè)計(jì)了一種混合遺傳-掃描算法進(jìn)行求解,即采用掃描算法作為局部搜索的遺傳算法,并在構(gòu)造初始解時(shí)采用了最近鄰算法和改進(jìn)的節(jié)約算法。Felix和Udo[30]提出一個(gè)分支切割(branch and cut, B&C)算法進(jìn)行求解,并使用有效的不等式來(lái)加強(qiáng)線(xiàn)性松弛和加速求解過(guò)程,最后說(shuō)明MTSPD不僅可以提高交付速度,還可以減少車(chē)隊(duì)規(guī)模,而不會(huì)減緩交付過(guò)程,并增加車(chē)輛司機(jī)的工作量。

MTSPD模式是將FSTSP中TSP-D擴(kuò)展的一種模式,協(xié)同性從二維升至高維,建模復(fù)雜難度急劇上升,求解更加困難,所以在絕大部分MTSPD問(wèn)題研究中,設(shè)置了較多的假設(shè)條件,并且忽略了很多現(xiàn)實(shí)因素而簡(jiǎn)化模型。當(dāng)不僅僅能實(shí)現(xiàn)只基于FSTSP的MTSPD,而是實(shí)現(xiàn)基于多種組合模式的MTSPD時(shí),才能真正將MTSPD運(yùn)用于真實(shí)的配送場(chǎng)景中。

2.1.2 基于VGDTSP的TSP-mD

Ferrandez等[31]研究了車(chē)輛和無(wú)人機(jī)協(xié)同交付系統(tǒng)中的時(shí)間效率和能量效率,考慮由一輛貨車(chē)保障多架無(wú)人機(jī)完成交付作業(yè),通過(guò)融合K均值聚類(lèi)和遺傳算法,解決了聯(lián)合配送時(shí)無(wú)人機(jī)發(fā)射位置的確定以及單車(chē)攜帶無(wú)人機(jī)數(shù)量的優(yōu)化問(wèn)題。文獻(xiàn)[31]做了一些實(shí)驗(yàn)來(lái)研究各種相對(duì)速度的影響,結(jié)果表明無(wú)人機(jī)的速度應(yīng)該至少是車(chē)輛速度的2倍,以顯著減少路線(xiàn)時(shí)間。Boysen等[32]基于VGDTSP研究了由沿著給定車(chē)輛路線(xiàn)運(yùn)行的車(chē)輛發(fā)射無(wú)人機(jī)的調(diào)度問(wèn)題。根據(jù)車(chē)輛上無(wú)人機(jī)的數(shù)量和無(wú)人機(jī)的操作策略,導(dǎo)出了6個(gè)基本問(wèn)題版本,并顯示了其計(jì)算復(fù)雜性。Chang和Lee[33]展示了一輛車(chē)輛作為無(wú)人機(jī)的移動(dòng)倉(cāng)庫(kù),以獲得車(chē)輛和無(wú)人機(jī)返回倉(cāng)庫(kù)的最短時(shí)間。其開(kāi)發(fā)了一個(gè)三階段算法來(lái)解決多達(dá)100個(gè)客戶(hù)的幾個(gè)問(wèn)題實(shí)例。該算法首先使用K均值聚類(lèi)對(duì)客戶(hù)進(jìn)行分組,然后通過(guò)在第二步中求解一個(gè)旅行商問(wèn)題來(lái)確定車(chē)輛路線(xiàn),最后通過(guò)尋找移動(dòng)集群中心的移位權(quán)值和非線(xiàn)性規(guī)劃,以增加所獲得的集群覆蓋的總面積。Aline和khaled[34]基于VGSTSP模式提出單車(chē)多機(jī)模式,無(wú)人機(jī)每次執(zhí)行交付任務(wù)能配送一個(gè)或多個(gè)客戶(hù),并且在每個(gè)位置都能發(fā)射和回收多個(gè)無(wú)人機(jī)。最后設(shè)計(jì)了改進(jìn)節(jié)約里程算法,對(duì)比求解得到:當(dāng)使用的無(wú)人機(jī)在其飛行范圍和承載能力方面平衡時(shí),網(wǎng)絡(luò)運(yùn)行成本顯示為最小。一般以客戶(hù)密度高為特點(diǎn)的服務(wù)區(qū),需要承載能力大的無(wú)人機(jī);客戶(hù)稀少的服務(wù)區(qū),更適合使用航程較長(zhǎng)的無(wú)人機(jī)。

目前,TSP-mD模式仍停留在基于VGDTSP模式的研究,相比于MTSPD而言復(fù)雜度較低,假設(shè)條件較少,研究范圍較廣。雖然當(dāng)將VGDTSP模式拓展到MTSPD時(shí),復(fù)雜度也急劇增大,但復(fù)雜度仍遠(yuǎn)比不上基于FSTSP的MTSPD,這是因?yàn)榛赩GDTSP的MTSPD不需要考慮車(chē)輛之間的任務(wù)分配,而只需要考慮無(wú)人機(jī)與車(chē)輛之間的映射關(guān)系,比如無(wú)人機(jī)不一定返回原先出發(fā)的車(chē)輛,而是根據(jù)最優(yōu)原則返回至任一車(chē)輛。

2.2 基于多種組合模式

Patchara等[35]總結(jié)了MTSPD的4種運(yùn)行模式:① 無(wú)人機(jī)從車(chē)輛出發(fā)執(zhí)行配送和交付任務(wù),在任務(wù)完成后返回同一車(chē)輛,如圖4所示;② 無(wú)人機(jī)從車(chē)輛出發(fā)執(zhí)行配送和交付任務(wù),在任務(wù)完成后返回不同車(chē)輛,如圖5所示;③ 無(wú)人機(jī)從倉(cāng)庫(kù)出發(fā)執(zhí)行配送和交付任務(wù),在任務(wù)完成后返回車(chē)輛,如圖6所示;④ 無(wú)人機(jī)從倉(cāng)庫(kù)出發(fā)執(zhí)行配送和交付任務(wù),在任務(wù)完成后直接返回倉(cāng)庫(kù),如圖7所示。

圖4 無(wú)人機(jī)返回同一車(chē)輛的MTSPD運(yùn)行模式Fig.4 MTSPD operating mode of drones returning to the same vehicles

圖5 無(wú)人機(jī)返回不同車(chē)輛的MTSPD運(yùn)行模式Fig.5 MTSPD operating mode of drones returning to the different vehicles

圖6 無(wú)人機(jī)由倉(cāng)庫(kù)出發(fā)返回車(chē)輛的MTSPD運(yùn)行模式Fig.6 MTSPD operating mode of drones from warehouse to the vehicles

圖7 無(wú)人機(jī)由倉(cāng)庫(kù)出發(fā)返回倉(cāng)庫(kù)的MTSPD運(yùn)行模式Fig.7 MTSPD operating mode of drones from warehouse to warehouse

由圖4～圖7,可以看出前3種模式都屬于FSTSP模式,最后一種模式則屬于PDSTSP模式。聯(lián)合此4種運(yùn)行模式思想,發(fā)現(xiàn)運(yùn)用PDSTSP和FSTSP組合模式,比單一使用FSTSP能減少配送時(shí)間。文獻(xiàn)[35]在求解中開(kāi)發(fā)了一種新的啟發(fā)式算法,稱(chēng)為自適應(yīng)插入啟發(fā)式算法(adaptive insertion heuristics, ADI)，來(lái)解決MTSPD。啟發(fā)式方法由兩個(gè)階段組成:構(gòu)建多旅行商解決方案和對(duì)初始多旅行商解決方案應(yīng)用移除和插入操作符來(lái)構(gòu)建MTSPD解決方案。在ADI中涉及3種多旅行商啟發(fā)式算法:遺傳算法、組合K均值/最近鄰法和隨機(jī)聚類(lèi)/旅行法。在Dukkanci等[36]研究的無(wú)人機(jī)和車(chē)輛協(xié)同配送中,建立了PDSTSP和VGDTSP組合模式,但其已確定了車(chē)輛的路線(xiàn),如圖8所示。

圖8 VGDTSP和PDSTSP的組合模式Fig.8 Combination mode of VGDTSP and PDSTSP

目前,對(duì)基于多種組合模式的研究較少,但研究的拓展空間很大。雖然目前相關(guān)文獻(xiàn)只涉及了PDSTSP和VGDTSP的組合模式,但未來(lái)還可以探討FSTSP和PDSTSP組合模式、FSTSP和VGDTSP組合模式、VGDTSP和無(wú)人機(jī)和車(chē)輛協(xié)同配送模式(vehicle routing problem with drone, VRPD)的組合模式等。在未來(lái)，要想運(yùn)用好多種組合模式,需要從頂層設(shè)計(jì)入手,建立起多種組合模式的模型,并設(shè)計(jì)出可行的算法。

3 3種映射模式下的總結(jié)和討論

前兩節(jié)將大部分關(guān)于無(wú)人機(jī)和車(chē)輛協(xié)同配送的相關(guān)文獻(xiàn)進(jìn)行了綜述,有些文獻(xiàn)將無(wú)人機(jī)和車(chē)輛協(xié)同配送的模式命名為VRPD,但無(wú)特殊情況時(shí),VRPD模式可以轉(zhuǎn)化為MTSPD模式。本節(jié)將基于TSP-D的前兩者(即FSTSP和PDSTSP)的TSP-D、TSP-mD和MTSPD的文獻(xiàn)回顧,進(jìn)行綜合性分析和論述,并對(duì)未來(lái)無(wú)人機(jī)和車(chē)輛協(xié)同配送的研究方向提出展望。

3.1 3種映射模式下的變體討論

3.1.1 3種映射模式下變體的相同處

由于3種映射模式只是改變了無(wú)人機(jī)和車(chē)輛的數(shù)量,所以實(shí)質(zhì)上MTSPD是基于TSP-mD的更復(fù)雜問(wèn)題,而TSP-mD是基于TSP-D的更復(fù)雜問(wèn)題。3種映射模式下的相同處即為T(mén)SP-D下的問(wèn)題,本節(jié)將基于TSP-D分析FSTSP、PDSTSP和VGDTSP下的異同。大部分文獻(xiàn)將無(wú)人機(jī)與車(chē)輛協(xié)同配送分為串聯(lián)式服務(wù)和并聯(lián)式服務(wù),將串聯(lián)式服務(wù)定義為無(wú)人機(jī)安裝在車(chē)輛上并一起使用,如FSTSP;將并聯(lián)式服務(wù)定義為無(wú)人機(jī)和車(chē)輛互不干擾,如PDSTSP[37]。本文提出一種新的串并聯(lián)服務(wù)定義:在VGDTSP中,所有需求點(diǎn)都是由無(wú)人機(jī)進(jìn)行交付,所以可稱(chēng)為串聯(lián)服務(wù);PDSTSP和FSTSP中部分需求點(diǎn)由無(wú)人機(jī)交付,部分需求點(diǎn)由車(chē)輛交付,所以可稱(chēng)為并聯(lián)服務(wù)。分析FSTSP的相關(guān)文獻(xiàn),其變體有如下4種形式:① 無(wú)人機(jī)能否從倉(cāng)庫(kù)起飛或返回;② 無(wú)人機(jī)是否執(zhí)行可循環(huán)操作(車(chē)輛在原地等待無(wú)人機(jī)),此時(shí)包括3種情況:只能執(zhí)行可循環(huán)操作、不能執(zhí)行可循環(huán)操作、可能執(zhí)行可循環(huán)操作;③ 無(wú)人機(jī)在執(zhí)行一次配送任務(wù)時(shí)能否前往多個(gè)需求點(diǎn);④ 無(wú)人機(jī)能否從車(chē)輛路徑的任一位置起飛或返回,不能的情況為無(wú)人機(jī)只能從需求點(diǎn)起飛和返回。

在VGDTSP中,由于車(chē)輛專(zhuān)門(mén)保障無(wú)人機(jī),不存在上述變體形式中的②和④,即在VGDTSP中無(wú)人機(jī)可能執(zhí)行可循環(huán)操作,并且能從車(chē)輛路徑的任一位置起飛和返回。同時(shí)，對(duì)于變體形式中的①,在VGDTSP中無(wú)論無(wú)人機(jī)能否從倉(cāng)庫(kù)起飛或返回,對(duì)實(shí)驗(yàn)結(jié)果都不會(huì)造成影響,因?yàn)闊o(wú)人機(jī)從車(chē)輛路徑中最靠近倉(cāng)庫(kù)的位置發(fā)射,等同于從倉(cāng)庫(kù)發(fā)射,所以變體形式①在VGDTSP中也可以不討論。在PDSTSP中,無(wú)人機(jī)本來(lái)就是從倉(cāng)庫(kù)起飛執(zhí)行獨(dú)立交付任務(wù),所以不存在變體形式①、②和④。由于在PDSTSP中,無(wú)人機(jī)每次執(zhí)行配送任務(wù)的起始點(diǎn)都是倉(cāng)庫(kù),所以對(duì)于變體形式③,往往是根據(jù)無(wú)人機(jī)的續(xù)航能力進(jìn)行判斷,不需要提前假設(shè)。

3.1.2 3種映射模式下變體的不同處

3種映射模式下,只有基于FSTSP,才存在不同變體,TSP-mD中的FSTSP變體除了包含TSP-D中的4種變體形式,還包含任何位置能否發(fā)射和回收多架無(wú)人機(jī);MTSPD下的FSTSP變體除了包含TSP-D中的5種變體形式,還包含無(wú)人機(jī)能否返回不同車(chē)輛,如圖5所示。

除了上述不同,TSP-mD和MTSPD與TSP-D最大的區(qū)別在于:TSP-mD和MTSPD能同時(shí)使用多種組合配送模式。由于VGDTSP和FSTSP之間存在一定的矛盾性(車(chē)輛是否需要交付到客戶(hù)),所以?xún)烧卟荒芙M合使用。因此，在TSP-mD和MTSPD之間的多種組合模式往往是PDSTSP和FSTSP(見(jiàn)圖7)、PDSTSP和VGDTSP(見(jiàn)圖8)的兩種組合模式。雖然VGDTSP和FSTSP不能聯(lián)合使用,但將VGDTSP的思想運(yùn)用到FSTSP中,就變成了FSTSP中的一個(gè)變體形式:無(wú)人機(jī)能從車(chē)輛路線(xiàn)上的任一位置起飛和返回。

3.2 目標(biāo)和算法總結(jié)

3.2.1 目標(biāo)總結(jié)

無(wú)論是3種基礎(chǔ)配送模式還是3種映射模式,其目標(biāo)函數(shù)主要研究3方面內(nèi)容,但在不同映射模式的變體中存在差異,具體分析如下。

(1) 最小總配送時(shí)間，即最小-和時(shí)間[38],由所有配送時(shí)間和等待時(shí)間相加得到:

(1)

此目標(biāo)可分為兩類(lèi):一是無(wú)人機(jī)最小-和時(shí)間只考慮無(wú)人機(jī)的最小總配送時(shí)間,一般適用于VGDTSP中,這是因?yàn)樵赩GDTSP中車(chē)輛不進(jìn)行交付任務(wù),此時(shí)可以將式(1)中的第3項(xiàng)刪除;二是無(wú)人機(jī)和車(chē)輛最小-和時(shí)間,不僅要考慮無(wú)人機(jī),還需要考慮車(chē)輛的最小總配送時(shí)間,一般適用于FSTSP和PDSTSP中。將式(1)擴(kuò)展到TSP-mD中時(shí),最小總配送時(shí)間變?yōu)?/p>

(2)

式中:K為無(wú)人機(jī)集合;xijk為決策變量,xijk=1代表有無(wú)人機(jī)k從i點(diǎn)到j(luò)點(diǎn)的路徑。

將式(1)擴(kuò)展到MTSPD中時(shí),最小總配送時(shí)間變?yōu)?/p>

(3)

式中:W為車(chē)輛集合;yijw為決策變量,yijw=1代表有車(chē)輛w從i點(diǎn)到j(luò)點(diǎn)的路徑。

(2) 最小完成配送時(shí)間，即最小-最大時(shí)間[38],此目標(biāo)也可分為兩類(lèi):當(dāng)無(wú)人機(jī)被允許從需求點(diǎn)返回倉(cāng)庫(kù)時(shí),此時(shí)最小完成配送時(shí)間取車(chē)輛和無(wú)人機(jī)到達(dá)倉(cāng)庫(kù)時(shí)間的最大值,即

(4)

當(dāng)無(wú)人機(jī)不被允許從需求點(diǎn)返回倉(cāng)庫(kù)時(shí),此時(shí)最小完成配送時(shí)間為車(chē)輛到達(dá)倉(cāng)庫(kù)的時(shí)間,即

(5)

(3) 最小配送成本根據(jù)對(duì)成本包含的內(nèi)容不同而不同。配送成本通常指車(chē)輛和無(wú)人機(jī)在配送過(guò)程中基于行駛距離而產(chǎn)生的油耗和電力成本[39-41]。然而,成本的適當(dāng)建模通常是困難的,因?yàn)槌杀救Q于許多影響變量,并且可能出現(xiàn)非線(xiàn)性成本趨勢(shì),例如燃料消耗;另一方面,確定所有現(xiàn)實(shí)的成本可能非常麻煩。因此,經(jīng)常使用面向時(shí)間的目標(biāo)。最小-和時(shí)間對(duì)應(yīng)于以效率為導(dǎo)向的標(biāo)準(zhǔn),可以用于最大限度地縮減總完工時(shí)間,也可以用于近似最小化成本。相比之下,最小-最大方法代表了一種公平標(biāo)準(zhǔn),旨在平衡旅行長(zhǎng)度,有助于提高客戶(hù)服務(wù)的質(zhì)量。

3.2.2 算法總結(jié)

算法可從精確式算法、啟發(fā)式算法和連續(xù)近似算法3大類(lèi)分別進(jìn)行討論。在車(chē)輛和無(wú)人機(jī)協(xié)同配送模式中,現(xiàn)有運(yùn)用的精確式算法主要包括動(dòng)態(tài)規(guī)劃法和基于剪枝操作加速求解的分支定界(branch and bound, B&B)、B&P和B&C算法。Dell’amico等[42]重新構(gòu)建了FSTSP模式的目標(biāo)函數(shù),提出了三下標(biāo)模型和二下標(biāo)模型,并通過(guò)一組有效不等式加速了B&C的求解。盡管在精確式算法中采取了加速操作,但仍只能解決規(guī)模比較小的問(wèn)題?；趩l(fā)式算法的算法又可以分為兩類(lèi):經(jīng)典啟發(fā)式算法和元啟發(fā)式算法。在使用經(jīng)典啟發(fā)式算法求解車(chē)輛和無(wú)人機(jī)協(xié)同配送問(wèn)題中,主要包括節(jié)約里程算法和掃描算法。經(jīng)典啟發(fā)式算法簡(jiǎn)單普適,一般用于規(guī)劃一個(gè)初始可行解,再結(jié)合元啟發(fā)式算法進(jìn)一步求解。元啟發(fā)式算法又可以分為單點(diǎn)元啟發(fā)式算法和多點(diǎn)元啟發(fā)式算法[43]。在關(guān)于車(chē)輛和無(wú)人機(jī)協(xié)同配送問(wèn)題的單點(diǎn)元啟發(fā)式算法中,主要使用了鄰域搜索算法、模擬退火算法、貪婪搜索算法。在關(guān)于車(chē)輛和無(wú)人機(jī)協(xié)同配送問(wèn)題的多點(diǎn)元啟發(fā)式算法中,主要使用了遺傳算法和人工蜂群算法。連續(xù)近似算法通過(guò)不斷逼近的近似方法來(lái)求解問(wèn)題。在求解車(chē)輛和無(wú)人機(jī)協(xié)同配送問(wèn)題的過(guò)程中,與精確式算法不同的是,求解時(shí)間在一個(gè)多項(xiàng)式時(shí)間內(nèi),與啟發(fā)式算法不同的是,需要用嚴(yán)格的數(shù)學(xué)證明解的質(zhì)量。相比于精確式算法和啟發(fā)式算法,連續(xù)近似算法在解決車(chē)輛和無(wú)人機(jī)協(xié)同配送問(wèn)題時(shí)面臨一定的挑戰(zhàn)。目前在一些數(shù)學(xué)規(guī)劃優(yōu)化器,如CPLEX、Gurobi中,已有通過(guò)運(yùn)用上述算法來(lái)求解無(wú)人機(jī)和車(chē)輛協(xié)同配送問(wèn)題的實(shí)例[44]。車(chē)輛和無(wú)人機(jī)協(xié)同配送模式中的算法歸納如圖9所示。

圖9 算法歸納圖Fig.9 Algorithm induction graph

首先,由于無(wú)人機(jī)和車(chē)輛協(xié)同配送的問(wèn)題較為復(fù)雜,屬于NP-hard問(wèn)題,可基于經(jīng)典啟發(fā)式、元啟發(fā)式和精確式算法相結(jié)合的思想進(jìn)行融合求解。林驛等[45]設(shè)計(jì)了一個(gè)基于最近鄰思想的由改進(jìn)節(jié)約里程算法與動(dòng)態(tài)規(guī)劃法構(gòu)成的兩階段啟發(fā)式算法,對(duì)時(shí)變網(wǎng)絡(luò)下帶時(shí)間窗的無(wú)人機(jī)-車(chē)輛路徑問(wèn)題進(jìn)行了求解。楊航[46]設(shè)計(jì)了嵌入改進(jìn)節(jié)約里程算法的人工蜂群算法,對(duì)單運(yùn)輸車(chē)輛搭載多無(wú)人機(jī)的配送模式進(jìn)行了求解。

其次,大多數(shù)文獻(xiàn)都采取多階段策略進(jìn)行求解。在對(duì)FSTSP類(lèi)問(wèn)題進(jìn)行求解時(shí),一般至少采取兩階段算法進(jìn)行求解:第一階段是將需求點(diǎn)劃分為車(chē)輛配送點(diǎn)和無(wú)人機(jī)配送點(diǎn),并尋找車(chē)輛的最短路徑;第二階段是在考慮無(wú)人機(jī)續(xù)航、載重等多約束情況下,得到無(wú)人機(jī)的任務(wù)分配,并尋找無(wú)人機(jī)的最短路徑。在對(duì)VGDTSP類(lèi)問(wèn)題進(jìn)行求解時(shí),一般采取三階段算法進(jìn)行求解:首先,以改進(jìn)的K-means聚類(lèi)算法進(jìn)行客戶(hù)分類(lèi),將聚類(lèi)中心設(shè)置為車(chē)輛?？奎c(diǎn);第二階段,以所有車(chē)輛?？奎c(diǎn)為研究對(duì)象,構(gòu)建車(chē)輛最優(yōu)初始行駛路線(xiàn);第三階段,結(jié)合無(wú)人機(jī)的任務(wù)分配,最終確定車(chē)輛和無(wú)人機(jī)配送路線(xiàn)。這種多階段算法類(lèi)似于路由算法中的分組分層思想,通常需要與動(dòng)態(tài)規(guī)劃算法相結(jié)合,以進(jìn)行調(diào)整。VGDTSP和FSTSP雖然都使用了多階段策略求解,但VGDTSP是基于先聚類(lèi)后路徑算法[47]的思想,而FSTSP是基于先路徑后聚類(lèi)算法[48]的思想。

3.3 參數(shù)討論

在基于無(wú)人機(jī)和車(chē)輛協(xié)同配送的文獻(xiàn)中,影響其目標(biāo)值的參數(shù)包括:無(wú)人機(jī)飛行速度、車(chē)輛行駛速度、車(chē)輛數(shù)量、無(wú)人機(jī)數(shù)量、需求點(diǎn)數(shù)量、無(wú)人機(jī)和車(chē)輛的承載能力、無(wú)人機(jī)的續(xù)航能力等。本節(jié)將這些參數(shù)進(jìn)行合并分析,得到對(duì)目標(biāo)值影響最大的3個(gè)參數(shù)。

3.3.1 無(wú)人機(jī)和車(chē)輛的相對(duì)速度

無(wú)人機(jī)和車(chē)輛的相對(duì)速度之比(the ratio of speed of drone and truck, RS-DT)會(huì)在很大程度上影響運(yùn)用模式,一般使用無(wú)人機(jī)的最大飛行速度和車(chē)輛的平均行駛速度進(jìn)行對(duì)比:

(6)

RS-DT值越大,無(wú)人機(jī)進(jìn)行交付的客戶(hù)數(shù)量越多,更傾向于使用VGDTSP模式。當(dāng)RS-DT值小于一定程度時(shí),PDSTSP和VGDTSP將不可取,因?yàn)榇藭r(shí)無(wú)人機(jī)的優(yōu)勢(shì)不存在;但無(wú)人機(jī)在FSTSP中仍然可行,只不過(guò)無(wú)人機(jī)在每次執(zhí)行任務(wù)時(shí)與客戶(hù)的數(shù)量關(guān)系更傾向于一對(duì)一,以避免車(chē)輛等待的時(shí)間過(guò)長(zhǎng)。其次,RS-DT值會(huì)影響車(chē)輛和無(wú)人機(jī)的數(shù)量關(guān)系,當(dāng)RS-DT值大到一定程度時(shí),MTSPD可以轉(zhuǎn)化為T(mén)SP-mD,而對(duì)目標(biāo)結(jié)果影響不大,這將大大節(jié)省車(chē)輛所帶來(lái)的成本。然而,RS-DT值并不是越大越好,因?yàn)楫?dāng)RS-DT值大到一定程度時(shí),將會(huì)使無(wú)人機(jī)等待時(shí)間過(guò)長(zhǎng),反而導(dǎo)致效率降低。正如文獻(xiàn)[19]結(jié)論所得:無(wú)人機(jī)與車(chē)輛協(xié)同使用的潛在收益(提高效率)與無(wú)人機(jī)和車(chē)輛之間相對(duì)速度的平方根相關(guān)。RS-DT的最優(yōu)值將會(huì)根據(jù)具體的無(wú)人機(jī)和車(chē)輛運(yùn)行模式和其他參數(shù)的不同而變化。

3.3.2 無(wú)人機(jī)數(shù)量和需求點(diǎn)數(shù)量

無(wú)人機(jī)數(shù)量會(huì)影響目標(biāo)值,特別是影響最小完成配送時(shí)間的目標(biāo)值。然而,無(wú)人機(jī)數(shù)量有上限,其上限受兩個(gè)因素影響。一是需求點(diǎn)數(shù)量,這個(gè)決定因素是全局性指標(biāo),由需求點(diǎn)數(shù)量決定的無(wú)人機(jī)數(shù)量上限代表即使再增加一架無(wú)人機(jī),也不會(huì)再優(yōu)化目標(biāo)值。但這不意味著需求點(diǎn)數(shù)量的增加一定會(huì)導(dǎo)致無(wú)人機(jī)數(shù)量上限的增大,這是因?yàn)闊o(wú)人機(jī)之間的協(xié)調(diào)將會(huì)使無(wú)人機(jī)數(shù)量上限具備一定的冗余,而且在高密度需求領(lǐng)域,無(wú)人機(jī)的使用和利用率會(huì)隨著無(wú)人機(jī)潛在服務(wù)客戶(hù)的增加而增加[49];二是車(chē)輛容量限制,這個(gè)決定因素是局部性指標(biāo),根據(jù)每輛車(chē)輛的長(zhǎng)寬高與載重,決定每輛車(chē)輛的無(wú)人機(jī)數(shù)量上限。要想確切分析由此因素決定的無(wú)人機(jī)的數(shù)量上限,還要考慮根據(jù)實(shí)際需求數(shù)量而裝載的物資,這將存在最優(yōu)化裝載問(wèn)題。

無(wú)人機(jī)數(shù)量和需求點(diǎn)數(shù)量還會(huì)影響算法的優(yōu)劣,部分算法只適用于小規(guī)模問(wèn)題的求解。當(dāng)需求點(diǎn)數(shù)量過(guò)多,基于小規(guī)模構(gòu)建的算法將無(wú)法得到較優(yōu)解;而當(dāng)無(wú)人機(jī)數(shù)量增加時(shí),每個(gè)無(wú)人機(jī)的任務(wù)分配將變得更加復(fù)雜,如何合理地使用并改進(jìn)相關(guān)算法,將會(huì)直接影響目標(biāo)值的好壞。

3.3.3 無(wú)人機(jī)續(xù)航能力

雖然在部分無(wú)人機(jī)和車(chē)輛協(xié)同配送模式中,假設(shè)無(wú)人機(jī)在執(zhí)行一次配送任務(wù)時(shí),只能前往一個(gè)客戶(hù),不考慮無(wú)人機(jī)續(xù)航能力,但當(dāng)研究更實(shí)際化時(shí)則不需要此假設(shè),如部分文獻(xiàn)中無(wú)人機(jī)執(zhí)行一次配送任務(wù)時(shí)能前往的客戶(hù)數(shù)量將由其續(xù)航能力決定。

Dorling等[50]和Byung[51]等針對(duì)無(wú)人機(jī)配送問(wèn)題(drone delivery problem, DDP),提出了無(wú)人機(jī)最大飛行時(shí)間與有效載荷近似呈線(xiàn)性關(guān)系,只不過(guò)后者的有效載荷考慮了電池和有效負(fù)載。兩者利用MILP解決了無(wú)人機(jī)最小成本或最短時(shí)間配送問(wèn)題。彭勇等[52]在Dorling基礎(chǔ)上考慮了最大飛行時(shí)間受載重影響的TSP-D問(wèn)題。

Liu等[53]為多旋翼無(wú)人駕駛飛機(jī)系統(tǒng)開(kāi)發(fā)的模型,廣泛用于包裹交付的飛機(jī)類(lèi)型——證明了功耗是無(wú)人機(jī)速度和有效載荷的函數(shù)。在較低的速度下,功耗隨著速度的增加幾乎保持不變(或略有降低),但是在更高的速度下,功耗隨著速度非線(xiàn)性地增加,即無(wú)人機(jī)功耗與飛行速度為非線(xiàn)性關(guān)系。Murray和Raj[54]基于Liu等開(kāi)發(fā)的無(wú)人機(jī)續(xù)航模型,研究了多飛行伙伴旅行商問(wèn)題(multi flying sidekick traveling salesman problem, mFSTSP)。然而,其文中的多功能飛行模擬器中的無(wú)人機(jī)速度是固定的,因此無(wú)法利用變速飛行節(jié)省時(shí)間。

Dukkanci等[36]最早提出無(wú)人機(jī)速度是決策變量,但其假設(shè)車(chē)輛在成本最小化的問(wèn)題中不進(jìn)行交付,只充當(dāng)無(wú)人機(jī)返回的移動(dòng)樞紐,即研究的模型基于VGDTSP。Murray和Raj[55]進(jìn)一步基于mFSTSP提出可變mFSTSP,將無(wú)人機(jī)速度作為決策變量,在速度和航程之間進(jìn)行權(quán)衡。其提供了一個(gè)三階段算法,以最小化總交付時(shí)間為目標(biāo),動(dòng)態(tài)調(diào)整無(wú)人機(jī)速度,以實(shí)現(xiàn)卓越性能。將無(wú)人機(jī)速度作為決策變量而不是參數(shù),并革新了此前文獻(xiàn)中的觀念——無(wú)人機(jī)需要以最大飛行速度執(zhí)行任務(wù)。之后,無(wú)人機(jī)執(zhí)行任務(wù)的飛行速度將可取最大航程速度vL-max(使得無(wú)人機(jī)航程最大時(shí)的速度)和最大飛行速度vmax之間的所有值,如圖10所示。無(wú)人機(jī)在飛行途中可根據(jù)實(shí)際情況在vL-max和vmax之間調(diào)節(jié)飛行速度,而小于vL-max的飛行速度由于不能帶來(lái)任何收益,可以不予以討論。

圖10 無(wú)人機(jī)航程和飛行速度、載重之間的關(guān)系Fig.10 Relationship between drone range, flight speed and load

3.4 約束條件討論

大部分文獻(xiàn)目前對(duì)無(wú)人機(jī)與車(chē)輛協(xié)同配送約束條件的研究仍停留在一些基本的物理約束,如無(wú)人機(jī)續(xù)航能力、無(wú)人機(jī)載重能力、車(chē)輛容量等因素。只有個(gè)別文獻(xiàn)研究了特殊的約束條件,如Jeong等[56]不僅考慮了有效載荷對(duì)能耗的影響,還考慮了存在禁飛區(qū)的約束情況;朱曉寧等[57]不僅考慮了無(wú)人機(jī)禁飛區(qū)的約束,還考慮了車(chē)輛限行的約束條件;Di和Guerriero[58]在MTSPD模型中引入了客戶(hù)時(shí)間窗約束,這也是目前唯一一篇在無(wú)人機(jī)和車(chē)輛協(xié)同配送問(wèn)題中引入時(shí)間窗約束的文獻(xiàn)。

實(shí)際上，無(wú)人機(jī)和車(chē)輛協(xié)同配送問(wèn)題中的約束條件可以基于車(chē)輛路徑規(guī)劃(vehicle route problem, VRP)和DDP問(wèn)題中的約束條件進(jìn)行歸納和拓展。一是基于裝載限制的VRP問(wèn)題中的約束,車(chē)輛的容量不僅要考慮物資的長(zhǎng)、寬、高[59]、還要考慮無(wú)人機(jī)的長(zhǎng)、寬、高,并設(shè)計(jì)好相對(duì)應(yīng)的無(wú)人機(jī)和物資存放空間。這方面約束可以基于裝箱問(wèn)題(bin packing problem,BPP)進(jìn)行深入研究,以增強(qiáng)貨物尺寸的有效裝載;二是基于動(dòng)態(tài)需求問(wèn)題中的約束,無(wú)人機(jī)每次執(zhí)行任務(wù)的路線(xiàn)將會(huì)根據(jù)客戶(hù)動(dòng)態(tài)性進(jìn)行調(diào)整,比如新增客戶(hù)訂單、配送地址變化和服務(wù)時(shí)間窗變化等情況;其次,交通、天氣等環(huán)境因素也會(huì)動(dòng)態(tài)性影響車(chē)輛或無(wú)人機(jī)的配送路線(xiàn)[60],特別是在戰(zhàn)場(chǎng)環(huán)境下,此約束尤為重要。針對(duì)這方面約束,需要采取一些預(yù)測(cè)方法和備用方式,以盡可能減小動(dòng)態(tài)因素所帶來(lái)的損失;三是在DDP問(wèn)題中,要結(jié)合三維航跡規(guī)劃中的約束,如無(wú)人機(jī)的爬升/俯沖角約束、最小轉(zhuǎn)彎半徑約束、飛行高度約束等[61]。這些約束要結(jié)合物資尺寸和重量、無(wú)人機(jī)續(xù)航能力和風(fēng)力等參數(shù)進(jìn)一步分析,比如當(dāng)物資重量增大時(shí),無(wú)人機(jī)爬升需要的動(dòng)力更大,則無(wú)人機(jī)最大爬升角會(huì)減小;當(dāng)風(fēng)作為阻力并且物資尺寸增大時(shí),無(wú)人機(jī)轉(zhuǎn)彎所需的向心力更大,則無(wú)人機(jī)最小轉(zhuǎn)彎半徑會(huì)增大。最后,根據(jù)叢書(shū)全等[62]和黃俊波[63]所闡述的無(wú)人機(jī)空氣動(dòng)力學(xué)原理,可知無(wú)人機(jī)重量會(huì)影響無(wú)人機(jī)飛行速度,當(dāng)配送無(wú)人機(jī)裝載物資時(shí),可轉(zhuǎn)化為配送無(wú)人機(jī)重量的增加。但目前關(guān)于無(wú)人機(jī)配送的文獻(xiàn)并沒(méi)有考慮這點(diǎn),這將導(dǎo)致實(shí)驗(yàn)結(jié)果與理論存在偏差。除此之外,本文認(rèn)為無(wú)人機(jī)有效載荷對(duì)無(wú)人機(jī)飛行速度的影響是呈非線(xiàn)性的,需要考慮動(dòng)力冗余情況。

當(dāng)無(wú)人機(jī)和車(chē)輛協(xié)同配送問(wèn)題考慮了上述較為全面的約束條件時(shí),該問(wèn)題變得更為復(fù)雜,特別是考慮到無(wú)人機(jī)航跡規(guī)劃時(shí)。目前,所有無(wú)人機(jī)和車(chē)輛協(xié)同配送模型和求解過(guò)程都沒(méi)有考慮無(wú)人機(jī)航跡規(guī)劃中的約束條件,未來(lái)這將是一個(gè)艱巨且必要的研究方向。針對(duì)多約束條件整合的復(fù)雜性,未來(lái)一個(gè)可行的方案是結(jié)合智能交通系統(tǒng)和人工智能技術(shù),在預(yù)測(cè)的基礎(chǔ)上進(jìn)行降維分析,以同時(shí)滿(mǎn)足各約束條件。

4 無(wú)人機(jī)和車(chē)輛協(xié)同配送映射模式的未來(lái)展望

未來(lái),要想在實(shí)際中運(yùn)用無(wú)人機(jī)和車(chē)輛協(xié)同配送,必須從實(shí)際的參數(shù)和約束條件出發(fā)進(jìn)行仿真分析。一是根據(jù)物資、車(chē)輛和無(wú)人機(jī)的實(shí)際物理大小、重量,判斷出無(wú)人機(jī)和車(chē)輛的映射模式;二是根據(jù)需求點(diǎn)分布范圍、車(chē)輛和無(wú)人機(jī)的實(shí)際續(xù)航里程,判斷出適合無(wú)人機(jī)和車(chē)輛配送的模式;三是要結(jié)合無(wú)人機(jī)和車(chē)輛協(xié)同配送的具體應(yīng)用場(chǎng)景,增加特殊的相關(guān)約束。

在滿(mǎn)足實(shí)際性能分析的基礎(chǔ)上,可以進(jìn)一步研究異構(gòu)無(wú)人機(jī)和車(chē)輛的協(xié)同配送映射模式。廣義的異構(gòu)無(wú)人機(jī)在《異構(gòu)多無(wú)人機(jī)》一書(shū)中介紹為由不同飛行平臺(tái)、搭載不同負(fù)載、具備不同信息處理能力的多種無(wú)人機(jī)[64]。異構(gòu)無(wú)人機(jī)目前大多停留于偵察、打擊、監(jiān)測(cè)領(lǐng)域的應(yīng)用,肖東[65]探討了異構(gòu)無(wú)人機(jī)用于打擊的自主任務(wù)規(guī)劃方法;嚴(yán)飛等[66]考慮了偵察和打擊混合異構(gòu)無(wú)人機(jī)的實(shí)時(shí)任務(wù)分配,提出了基于協(xié)同粒子群算法和協(xié)同函數(shù)、協(xié)同變量相結(jié)合的算法;田震等[67]則進(jìn)一步以異構(gòu)無(wú)人機(jī)對(duì)多目標(biāo)執(zhí)行偵查、打擊和評(píng)估任務(wù)為背景,綜合考慮異構(gòu)無(wú)人機(jī)任務(wù)執(zhí)行能力、任務(wù)執(zhí)行時(shí)序和自身運(yùn)動(dòng)學(xué)等約束。而在無(wú)人機(jī)和車(chē)輛協(xié)同配送問(wèn)題中,由于無(wú)人機(jī)只執(zhí)行配送任務(wù),所以本文將異構(gòu)無(wú)人機(jī)狹義地定義為具有不同載荷能力、不同續(xù)航能力、不同飛行速度的多種配送無(wú)人機(jī)。異構(gòu)無(wú)人機(jī)的優(yōu)化可以從兩個(gè)方面進(jìn)行探討:異構(gòu)車(chē)輛和需求點(diǎn)分布網(wǎng)絡(luò)。異構(gòu)車(chē)輛會(huì)影響異構(gòu)無(wú)人機(jī)的數(shù)量——車(chē)輛的容量會(huì)限制無(wú)人機(jī)的數(shù)量:一輛車(chē)輛在裝載完物資后可以容納2架規(guī)格較大的無(wú)人機(jī),4架規(guī)格較小的無(wú)人機(jī)(載荷能力小、續(xù)航能力弱)。當(dāng)允許混合使用異構(gòu)無(wú)人機(jī)時(shí),一輛車(chē)可以裝載2架規(guī)格較小的無(wú)人機(jī)和1架規(guī)格較大的無(wú)人機(jī)。使用異構(gòu)無(wú)人機(jī)后,可能會(huì)使得目標(biāo)值更優(yōu),這就取決于需求點(diǎn)分布網(wǎng)絡(luò)。當(dāng)需求點(diǎn)分布網(wǎng)絡(luò)較為分散時(shí),使用規(guī)格較小的無(wú)人機(jī)、在每次執(zhí)行任務(wù)時(shí)配送少量需求點(diǎn)的方案更優(yōu);當(dāng)需求點(diǎn)分布網(wǎng)絡(luò)較為密集時(shí),使用規(guī)格較大的無(wú)人機(jī)、在每次執(zhí)行任務(wù)時(shí)配送大量需求點(diǎn)的方案更優(yōu)。但是,一個(gè)需求點(diǎn)分布網(wǎng)絡(luò)從局部來(lái)看,其平均距離是不一樣的,平均距離小的局部網(wǎng)絡(luò)適用規(guī)格較大的無(wú)人機(jī),而平均距離大的局部網(wǎng)絡(luò)適用規(guī)格較小的無(wú)人機(jī)。異構(gòu)無(wú)人機(jī)的使用不僅能優(yōu)化目標(biāo)值,還能擴(kuò)大配送范圍,但重點(diǎn)是要平衡規(guī)格較大無(wú)人機(jī)的配送能力優(yōu)勢(shì)和規(guī)格較小無(wú)人機(jī)的數(shù)量?jī)?yōu)勢(shì)。

針對(duì)無(wú)人機(jī)和車(chē)輛協(xié)同配送研究所考慮的內(nèi)容極多,求解空間較大,不僅可以采取自上而下的集中式算法,還可以采取自下而上的分布式算法,以滿(mǎn)足求解空間劇增條件下的快速收斂?jī)?yōu)化[68]。比如,周晶等[69]設(shè)計(jì)了一個(gè)分布式高維多目標(biāo)演化優(yōu)化算法,以解決多無(wú)人機(jī)協(xié)同時(shí)的最優(yōu)任務(wù)分配。

5 結(jié)束語(yǔ)

本文首先總結(jié)了TSP-D下的4種無(wú)人機(jī)和車(chē)輛協(xié)同配送模式下的相關(guān)文獻(xiàn),并基于VGDTSP總結(jié)了TSP-mD和基于FSTSP總結(jié)了MTSPD的相關(guān)文獻(xiàn);其次,針對(duì)3種映射模式的相同變體和不同變體進(jìn)行了述評(píng),并總結(jié)了目前無(wú)人機(jī)和車(chē)輛協(xié)同配送模式中研究的目標(biāo)和算法,進(jìn)而討論了相關(guān)參數(shù)和約束條件;最后,針對(duì)目前無(wú)人機(jī)和車(chē)輛協(xié)同配送模式中的不足,提出對(duì)未來(lái)研究方向的展望。

在之后的無(wú)人機(jī)和車(chē)輛協(xié)同配送問(wèn)題中,首先應(yīng)確認(rèn)無(wú)人機(jī)和車(chē)輛的映射模式,然后基于映射模式分析配送問(wèn)題屬于多種組合模式還是單一模式,并確定配送問(wèn)題屬于何種配送模式,最終再確定是否存在變體形式;其次,目前無(wú)人機(jī)和車(chē)輛協(xié)同配送問(wèn)題中的求解算法較少,未來(lái)可嘗試使用多種改良算法進(jìn)行求解。改良算法最好能提前識(shí)別“不良”操作,例如某一決策將會(huì)導(dǎo)致無(wú)人機(jī)或車(chē)輛等待時(shí)間變長(zhǎng)。再次,多種參數(shù)值不能自由選擇,而應(yīng)該根據(jù)實(shí)際情況分析取值范圍,再根據(jù)可行范圍內(nèi)的值、多種約束條件和異構(gòu)無(wú)人機(jī)等信息確定參數(shù)的最優(yōu)值;最后,有必要基于無(wú)人機(jī)和車(chē)輛協(xié)同配送問(wèn)題中的實(shí)際性能分析,進(jìn)一步研究異構(gòu)無(wú)人機(jī)能夠帶來(lái)的收益。針對(duì)異構(gòu)無(wú)人機(jī)的優(yōu)化而研究需求點(diǎn)分布網(wǎng)絡(luò)時(shí),有必要深入分析網(wǎng)絡(luò)的拓?fù)湫再|(zhì)、層次結(jié)構(gòu)、節(jié)點(diǎn)重要性和相似性等網(wǎng)絡(luò)特征[70],以進(jìn)一步得到深層的潛在結(jié)論。