無人機和車輛協同配送映射模式綜述與展望

劉正元, 王清華

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

0 引 言

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

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

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

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

1 TSP-D

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

1.1 FSTSP

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

圖1 FSTSP拓撲圖Fig.1 FSTSP topology

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

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

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

1.2 PDSTSP

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

圖2 PDSTSP拓撲圖Fig.2 PDSTSP topology

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

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

1.3 VGDTSP

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

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

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

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

圖3 VGDTSP拓撲圖Fig.3 VGDTSP topology

1.4 DGVTSP

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

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

2 TSP-mD和MTSPD

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

2.1 基于單一模式

2.1.1 基于FSTSP的MTSPD

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

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

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

2.1.2 基于VGDTSP的TSP-mD

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

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

2.2 基于多種組合模式

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

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

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

圖6 無人機由倉庫出發返回車輛的MTSPD運行模式Fig.6 MTSPD operating mode of drones from warehouse to the vehicles

圖7 無人機由倉庫出發返回倉庫的MTSPD運行模式Fig.7 MTSPD operating mode of drones from warehouse to warehouse

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

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

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

3 3種映射模式下的總結和討論

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

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

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

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

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

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

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

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

3.2 目標和算法總結

3.2.1 目標總結

無論是3種基礎配送模式還是3種映射模式,其目標函數主要研究3方面內容,但在不同映射模式的變體中存在差異,具體分析如下。

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

(1)

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

(2)

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

將式(1)擴展到MTSPD中時,最小總配送時間變為

(3)

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

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

(4)

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

(5)

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

3.2.2 算法總結

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

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

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

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

3.3 參數討論

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

3.3.1 無人機和車輛的相對速度

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

(6)

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

3.3.2 無人機數量和需求點數量

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

無人機數量和需求點數量還會影響算法的優劣,部分算法只適用于小規模問題的求解。當需求點數量過多,基于小規模構建的算法將無法得到較優解;而當無人機數量增加時,每個無人機的任務分配將變得更加復雜,如何合理地使用并改進相關算法,將會直接影響目標值的好壞。

3.3.3 無人機續航能力

雖然在部分無人機和車輛協同配送模式中,假設無人機在執行一次配送任務時,只能前往一個客戶,不考慮無人機續航能力,但當研究更實際化時則不需要此假設,如部分文獻中無人機執行一次配送任務時能前往的客戶數量將由其續航能力決定。

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

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

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

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

3.4 約束條件討論

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

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

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

4 無人機和車輛協同配送映射模式的未來展望

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

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

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

5 結束語

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

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