末端無人機物流路徑規劃研究綜述

劉亞京，呂文紅，王國娟，梁璐莉

（山東科技大學 交通學院，山東 青島 266590）

1 引言

近年來，隨著物流配送市場需求增大，配送成本升高，給物流配送業帶來了極大壓力。為滿足客戶對貨物運輸更高的要求，各大物流企業相繼開展相關研究，試圖用更經濟、高效的配送方案完成貨物運輸。無人機憑借自身方便、快捷的特點在物流配送領域占據了一席之地，各大物流企業紛紛加入無人機物流配送的競爭。“干線+支線+末端”三段式空運網是目前物流企業的理想服務場景。由于末端小型無人機本身載重能力、續航能力的限制和物流需求的多樣化，造成了整個運輸過程成本的增加。合理地規劃末端無人機物流配送路徑，制定無人機配送方案，對于提高無人機物流配送效率，降低物流企業成本具有非常重要的意義。

2 末端無人機物流路徑規劃研究現狀

2.1 無人機路徑規劃研究

目前，民用無人機路徑規劃的研究主要集中在智能避障功能的實現、路徑精確跟蹤以及多無人機協同路徑規劃三個方面。

2.1.1 智能避障。近年來，無人機在飛行過程中出現各種碰撞墜毀等事件，解決無人機自主避障問題已經迫在眉睫。馬躍濤[1]設計了一種磁感應裝置，以檢測帶電的障礙物，增強對未知環境的適應程度。辛守庭[2]設計的無人機系統能夠通過激光雷達獲取信息，將信息過濾后發送給無人機，無人機自動繞開障礙物。Allen[3]提出全堆棧動態實時運動框架，采用離線計算范式，依靠最優代價距離運動規劃和軌跡平滑實現飛行器的實時規劃。Yao等[4]針對無人機在復雜環境下躲避障礙物威脅問題，應用了智能集成診斷系統（Intelligent Integrated Diagnostic System,IIDS），較好地解決了局部極小值問題。Ma[5]和Mannar[6]利用單目視覺檢測算法，模擬人眼檢測，以確定障礙物位置。呂文紅等[7]在井下無人機航跡規劃中引入目標點策略，及時對航跡進行修正。張毅[8]提出一種基于雙旋Lyapunov 矢量場的無人機避障算法，建立了障礙物回避規則，該算法適用于未知環境下的無人機在線避障。上述研究表明：目前無人機智能避障研究主要集中在設計新型無人機避障系統、運用智能算法規劃無人機航跡兩個方面，以提高對障礙物距離估計的精度和計算效率，保證無人機作業的安全性和實效性。

2.1.2 路徑精確跟蹤。路徑跟蹤系統是無人機系統的重要組成部分，它決定了無人機是否能夠按照預設的軌道飛行。陳子昂等[9]提出一種基于曲率圓的無人機路徑跟蹤制導方法，使用幾何方法選擇虛擬跟蹤點，計算預設路徑與實際路徑之間最小誤差。王勛[10]提出一種基于虛擬力的無人機路徑跟蹤控制方法，利用虛擬力控制無人機，精確跟蹤直線、圓形、變曲率曲線路徑。趙述龍[11]采用側偏距積分法，克服了不同風力和風向對無人機帶來的干擾，使用高性能半實物仿真系統驗證了提出方法的抗風跟蹤性能。程歡[12]研究的四旋翼無人機采用雙環控制結構，外環（位置環）采用模型預測控制方法（Model Predictive Control,MPC）以實現位置跟蹤，內環（姿態環）采用PID 控制器以實現姿態跟蹤。楊 明[13]以部分可觀測馬爾科夫決策過程（Partially Observable Markov Decision Process,POMDP）為理論框架，建立起無人機路徑在線規劃模型，采用交互多模型（Interactive Multi-Model,IMM）方法描述無人機移動規律。李秋妮[14]針對多無人機目標軌跡追蹤問題設計了目標追蹤自適應控制指令，解決了速度與航向角通道系數未知所造成的設計困難，達到了非常好的追蹤效果。上述研究的模型實現了對無人機路徑的精確跟蹤，提高了無人機執行任務的效率。

