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

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

1 引言

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

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

2.1 無人機路徑規(guī)劃研究

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

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

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

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

2.2 末端無人機物流路徑規(guī)劃研究

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 配送回路總數過多

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

3.3 地面?zhèn)}庫加大了路徑規(guī)劃的難度

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

4 末端無人機物流路徑規(guī)劃發(fā)展趨勢

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

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

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

4.2 滿足續(xù)航里程約束的基礎上進行路徑規(guī)劃

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

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

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

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

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