無人機(jī)和車輛協(xié)同配送映射模式綜述與展望

劉正元, 王清華

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

0 引 言

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

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

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

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

1 TSP-D

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

1.1 FSTSP

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

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

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

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

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

1.2 PDSTSP

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

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

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

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

1.3 VGDTSP

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

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

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

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

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

1.4 DGVTSP

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

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

2 TSP-mD和MTSPD

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

2.1 基于單一模式

2.1.1 基于FSTSP的MTSPD

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

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

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

2.1.2 基于VGDTSP的TSP-mD

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

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

2.2 基于多種組合模式

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

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

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

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

圖7 無人機(jī)由倉庫出發(fā)返回倉庫的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能減少配送時間。文獻(xiàn)[35]在求解中開發(fā)了一種新的啟發(fā)式算法,稱為自適應(yīng)插入啟發(fā)式算法(adaptive insertion heuristics, ADI)，來解決MTSPD。啟發(fā)式方法由兩個階段組成:構(gòu)建多旅行商解決方案和對初始多旅行商解決方案應(yīng)用移除和插入操作符來構(gòu)建MTSPD解決方案。在ADI中涉及3種多旅行商啟發(fā)式算法:遺傳算法、組合K均值/最近鄰法和隨機(jī)聚類/旅行法。在Dukkanci等[36]研究的無人機(jī)和車輛協(xié)同配送中,建立了PDSTSP和VGDTSP組合模式,但其已確定了車輛的路線,如圖8所示。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

(2)

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

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

(3)

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

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

(4)

當(dāng)無人機(jī)不被允許從需求點返回倉庫時,此時最小完成配送時間為車輛到達(dá)倉庫的時間,即

(5)

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

3.2.2 算法總結(jié)

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

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

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

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

3.3 參數(shù)討論

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

3.3.1 無人機(jī)和車輛的相對速度

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

(6)

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

3.3.2 無人機(jī)數(shù)量和需求點數(shù)量

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

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

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

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

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

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

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

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

3.4 約束條件討論

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

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

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

4 無人機(jī)和車輛協(xié)同配送映射模式的未來展望

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

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

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

5 結(jié)束語

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

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