2.1.3 多無人機協同路徑規劃。在協同搜索背景下，多架無人機同時從同一個基地出發搜索附近的可疑目標以盡快完成搜索任務。多無人機協同路徑規劃可以有效提高無人機搜索、偵查等任務效率。李松[15]提出問題轉換策略，將多無人機搜索問題轉換為車輛路徑問題，指導多架無人機對目標區域進行協同覆蓋搜索。劉文兵[16]采用一種聚類算法和遺傳算法進行分布組合的優化算法，建立多旅行商問題（Multiple Traveling Salesman Problem,MTSP）模型。宋雪倩[17]利用基于Dubins路徑的A*算法的多無人機協同路徑規劃方法，保證了路徑的光滑和無人機飛行的安全。劉暢等[18]針對多目標群多基地多無人機協同任務規劃問題提出了一種周期性快速搜索遺傳算法，構建了多無人機協同偵察任務規劃決策數學模型。上述研究的模型和算法提高了多無人機任務執行的效率和精確度。

2.2 末端無人機物流路徑規劃研究

相對于一般民用無人機路徑規劃，末端無人機物流路徑規劃在研究中加入了時間窗限制，能夠更加精確地安排無人機配送路線；解決資源限制問題，采用新型燃油發電機、新型燃料氫等延長續航里程。另外，提高末端無人機物流配送效率除了考慮更多的影響因素之外，還可以采用其他的方式：物流配送中心選址和物流路徑共同優化的方式，建立“配送車+無人機”的新型末端配送模式。

2.2.1 末端無人機物流路徑規劃約束要素

（1）時間窗限制。受時間窗限制的物流路徑問題是指送貨的車輛組織合適的行車路線，在滿足客戶需求的同時，盡可能達到路程最短、時間最少等。由于受顧客最早開始服務時間和最后服務時間的限制，末端無人機物流路徑規劃除考慮空間方面外，還需要合理安排時間。

末端物流路徑規劃的時間窗限制應該考慮三種：軟時間窗、硬時間窗、混合時間窗。儀孝展[19]采用遺傳模擬退火算法求解了帶時間窗限制的路徑問題，保證物流配送車輛滿足行駛距離和車身容量限制的同時，在規定時間段內將貨物配送到客戶節點，否則接受相應費用懲罰。劉瀾[20]在研究路徑問題時，充分考慮了軟時間窗對配送業務的影響，將時間懲罰成本作為優化目標之一，并與VRP結合，提出了帶軟時間窗的車輛路徑問題（Vehicle Routing Problem with Soft Time windows,VRPSTW）。侯同娟[21]在乳制品冷鏈物流配送選址與路徑優化問題研究中加入了軟時間窗限制，允許物流配送中出現延時情況，提高了物流整體服務質量。史昊[22]結合醫藥配送中客戶對收貨時間區間要求嚴格程度不同，提出軟硬時間窗共存的配送路徑優化問題，并對無時間窗、單一時間窗與軟硬時間窗共存三種情況進行求解比較。研究表明：最優成本、路徑數大致與時間窗要求的嚴格程度成正比。

（2）續航里程限制。傳統鋰電池無人機受電池容量的限制，續航里程較短，尤其在搭載重物的情況下，飛行時間一般不超過30min。中通快遞為應對偏遠地區配送問題，研發出第一代末端無人機物流配送系統—普羅米修斯1600A 油電混合物流無人機，創新采用燃油發電機對無人機進行供電，既保留了電動無人機的穩定、安全，同時又提供滿載最長1.5h的續航時間[23]。韓國液態氫專家MetaVista 配合智能能源燃料電池動力模塊，創造了無人機試飛達10小時50分鐘的新記錄[24]。燃料氫電池比普通的電池續航能力更長，液態氫及其儲存罐重量非常的小，不會為無人機帶來很大負擔。解決末端無人機的續航里程限制，延長續航時間，充分利用無人機進行末端配送，能夠降低整個運輸過程的成本。

2.2.2 新型末端無人機物流配送模式

（1）“配送中心+配送路徑”共同優化的模式。石梓涵[25]在無人機物流路徑規劃研究中采用重心法對物流站點進行設計的同時應用遺傳算法設計最優路徑，選擇合適的配送中心位置和最優的無人機配送路徑，降低了物流成本。

