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

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

（山東科技大學(xué) 交通學(xué)院，山東 青島 266590）

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2.2 新型末端無人機(jī)物流配送模式

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

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

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

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

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

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

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

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

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

3.2 配送回路總數(shù)過多

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

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

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

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

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

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

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

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

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

圖1 “配送車+無人機(jī)”配送概念模型

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

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

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