配送中心是整個物流網絡優化節點的核心，在末端無人機物流路徑優化過程中，需要將上級配送中心位置的選擇和路徑優化問題綜合考慮。馬帥[26]研究的物流配送中心選址及路徑協同優化問題（Location-Routing Problem,LRP），既滿足了配送中心的最優數量和容量，又可以確定配送車輛的最優路徑，是LAP 問題和VRP 問題的集成。侯同娟[21]構建了乳制品冷鏈物流配送選址—路徑優化問題的雙層規劃模型，上層確定最佳配送中心選址,下層確定最優配送路徑，使乳制品冷鏈物流達到整體系統最優。劉聰[27]針對O2O藥品配送選址—路徑問題，設計了雙層的遺傳—蟻群求解算法，采用Halton 序列和記憶庫操作對上層遺傳算法進行改進。

（2）“配送車+無人機”末端配送模式。針對無人機和貨車的最優路由調度問題，國內外一些研究提出了一種新型物流配送模式，在末端無人機物流配送中引入經典車輛路徑問題，無人機和配送車合作的形式配送，有效釋放人力，同時彌補無人機單獨配送在耐力方面的缺陷。

Chase C.Murray[28]將傳統旅行推銷員問題轉變為“飛行伙伴旅行推銷員問題”（Flight Partner Traveling Salesman Problem ,FPTSP），運用整數線性規劃方法解決無人機與貨車協同工作時的最佳客戶分配問題。梅賽德斯·奔馳[29]宣布了一款“無人機配送車”概念車—Vision Van，其貨艙中不僅擁有自動化的貨架和貨箱，車頂還帶有兩架無人機設備，以提升配送效率。UPS[30]在實踐中實現了這一概念，已經宣布通過修改其傳統的配送卡車，使其實現與無人機交互，成功測試了無人機與卡車的協同配送。Ferrandez[31]等人研究了卡車和無人機協同交付系統中的時間效率和能量效率，考慮將一輛貨車攜帶多架無人機，無人機分別從卡車上發射進行訪問，并在訪問完成后返回卡車。周浪[32]在研究農村電商配送時，采用“配送車+無人機”模式，充分發揮配送車載重量大和無人機配送速度快的優勢。研究表明：采用“無人機+配送車”的方式進行末端配送，能夠減少車輛投入和車輛運行距離，延長無人機配送效率，提高末端物流配送的效率。

3 末端無人機物流路徑規劃存在的問題

3.1 末端無人機物流配送續航里程較短

目前市場上的無人機主要采用鋰聚合物電池，續航能力一般在20—30min之間，充電時間超過一個小時，限制了無人機的飛行時間和飛行距離[33]。當電池能量不足時，無人機很難完成飛行，如果沒有及時進行能量補給，無人機可能會在中途墜毀。小米無人機在正式發布的當晚直播試飛，直播途中突然搖晃下墜，最終炸機墜落，小米官方解釋是電量不足，無人機自動返航[34]。

目前以太陽能作為能量驅動的無人機開始應用，但此類無人機不能全天候進行配送。同時，太陽能電池本身自重較大，很難再裝載大批量的配送貨物。

末端無人機物流的路徑規劃主要是合理規劃無人機的配送路徑，用最少的耗時，最少的耗能，最少的路程來實現節約物流成本的目的。若末端小型無人機的續航里程能夠延長，則單次飛行配送的貨物會更多，節省回飛充電的時間和路程，降低路徑規劃的難度，節約配送成本。

3.2 配送回路總數過多

目前，國內外應用于配送的無人機載重一般在15kg 以下[35]。無人機每次攜帶一定重量的任務從配送中心飛出，由于攜帶任務重量不同，難以進行合理搭配，導致無人機非滿載配送，同一批待配送的貨物下無人機的回路總數增加，加大了運輸成本投入，延長了貨物配送時間。如果能夠合理裝載貨物，充分利用無人機配載容積，提高無人機的利用率，再根據任務目的地進行路徑規劃，合理安排配送路線，對提高配送效率，降低物流成本具有非常重要的意義。

3.3 地面倉庫加大了路徑規劃的難度

物流配送中心相當于一個臨時倉庫，客戶所需要的貨物在此周轉，再進行配送，具有集成化、規范化、現代化的特點。目前國內外在研究末端無人機物流路徑規劃時，都以地面倉庫作為無人機配送中心。末端小型無人機在完成一次配送之前必須進行垂直上升、水平飛行、垂直下降運動，這樣在進行路徑規劃時必須考慮無人機攜帶貨物起飛的耗能，加大了末端無人機物流路徑規劃的難度。如果在規劃時忽略垂直起飛的耗能，則實際飛行中，無人機可能會因能量不足而中途墜落，不能按照預設軌跡飛行。如果能夠建立一個空中配送中心，無人機攜帶貨物直接從配送中心進行水平飛行，在末端無人機物流路徑規劃時將不用考慮垂直方向起飛的能耗問題，降低末端無人機物流路徑規劃的難度。

4 末端無人機物流路徑規劃發展趨勢

4.1 基于智能算法的無人機物流路徑規劃

末端無人機物流配送路線需要依靠智能算法計算總體飛行路徑，不同環境條件下的路徑規劃算法也有所不同。將全局算法和虛擬力場法結合、環境建模技術與路徑規劃算法相結合能夠設計出適用于特殊環境的無人機物流配送路徑。

運用全局算法中的A*算法，在出發點和到達點之間設計一條預設路徑，同時采用虛擬力場法進行避障，走出障礙區域之后，再按照預設路徑飛行。環境建模技術中的柵格法和蟻群算法結合，柵格法模擬三維無人機飛行空間，模擬蟻群進行試驗，將模擬蟻群走的路線應用到實際環境中。以上兩種混合算法的應用，能夠節省末端無人機物流配送的成本，降低危險系數，具有非常高的實用性。

4.2 滿足續航里程約束的基礎上進行路徑規劃

4.2.1 配送車攜帶充電樁場景下的路徑規劃。目前在無人機物流配送中，“配送車+無人機”模式的應用越來越多，無人機從配送車上發射，向客戶配送貨物，完成任務后自動返回貨車，進行下一項任務，如圖1。2018年深圳科衛泰研制了一款車載無人機倉庫系統，能夠在移動環境中，輔助無人機精準起降，并根據要求實現充電換電功能。配送車攜帶無人機和若干貨物從配送中心出發，按照預設路徑配送，到達站點1 之后，無人機出發完成站點2 的配送任務，配送車繼續行駛,完成站點3 的配送任務，最后無人機在站點3 處回到配送車，落入配送車載倉庫平臺，此時，無人機可以進行無線充電，配送車攜帶無人機繼續行駛，當無人機有配送任務時，繼續完成任務，如此循環，直至完成整個配送過程。

圖1 “配送車+無人機”配送概念模型

4.2.2 地面巡邏式移動充電站場景下的路徑規劃。美國允許在邊遠地區銷售移動汽油[36]，根據這一模式，無人機物流公司可以推出移動式充電站。充電站的便利性對無人機物流的應用有很大影響，“巡邏式移動充電站”具有高度靈活性，滿足無人機充電需求。開展無人機配送的公司在配送區域內放置若干臺移動充電站，構成一個移動充電網絡，每臺充電站有固定路線，兩次經過某一地點的時間間隔固定，方便無人機搜索充電。移動充電站上方設有無線充電平臺，當配送無人機自身電量低于某值時，根據系統信息就近尋找移動充電樁充電，充電完成后，繼續進行下一項配送任務。當移動充電站自身電量不足20%時，按照預先設置的路線返回倉庫充電，充電完成后繼續進行巡邏任務。

4.2.3 建立無線充電信號基站場景下的路徑規劃。華為在2017年提出了“創新城市”[37]這一概念，支持無線充電的信號基站。發展無人機物流的公司和移動公司合作，利用現有信號塔為無人機無線充電，實現不同企業間的互利共贏。建立無線充電信號基站后，進行無人機物流路徑規劃時，將充電基站作為固定的客戶，每一條配送路徑中，必須保證有一個充電基站，在此基礎上實現路徑最優。無人機每次飛行攜帶若干個任務，在幾個任務之間安排無人機飛往充電基站進行充電，設定充電停留的時長，充電結束后繼續飛行，完成剩下的任務。這種方法將充電作為一個任務，放入整體中一起規劃，相比配送車攜帶移動充電樁這種場景，無人機不再進行搜索，尋找充電位置，降低了系統的復雜程度，達到無人機物流配送要求。

今后末端無人機物流路徑規劃研究應該在保證續航里程基礎上進行，能夠降低路徑規劃難度，避免無人機因續航里程不足而墜毀，提高無人機物流的安全性，降低整個運輸過程的成本。