基于配送模式的無人機(jī)城市配送路徑規(guī)劃

任新惠， 武 彤

(中國民航大學(xué)經(jīng)濟(jì)與管理學(xué)院， 天津 300300)

過去的十年中，無人機(jī)(unmanned aerial vehicle, UAV)在軍事活動、公共安全、即時配送、環(huán)境監(jiān)測等多個領(lǐng)域逐漸興起。預(yù)計到2022年，全球?qū)⒂袃r值150億美元的無人機(jī)市場，到2040年，空中的物流市場將達(dá)到1.5萬億美元。尤其是在物流配送領(lǐng)域，無人機(jī)配送的優(yōu)勢逐漸凸顯。早在2013年亞馬遜推出“Amazon Prime Air”項(xiàng)目,該項(xiàng)目的最終目標(biāo)是在30 min內(nèi)配送5磅的包裹，2016年首飛成功。2017年，谷歌旗下的子公司W(wǎng)ing推出“羽翼項(xiàng)目”，該公司在試點(diǎn)區(qū)進(jìn)行試飛，并于2019年底在芬蘭開始運(yùn)行。中國無人機(jī)配送起步較晚。2019年，億航開通了其首個無人機(jī)配送航線，將配送時間從原來的40 min縮短至8 min。2018年，訊蟻開始用無人機(jī)在園區(qū)內(nèi)進(jìn)行配送，一年內(nèi)用無人機(jī)累計配送約10 000杯咖啡。因無人機(jī)運(yùn)送檢驗(yàn)樣本、醫(yī)療物資方面有時效快和易消毒的優(yōu)點(diǎn)，2020年1月28日起，迅蟻開始在余杭區(qū)定點(diǎn)醫(yī)院、余杭區(qū)疾控中心等地用無人機(jī)運(yùn)送醫(yī)療物品的計劃配送檢驗(yàn)檢疫醫(yī)療物資，尤其在疫情期間發(fā)揮重要作用。

無人機(jī)配送在農(nóng)村地區(qū)、城市如廣州、杭州等地區(qū)開始運(yùn)行，相比于單一的車輛模式配送方式，加入無人機(jī)后的配送模式優(yōu)勢逐漸凸顯，如無人機(jī)與參與配送的車輛組合配送模式、無人機(jī)與不參與配送的車輛組合模式、無人機(jī)單獨(dú)即時配送等模式。城市物流配送中，無人機(jī)不受地面復(fù)雜條件限制，避免了地面配送中存在的擁堵、交通管制、及車輛配送引發(fā)的安全等問題。無人機(jī)的配送速度也高于傳統(tǒng)車輛，并且部分配送路線為點(diǎn)對點(diǎn)模式，距離短，大幅減少了配送能耗與時長。其次，大多無人機(jī)動力能源為電力，配送成本低且機(jī)動性強(qiáng)，提高了配送的效率減少了人力的成本[1-2]。在最后一公里配送中，無人機(jī)通常也會與地面車輛的組合提高配送效率[3]。隨著無人機(jī)在物流業(yè)的興起，“最后一公里”配送問題逐漸成為研究的熱點(diǎn)，無人機(jī)末端配送模式與路徑優(yōu)化成為研究重點(diǎn)，但無人機(jī)運(yùn)載能力有限，續(xù)航時間較短，且城市運(yùn)行環(huán)境復(fù)雜，能耗以及其他外部因素成為影響路徑規(guī)劃的重要內(nèi)容，不同配送模式下的路徑規(guī)劃也不盡相同。

為此，基于無人機(jī)配送模式，主要包含車輛和無人機(jī)協(xié)作運(yùn)行與無人機(jī)單獨(dú)交付兩種模式(其中卡車和無人機(jī)協(xié)作運(yùn)行又可分為卡車參與配送與不參與配送兩類)，研究在城市運(yùn)營環(huán)境下無人機(jī)配送影響因素，重點(diǎn)分析在不同模式下，考慮多種因素的路徑規(guī)劃問題及求解方法，最后展望未來無人機(jī)配送路徑規(guī)劃中還需進(jìn)一步考慮的影響因素。

1 無人機(jī)配送模式

目前對無人機(jī)配送模式的研究逐漸增多，不同配送模式下路徑規(guī)劃需要考慮的因素也不同。當(dāng)無人機(jī)單獨(dú)交付時對路徑規(guī)劃的影響主要包括無人機(jī)能耗因素、禁區(qū)或障礙物等導(dǎo)致無人機(jī)繞飛因素以及不確定的環(huán)境因素對無人機(jī)飛行路線的影響。當(dāng)無人機(jī)與車輛協(xié)作運(yùn)行時，除了要考慮對無人機(jī)本身的影響的因素，還應(yīng)考慮無人機(jī)與車輛的接駁問題。其次不同的配送模式的路徑規(guī)劃也不同，無人機(jī)單獨(dú)交付只需規(guī)劃無人機(jī)飛行路徑，當(dāng)與車輛協(xié)作時，同時還需考慮車輛的行進(jìn)路線?？紤]到無人機(jī)的飛行距離、飛行時間有限，并且攜帶包裹數(shù)量與重量也有限，故大多研究將無人機(jī)與車輛相結(jié)合，擴(kuò)大配送范圍，提高配送效率。任新惠等[4]重點(diǎn)研究了無人機(jī)與卡車組合模式、無人機(jī)與無人柜組合模式、無人機(jī)與無人倉組合模式。任新惠等[5]根據(jù)無人機(jī)與車輛組合時的角色將配送模式分為車輛支持無人機(jī)、無人機(jī)支持車輛、無人機(jī)車輛同步運(yùn)行和無人機(jī)和車輛獨(dú)立運(yùn)行4類。任璇等[6]將配送模式分為車輛與無人機(jī)協(xié)同配送、車輛與無人機(jī)并行配送、車輛支持無人機(jī)配送、無人機(jī)支持車輛配送,以及混合模式配送5類。

根據(jù)無人機(jī)是否與車輛組合將無人機(jī)配送模式分為無人機(jī)獨(dú)立運(yùn)行模式和無人機(jī)與車輛協(xié)同模式。其中無人機(jī)與車輛協(xié)同模式又包括一輛車與一架或多架無人機(jī)的運(yùn)行模式、多輛車與多架無人機(jī)的運(yùn)行模式，同時無人機(jī)與車輛協(xié)同模式又分為車輛參與配送與不參與配送兩種情況，如圖1所示。

圖1 無人機(jī)配送模式分類Fig.1 Classification of UAV delivery modes

1.1 無人機(jī)與車輛協(xié)同運(yùn)行

1.1.1 車輛參與配送

Sergio等[7]提出了將卡車與無人機(jī)串聯(lián)，使用一輛卡車與一架無人機(jī)協(xié)作同時配送，建立了無人機(jī)旅行商模型，規(guī)定無人機(jī)只能從卡車上發(fā)射交付貨物后再返回卡車。從時間與能量的角度進(jìn)行分析，發(fā)現(xiàn)將無人機(jī)從卡車上發(fā)射可以減小總交付時間。通過找到卡車?？康淖罴汛螖?shù)和位置，實(shí)現(xiàn)了最短的交付時間。Murray等[8]提出了無人機(jī)旅行商模式的兩個變種模式，分別是飛行助手旅行商模式(flying sidekick traveling salesman problem，F(xiàn)STSP)和并行無人機(jī)調(diào)度旅行商模式(the parallel drone scheduling traveling salesman problem, PDSTSP)。兩種模式都是一輛卡車和一架無人機(jī)協(xié)作配合為多個客戶提供服務(wù)，目標(biāo)是減小卡車和無人機(jī)從倉庫出發(fā)到配送完畢所有包裹返回倉庫的時間。其中無人機(jī)只能攜帶一個包裹為一位顧客服務(wù)，并且較重的包裹只能由卡車配送，卡車可以為多個顧客服務(wù)。飛行助手旅行商模式中卡車與無人機(jī)協(xié)作，并行的無人機(jī)調(diào)度旅行商模式中卡車與無人機(jī)相互獨(dú)立，兩種配送模式示意圖如圖2[8]所示。

圖2 無人機(jī)與車輛協(xié)作模式[8]Fig.2 UAV and vehicle cooperation mode[8]

基于FSTSP配送模式，為減少總配送時間或成本，Salama等[9]提出了在客戶集群中某個客戶點(diǎn)位置或非客戶點(diǎn)位置設(shè)置焦點(diǎn)，車在焦點(diǎn)?？堪l(fā)射無人機(jī)，而不是規(guī)定焦點(diǎn)只能設(shè)置于客戶所在位置。通過計算發(fā)現(xiàn)，取消焦點(diǎn)位置限制后成本與交付完成時間大幅減少。Moshref-Javadi等[10]則是規(guī)定可以車?？课恢冒l(fā)射多架無人機(jī)且配送完畢后車不必等待無人機(jī)返回，在下一交付站與其會和。相反Moshref-Javadi等[11]規(guī)定待無人機(jī)返回，車才可為下一位顧客配送，但其通過在卡車?？奎c(diǎn)多次發(fā)射同一無人機(jī)為多個客戶提供服務(wù)減少總配送時間。Wang等[12]提出了并行的無人機(jī)調(diào)度旅行商模式的變體，將客戶分為只能由卡車配送、只能由無人機(jī)配送。彭勇等[13]則添加了卡車和無人機(jī)或卡車都能配送的第三類客戶，目標(biāo)為最小化無人機(jī)與車輛的總服務(wù)時間。韓明等[14]在飛行助手旅行商模式的基礎(chǔ)上加入了受限地區(qū)這一概念，綜合考慮了車輛與無人機(jī)本身的特點(diǎn)，將車與無人機(jī)的運(yùn)送分為三種模式：一是無人機(jī)與車輛同時啟用；二是在受限地區(qū)，車輛無法配送，這時啟動無人機(jī)配送；三是在道路情況良好的地區(qū)不啟動無人機(jī)只用車輛進(jìn)行運(yùn)送，提高了復(fù)雜地形區(qū)域的配送效率。為了擴(kuò)大無人機(jī)的飛行范圍，Coelho等[15]、Yadav等[16]和Kim等[17]提出了無人機(jī)站-商旅模型。在某一客戶群周圍設(shè)立無人機(jī)站，假設(shè)無人機(jī)站可以存儲無人機(jī)并且可以為無人機(jī)充電。當(dāng)卡車將該無人機(jī)站附近客戶的包裹運(yùn)送到站點(diǎn)，此時該無人機(jī)站被激活，“存儲”在站點(diǎn)的無人機(jī)開始派送包裹，卡車也派送其需要派送的包裹。無人機(jī)完成任務(wù)返回后可以在該站充電，目標(biāo)是最小化車與無人機(jī)的總交付時間。Murray等[18]提出了無人機(jī)旅行商模式的變體?？蛻舭梢酝ㄟ^多架不同種類的無人機(jī)和一輛卡車進(jìn)行配送，卡車也是移動倉庫和無人機(jī)的充電站。

當(dāng)服務(wù)客戶數(shù)量大時，一輛卡車與多架無人機(jī)已滿足不了客戶需求，這時問題則變成了多輛交通工具以及運(yùn)輸工具的服務(wù)順序兩個問題的求解。文獻(xiàn)[12,19-22]提出此類問題涉及多輛卡車與多架無人機(jī),無人機(jī)可以從卡車上發(fā)射為顧客派送包裹也可以由卡車直接運(yùn)送，并提出了兩級交付系統(tǒng)：第一級交付系統(tǒng)是卡車配送系統(tǒng)，第二級則是無人機(jī)配送系統(tǒng)，其目標(biāo)是最小化卡車與無人機(jī)從出倉庫到回倉庫時間。服務(wù)模式示意圖如圖3所示。

圖3 多卡車多無人機(jī)配送模式Fig.3 Multi-truck and multi-UAV distribution mode

經(jīng)驗(yàn)證，同時使用卡車和無人機(jī)比單獨(dú)使用卡車或無人機(jī)派送更加節(jié)省時間。

1.1.2 車輛不參與配送

車輛不參與配送是之前3種問題的組合。在這類問題中，卡車只負(fù)責(zé)運(yùn)載包裹和作為無人機(jī)的移動充電站和倉庫，只有無人機(jī)負(fù)責(zé)配送。服務(wù)模式示意圖如圖4所示。

圖4 單車輛多無人機(jī)協(xié)作，車輛不參與配送模式Fig.4 Single vehicle multi-UAV cooperation, vehicles do not participate in the distribution mode

車輛不參與配送模式又可分為單車與單機(jī)組合[23-28]、單車與多機(jī)組合[29-31]以及多車與多機(jī)組合[32-33]。此類問題規(guī)定卡車只能在街道上運(yùn)行，到達(dá)指定的?？奎c(diǎn)后停車釋放無人機(jī)，卡車可以充當(dāng)無人機(jī)的“母艦”，主要負(fù)責(zé)運(yùn)載包裹和無人機(jī)以及為無人機(jī)充電，無人機(jī)則是負(fù)責(zé)派送包裹，無人機(jī)負(fù)責(zé)的客服不能超過其飛行范圍與運(yùn)載能力。派送完畢后到達(dá)卡車停靠點(diǎn)與卡車匯合。通過算例分析，不論是時間還是成本，無人機(jī)卡車協(xié)作模式結(jié)果優(yōu)于傳統(tǒng)的單卡車配送模式。

1.2 無人機(jī)獨(dú)立運(yùn)行

不同于無人機(jī)與卡車協(xié)同運(yùn)行，無人機(jī)獨(dú)立運(yùn)行時，面臨著配送包裹量、飛行距離和時間有限等問題，所以此類問題多會考慮無人機(jī)電池容量、能量消耗、轉(zhuǎn)換率及其飛行范圍等。Dorling等[34]規(guī)定多個無人機(jī)在其飛行范圍內(nèi)同時配送包裹，每架無人機(jī)從倉庫出發(fā)，可以攜帶多個包裹，而后在其飛行路線上為多個客戶服務(wù)。服務(wù)完畢后返回倉庫充電，充電完畢繼續(xù)配送。目標(biāo)是最小化總成本或總配送時間。Kim等[17]提出了相同的運(yùn)行模式，但其目標(biāo)是最小化無人機(jī)使用數(shù)量，為了實(shí)現(xiàn)該目標(biāo)同時覆蓋所有客戶，最終從5個候選倉庫位置選出2個，該運(yùn)行模式適合小范圍多用戶地區(qū)。為了擴(kuò)大配送范圍，Liu[35]提出了設(shè)立無人機(jī)充電站，當(dāng)無人機(jī)的電池電量低于閾值時，其必須到最近的充電站更換電池或充電，充電站資源充足，最終目標(biāo)是配送延誤時間最短。Wu等[36]則認(rèn)為在實(shí)際運(yùn)行中充電樁數(shù)量有限，需要合理的時刻調(diào)度表，設(shè)計良好的調(diào)度策略，在滿足用戶服務(wù)需求的同時，滿足無人機(jī)充電需求。

2 無人機(jī)城市配送路徑規(guī)劃影響因素

不論是無人機(jī)獨(dú)立運(yùn)行還是無人機(jī)與車輛協(xié)作運(yùn)行，城市配送都存在較多影響因素，包括外部因素與內(nèi)部因素，外部因素包括不確定的天氣狀況、人為因素、繞飛因素等，內(nèi)部因素包括無人機(jī)電池電量、有效載荷、能耗等因素。不同的配送模式需要考慮的因素也不盡相同。當(dāng)無人機(jī)單獨(dú)交付時對路徑規(guī)劃的影響主要包括無人機(jī)能耗因素、禁區(qū)或障礙物等導(dǎo)致無人機(jī)繞飛因素以及不確定的環(huán)境因素對無人機(jī)飛行路線的影響。當(dāng)無人機(jī)與車輛協(xié)作運(yùn)行時，除了要考慮對無人機(jī)本身有影響的因素，還應(yīng)考慮無人機(jī)與車輛的接駁問題。為此，主要總結(jié)外部不確定的天氣情況和繞飛因素，內(nèi)部無人機(jī)電池電量、有效載荷等能量消耗對無人機(jī)路徑規(guī)劃的影響。

2.1 能量消耗

目前在進(jìn)行無人機(jī)路徑規(guī)劃中，單純對無人機(jī)飛行范圍、飛行時間、載重能力等進(jìn)行約束，構(gòu)建的線性模型不能滿足實(shí)際運(yùn)行的約束，構(gòu)建的應(yīng)是非線性模型[37]，求解時如果用線性模型的約束就不可行性。為了使得求解的無人機(jī)優(yōu)化路線在實(shí)際運(yùn)行中可行，考慮無人機(jī)能耗是必要的。文獻(xiàn)[38]將對無人機(jī)續(xù)航的影響可以分為3個方面，分別是無人機(jī)本身的影響，無人機(jī)機(jī)動動作的影響以及配送過程中的一些操作的影響，詳細(xì)分類如圖5所示。目前的無人機(jī)能耗方面的研究大多是其中某幾個主要因素的研究。

圖5 影響無人機(jī)續(xù)航的主要因素Fig.5 Main factors affecting the endurance of UAV

Dorling等[34]認(rèn)為無人機(jī)的飛行時間受到其自重以及電池儲能的限制，證明了能耗隨有效載荷和電池重量近似線性變化。無人機(jī)飛行功率大小與其自重、有效載荷、空氣密度、旋翼面積、推力大小和重力加速度有關(guān)，建立了考慮能耗模型和無人機(jī)功耗模型，根據(jù)單旋翼功率[式(1)]推導(dǎo)出多旋翼能耗模型為

(1)

(2)

式中：P*為單旋翼直升機(jī)盤旋功率，W；P為多旋翼無人機(jī)飛行功率，W；T為推力，T=(W+w)，N；W為無人機(jī)自重，kg；w有效載荷，kg；ρ為空氣密度，kg/m3；g為重力加速度，N/kg；ζ為旋翼面積，m2；n為旋翼的個數(shù)。隨后通過數(shù)據(jù)擬和為線性公式，可表示為

p(m)=αm+β

(3)

式(3)中：m為電池重量和有效載荷之和,kg；p(m)為電池和有效載荷為m時的無人機(jī)飛行功率；α為每千克電池和有效載荷消耗的功率，W/kg；β為飛行器在空中飛行所需的功率，W。

而后運(yùn)用模擬退火算法求解，發(fā)現(xiàn)最小的總交付時間與預(yù)算成本成反比，無人機(jī)的多次重復(fù)使用與其電池尺寸的優(yōu)化對最后的結(jié)果也存在著較大的影響。Dorling等[34]只將有效載荷作為飛行功率影響因素；文獻(xiàn)[39]同時將有效載荷與速度作為影響飛行功率的因素。Jeong等[40]則擴(kuò)展了能耗模型。根據(jù)無人機(jī)功率雖有效載荷變化成線性變化又推導(dǎo)出飛行時間與飛行功率、電池塊數(shù)、電池電壓和轉(zhuǎn)化效率等的關(guān)系。為更加詳細(xì)描述飛行間的能量變化，Cheng等[37]建立了與無人機(jī)有效載荷和行駛距離有關(guān)的非線性能耗模型，同時考慮了時間窗的約束，與近似線性能耗模型相比，非線性能耗模型能夠更加真實(shí)的模擬無人機(jī)在整個配送過程中的能量消耗情況。非線性能耗模型為

(4)

式(4)中：k為與無人機(jī)本身以及環(huán)境相關(guān)的常數(shù)；mbattery為電池質(zhì)量；qij為有效載荷。

圖6 無人機(jī)飛行過程的不同階段Fig.6 Different stages of the UAV flight process

通過仿真測試發(fā)現(xiàn)使用線性近似模型求解的優(yōu)化配送方案在非線性模型約束下是不可行的，該非線性模型計算出的能耗與文獻(xiàn)[34]中的線性模型計算結(jié)果相比相差9%，線性近似模型的計算結(jié)果在非線性能量模型下是不可行。當(dāng)解決實(shí)際問題時，非線性模型的優(yōu)勢更加突出，它可以更保守更真實(shí)的描述實(shí)際情況，產(chǎn)生可行的方案。Liu等[41]從力學(xué)的角度剖析，從推力與阻力的角度分析無人機(jī)飛行時的功率。將無人機(jī)飛行功率消耗分為誘導(dǎo)功率、外形功率與寄生功率，這3個功率部件占總功耗的95%以上。Raj等[42]細(xì)化了無人機(jī)配送的過程，認(rèn)為不同飛行階段無人機(jī)的飛行速度不同，無人機(jī)的飛行速度應(yīng)作為決策變量，在速度和航程之間權(quán)衡，目標(biāo)是最小化配送時間，因此建立能耗模型，認(rèn)為電池大小、有效載荷、飛行距離和飛行階段(如起飛、巡航和著陸)都與能耗存在關(guān)系，限定了電池的可用能量大小。將整個過程分為8個階段，即起飛、巡航、降落、配送、起飛、巡航、等待和降落，如圖6所示。

為了細(xì)化飛行過程，飛行過程可分為3類，第一類是起飛或降落，第二類程是巡航，第三類是懸停。每類飛行過程的飛行功率計算公式不同，根據(jù)每一飛行階段的功率與飛行時間推導(dǎo)出整個飛行所需能量。與Raj等[42]提出的模型類似，Liu等[20]認(rèn)為隨著包裹交付給客戶無人機(jī)的能耗分階段減少，也建立多階段無人機(jī)能耗模型。Coelho等[15]則提出了僅與無人機(jī)速度有關(guān)的能耗模型。

相比于簡單的對無人機(jī)飛行時間與飛行距離約束的模型，考慮無人機(jī)能耗模型可以詳細(xì)計算無人機(jī)在配送的各個階段所需的能量，從而在能量的限制下更加精確的規(guī)劃無人機(jī)城市配送路徑。目前相關(guān)文獻(xiàn)建立的能耗模型影響因素匯總?cè)绫?所示，每篇文獻(xiàn)考慮的因素如表2所示。

表1 無人機(jī)能耗模型影響因素Table 1 Influencing factors of UAV energy consumption model

表2 不同能耗模型考慮因素Table 2 Influencing factors were considered in different energy consumption models

從表2中可以看出，學(xué)者們在無人機(jī)能耗模型構(gòu)建中考慮了不同的因素，其中速度，有效載荷，重力加速度等是常使用的因素。

2.2 繞飛因素

無人機(jī)城市配送存在禁區(qū)限制區(qū)、較高的建筑物、自然障礙物和人工障礙物等，但多數(shù)無人機(jī)路徑規(guī)劃問題建模時并沒有考慮禁區(qū)、限制區(qū)或障礙物等因素，求解的路徑為點(diǎn)對點(diǎn)模式，因此未來無人機(jī)在城市執(zhí)行配送任務(wù)時，必將存在繞飛的情況。Jeong等[40]在規(guī)劃無人機(jī)配送路徑時考慮了禁飛區(qū)的影響，假定禁飛區(qū)在特定時段禁止無人機(jī)進(jìn)入，圖7為無人機(jī)飛行路徑。Zhang等[43]則將繞飛因素分為禁區(qū)與危險區(qū)域，分別探討了交會任務(wù)中的協(xié)同路徑規(guī)劃，分配任務(wù)中的協(xié)同路徑規(guī)劃，覆蓋任務(wù)中的協(xié)同路徑規(guī)劃。

為模擬真實(shí)配送環(huán)境，將UAV編隊(duì)，考慮了配送過程中UAV之間的碰撞風(fēng)險與障礙物風(fēng)險考慮在內(nèi)，在三維空間中建模[44-46]。障礙物既可設(shè)為長方體，也可將障礙物假設(shè)為圓柱體，UAV在避障時既可以水平繞飛也可以垂直繞飛。郭興海等[44]假設(shè)飛行路徑中存在超過10 m障礙物UAV只能水平繞飛，同時為了避免UAV之間的碰撞設(shè)置了安全距離，規(guī)定了UAV飛行高度限制。

l為禁飛區(qū)內(nèi)執(zhí)飛距離；l′為禁飛區(qū)外繞飛距離；θ為繞飛角度圖7 無人機(jī)飛行路徑[40]Fig.7 UAV flight path[40]

2.3 不確定的自然環(huán)境

無人機(jī)在城市中進(jìn)行配送時，天氣原因(例如風(fēng)、溫度、惡劣天氣等)多會影響其配送效率與安全，越來越多的文獻(xiàn)將天氣的影響加入無人機(jī)配送路徑規(guī)劃模型。Seon等[47]考慮了大氣溫度對無人機(jī)電池容量的影響，探討了不同溫度對電池容量的影響，研究發(fā)現(xiàn)隨著溫度的下降電池容量減小從而縮短了無人機(jī)的飛行時間，如果在溫度變化顯著(1 d內(nèi))地區(qū)運(yùn)行，那么電池性能必將受到影響。通過實(shí)際數(shù)據(jù)擬和了無人機(jī)鋰電池容量與溫度的二次函數(shù)方程以便預(yù)測電池容量的未來變化趨勢。

除溫度對無人機(jī)本身有影響，風(fēng)對無人機(jī)的飛行軌跡也存在較大的影響，進(jìn)而影響無人機(jī)到達(dá)目的地的時間。在風(fēng)的影響下，無人機(jī)為準(zhǔn)確到達(dá)客戶所在地，發(fā)射方向與實(shí)際飛行軌跡存在一定夾角。

Baskar等[48]研究了現(xiàn)實(shí)城市幾何中城市空氣流動性對無人機(jī)路徑規(guī)劃的影響，構(gòu)建了真實(shí)城市環(huán)境中風(fēng)影響下無人機(jī)配送模型路線規(guī)劃，同時也考慮了城市障礙物繞行。

3 多因素影響下的無人機(jī)路徑規(guī)劃問題

根據(jù)無人機(jī)與卡車的協(xié)作模式，無人機(jī)的路徑規(guī)劃問題(routing problem with drones，RP-D)可分為:無人機(jī)旅行商問題(travelling salesman problem with drone, TSP-D)、無人機(jī)配送路線問題(vehicle routing problem with drone, VRP-D)、無人機(jī)配送問題(drone delivery problem, DDP)、承運(yùn)人無人機(jī)運(yùn)輸車問題(carrier-vehicle with drones, CVP-D)[49]，其中TSP-D問題又可分為飛行助手商旅問題(flying sidekick traveling salesman problem，F(xiàn)STSP)和并行的無人機(jī)調(diào)度問題(the parallel drone scheduling TSP, PDSTSP)。TSP-D與VRP-D中無人機(jī)與卡車參加配 送，DDP與CVP-D只有無人機(jī)配送，分類如圖8[49]所示。

圖8 無人機(jī)路徑規(guī)劃問題分類[49]Fig.8 Classification of UAV path planning problems[49]

將無人機(jī)配送模式分為機(jī)車協(xié)同與無人機(jī)單獨(dú)配送兩類，不同的配送模式路徑不同，在兩種模式下因內(nèi)部或外部某些因素，如能耗、禁區(qū)、障礙物或不確定自然環(huán)境等對無人機(jī)路徑規(guī)劃問題產(chǎn)生的影響也不同。

3.1 無人機(jī)與車輛協(xié)同路徑規(guī)劃

3.1.1 能耗相關(guān)路徑規(guī)劃

無人機(jī)與車輛組合配送路徑規(guī)劃問題涉及多輛卡車與多架無人機(jī)的協(xié)調(diào)，其目標(biāo)是最短配送時間或最短配送路線、成本。較多研究未考慮無人機(jī)能耗問題，只是對無人機(jī)飛行時間與飛行距離進(jìn)行簡單的約束，其計算結(jié)果、優(yōu)化路線方案等與實(shí)際運(yùn)行存在較大的偏差，無人機(jī)能耗模型建立對機(jī)車協(xié)作模式的問題求解有了進(jìn)一步的改善，符合實(shí)際。

在能耗問題的研究中，學(xué)者們基于TSP-D基礎(chǔ)上提出FSTSP變體，因無人機(jī)具有不同飛行速度、有效載荷、服務(wù)時間和飛行持久度，因此無人機(jī)能量被確定為包裹重量、速度和運(yùn)行時間的線性函數(shù)。為比較不同能耗模型對路徑規(guī)劃的影響，分別運(yùn)用非線性能耗模型、線性能耗模型、固定飛行時間模型、固定飛行距離模型和無限續(xù)航時間模型對無人機(jī)路線進(jìn)行規(guī)劃，目標(biāo)是最小化配送時間。為求解規(guī)模較大的實(shí)際問題，提出一種三階段迭代啟發(fā)式算法，分別規(guī)劃卡車與無人機(jī)的配送路線，而后重新權(quán)衡卡車行駛時間、卡車服務(wù)時間以及無人機(jī)發(fā)射和回收時間以期最小化總配送時間，結(jié)果表明在線性能耗模型約束下與在非線性能耗模型約束下產(chǎn)生結(jié)果相差最小，在固定飛行時間模型約束下與在非線性能耗模型約束下產(chǎn)生結(jié)果則相差最大。此外在固定飛行時間模型、線性模型、固定飛行距離模型和無限制條件模型約束下產(chǎn)生的飛行路線在非線性能耗模型約束下的可行率逐漸下降。如果在運(yùn)用不恰當(dāng)?shù)哪芎哪Ｐ蜕蔁o人機(jī)飛行路線，那么無人機(jī)在途中有耗盡電池電量的危險。FSTSP變體問題[42]與DDP問題[37]類似，認(rèn)為無人機(jī)功耗是速度和包裹重量的非線性函數(shù)，不同的飛行速度會影響其有效航程。為驗(yàn)證此結(jié)論，建立新型的機(jī)車協(xié)同配送模型[42]，把無人機(jī)速度作為決策變量，在速度和航程之間進(jìn)行權(quán)衡，動態(tài)調(diào)整無人機(jī)速度，目標(biāo)為最小化總交付時間。結(jié)果表明，與固定的最大飛行速度和固定最大航程速度相比，可變速度無人機(jī)在非必要時刻減小飛行速度從而減小能耗，更多的客戶也將由無人機(jī)服務(wù)(與固定速度飛行相比)，卡車服務(wù)用戶減少，縮短卡車行程，配送時間變短，減少無人機(jī)與卡車會合時的等待時間，減少總能耗。從節(jié)省資金的角度來看，這對運(yùn)輸公司來說意義重大。變速無人機(jī)每架次消耗的能量更少，等待卡車的時間也更少，車輛消耗能量也更少。

由此可見，在無人機(jī)與車輛協(xié)同的路徑規(guī)劃中，無人機(jī)能耗問題是影響無人機(jī)安全飛行的重要因素，能耗模型的構(gòu)建也至關(guān)重要，研究表明非線性模型更符合無人機(jī)真實(shí)能耗狀況，可以更精確的計算其飛行過程能耗情況。在與車輛協(xié)同中，分別規(guī)劃各自路徑，然后再權(quán)衡，協(xié)調(diào)了無人機(jī)與卡車配送任務(wù)與路徑，找出最優(yōu)配送方案。單卡車多無人機(jī)環(huán)境下與可變速度的無人機(jī)更節(jié)省時間[42]，此類題可以擴(kuò)展到考慮變速卡車，以減少排放和機(jī)車接駁時間為目標(biāo)。此外，未來可以使用更加精準(zhǔn)的能耗模型同時描述無人機(jī)與卡車的能耗情況。

3.1.2 考慮多因素的路徑規(guī)劃

Dukkanci等[50-51]、Poikonen等[30]和Han等[33]提出了CVP-D的3種變體，明確考慮了無人機(jī)的能耗，Dukkanci等[50]、Han等[33]還加入時間窗的影響。Dukkanci等[50]提出的配送系統(tǒng)是FSTSP[18]和DDP中使用的系統(tǒng)[34]的組合，卡車可以運(yùn)輸無人機(jī)，無人機(jī)可以在倉庫或卡車上發(fā)射可以為客戶配送包裹，卡車在停車點(diǎn)等待回收無人機(jī)，將無人機(jī)的速度作為決策變量。加入時間窗約束后無人機(jī)飛行范圍與飛行時間受限會導(dǎo)致原可行方案部分變?yōu)椴豢尚衃33]，且隨著可接受配送時間范圍減小，不可行方案增加，同時為在時間窗約束內(nèi)完成交付任務(wù)，總成本與總能耗也有小幅增加。Poikonen等[30]與Dukkanci等[51]提出了CVP-D的變體中，卡車攜帶的無人機(jī)可以執(zhí)行多次訪問并攜帶多個異構(gòu)包，最小化交付時間與能耗。目標(biāo)值對無人機(jī)速度高度敏感[35]，此外無人機(jī)的數(shù)量對交付也有很大影響，隨著數(shù)量增加，每架無人機(jī)服務(wù)客戶被重新分配，總交付效率提高。Dukkanci等[51]則是從發(fā)射點(diǎn)的角度出發(fā)，選取合適的發(fā)射點(diǎn)，而后使用卡車將無人機(jī)運(yùn)載至發(fā)射點(diǎn)。在交付時間約束下探究不同無人機(jī)速度與卡車速度對成本以及能耗的影響。論文中的一個假設(shè)是卡車以恒定速度行駛。林驛等[52]則將卡車行駛路程分段，每段速度不同。在客車時間窗限制下優(yōu)化無人機(jī)配送方案以及電池組的調(diào)度方案以最小化配送成本。

FSTSP問題中除了考慮有效載荷對無人機(jī)能耗影響，還加入禁飛區(qū)對配送影響[40]。使用基于進(jìn)化的啟發(fā)式算法求解卡車與無人機(jī)配送路線，目標(biāo)是最小化配送總時間。對比不同有效載荷與禁區(qū)數(shù)量對求解結(jié)果影響。隨著有效載荷和禁區(qū)數(shù)量的增加，配送時間逐漸增加，其中有效載荷對時間影響范圍為1%～4.6%，而禁區(qū)對時間的影響范圍高達(dá)17.2%～22.5%。禁飛區(qū)直接導(dǎo)致無人機(jī)繞飛從而改變其原路徑增加了飛行距離，而有效載荷差距較小，對能耗影響較小，配送路徑?jīng)]有發(fā)生較大變化，因此禁飛區(qū)影響高于有效載荷。

基于能耗，在不同變體的問題中考慮時間窗、禁飛區(qū)、速度、障礙物和配送中心位置等多種因素下路徑規(guī)劃，更符合無人機(jī)配送的動態(tài)性、實(shí)時性[53]與安全性要求；在與車輛協(xié)同中，同時考慮兩種交通工具的特性，同時運(yùn)行中考慮無人機(jī)發(fā)射與回收等接駁時間因素，確保配送時間最短、成本最低。然而，地面交通影響車輛行駛、空中障礙物或風(fēng)等不確定的外部因素可能會影響無人機(jī)的速度和方向，這是目前研究的一個局限性。

3.2 無人機(jī)配送路徑規(guī)劃

3.2.1 基于能耗的路徑規(guī)劃

在無人機(jī)獨(dú)立運(yùn)行模式下的路徑規(guī)劃問題屬于DDP問題，一般也會建立無人機(jī)的能耗模型，考慮有效載荷、電池重量和速度與能耗的關(guān)系，細(xì)化無人機(jī)在配送過程的能量消耗，探究電池消耗率與有效載荷關(guān)系[54]或能耗與速度電池重量等的關(guān)系，而不只是粗略的考慮其飛行距離與時間。除了建立線性能耗模型描述無人機(jī)有效載重與能量消耗的關(guān)系[40]，Cheng等[37]建立了非線性能耗模型可以更好地刻畫整個能耗過程，發(fā)現(xiàn)非線性能耗模型計算能耗結(jié)果與線性模型相差9%，也就是線性模型下產(chǎn)生的配送方案在非線性模型下是不可行的。Liu等[41]從力學(xué)角度分析，建立飛行時的無人機(jī)自身能耗模型，將功率分為誘導(dǎo)功率(飛機(jī)發(fā)動機(jī)對流經(jīng)機(jī)翼表面空氣傳輸動能的效率)、外型功率(葉片轉(zhuǎn)動時的功率)與寄生功率(飛行時克服機(jī)身產(chǎn)生阻力時的功率)。實(shí)際所需能量與模型計算產(chǎn)生能耗有10%左右的差距。原因是無人機(jī)飛行中加速和減速比較多，因此實(shí)際消耗的能量高于模型計算結(jié)果。其次無人機(jī)飛行高度的風(fēng)速比地面的風(fēng)速更大變化也更為顯著。但是模型中假設(shè)風(fēng)速為零。實(shí)驗(yàn)結(jié)果證明實(shí)際配送過程復(fù)雜[37,41]，簡單線性模型并不能很好的描述無人機(jī)能耗。

Wu等[36]從排班時間、充電設(shè)施和充電時間的角度探究能耗對配送的影響。將乘客配送至目的地，無人機(jī)在充電站充電。建立混合整數(shù)規(guī)劃來模擬電動公交(urban air mobility,UAM)收費(fèi)調(diào)度過程，設(shè)計充電時間表使乘客的延誤最小化，同時滿足電動汽車的電池充電需求。通過仿真發(fā)現(xiàn)隨著排班間隔時間增加總延誤時間逐漸減小，充電設(shè)施要適中，少充電設(shè)施影響電調(diào)度效率，多設(shè)施但無人機(jī)數(shù)量不足也會影響調(diào)度。

3.2.2 外部因素影響下路徑規(guī)劃

無人機(jī)本身能耗特性會影響無人機(jī)配送路徑規(guī)劃，實(shí)際運(yùn)行中外部因素，例如風(fēng)、溫度等天氣也會對其產(chǎn)生影響。風(fēng)會影響無人機(jī)速度與實(shí)際飛行軌跡從而可能會影響無人機(jī)的能耗與配送時間[55]。除了考慮了風(fēng)對無人機(jī)路徑選擇的影響，Troudi等[56]還加入了時間窗的限制，分別探究了最小化行駛距離、最小化無人機(jī)使用數(shù)量與最小化電池使用數(shù)量3個目標(biāo)下，時間窗對能耗與行駛距離的影響。目標(biāo)為最小化行駛距離和最小化電池使用數(shù)量時，能耗與距離隨著時間窗增加而減小，而最小化無人機(jī)使用數(shù)量時，能耗與距離隨著時間窗增加而先減小后增加。未來解決3個不同目標(biāo)之間的平衡有助于在實(shí)際運(yùn)營中節(jié)省成本。

城市運(yùn)行環(huán)境復(fù)雜，為了真實(shí)模擬城市配送環(huán)境，將風(fēng)場與城市障礙物結(jié)合考慮[48]，在優(yōu)化配送路徑時，加入風(fēng)對無人機(jī)能量影響的同時考慮城市建筑物、障礙物等繞行，利用Dijkrstra算法在指定的權(quán)重的加權(quán)圖上找到路徑，得出能量最佳路線與繞行最短路線而不是簡單點(diǎn)對點(diǎn)直線路徑，但只是為一位客戶服務(wù)路線，后續(xù)可在此模型的基礎(chǔ)上計算得到為多個客戶服務(wù)路線。

除風(fēng)的影響，氣溫會對電池容量產(chǎn)生影響。在實(shí)際運(yùn)行中不同時段的溫度不同，Seon等[47]認(rèn)為溫度影響無人機(jī)電池實(shí)際容量，根據(jù)歷史數(shù)據(jù)擬合電池容量與溫度的函數(shù)關(guān)系式，從而推導(dǎo)出未來在不同溫度下無人機(jī)的電池容量，溫度越低無人機(jī)電池實(shí)際容量與標(biāo)稱容量相差越大，最大偏差為8%。最終目的為求解出最佳無人機(jī)飛行時間表且總運(yùn)行成本最小。

不論何種配送模式，核心是無人機(jī)的運(yùn)行，因此研究中重點(diǎn)是無人機(jī)的影響因素。表3總結(jié)了無人機(jī)規(guī)劃路徑時所考慮的因素。可以看出，目前在對無人機(jī)路徑規(guī)劃問題研究中，對無人機(jī)能耗問題研究較多，考慮到能耗對飛行時間、距離的而影響。也有從時間窗限制考慮對路徑規(guī)劃的影響。其他一些不確定性的參數(shù)，如環(huán)境的影響，溫度、風(fēng)、氣壓等考慮較少。

表3 無人機(jī)路徑規(guī)劃問題考慮影響因素Table 3 The influencing factors are considered in UAV path planning

4 結(jié)論與展望

根據(jù)中外對無人機(jī)配送路徑規(guī)劃研究，將無人機(jī)配送模式分為機(jī)車協(xié)同與無人機(jī)獨(dú)立運(yùn)行兩種運(yùn)行模式。機(jī)車協(xié)同配送范圍更遠(yuǎn)但其運(yùn)行也更為復(fù)雜，根據(jù)二者協(xié)同方式，將其分為車輛參與配送與不參與配送兩種模式。探究了無人機(jī)能耗、繞飛因素與不確定自然環(huán)境對配送路徑的影響。從目前已有研究可以看出，較多文獻(xiàn)開始深入研究無人機(jī)能耗對配送影響，而對外部環(huán)境因素如溫度、風(fēng)，繞飛因素、時間窗等研究相對較少，有待進(jìn)一步豐富。

實(shí)際運(yùn)行中無人機(jī)會受到多重因素共同影響，顯然，能耗與外部因素對無人機(jī)路徑規(guī)劃影響問題尚未得到充分研究。未來研究此類問題可以考慮以下因素。

(1)能量評估。目前多數(shù)研究簡單地限制了無人機(jī)的飛行距離或飛行時間，但在實(shí)際運(yùn)行環(huán)境中，無人機(jī)能耗是一個受多因素影響復(fù)雜的過程，例如本文提到的風(fēng)、溫度等不確定自然環(huán)境的影響以及外部障礙物或禁飛區(qū)的影響，在復(fù)雜因素的影響下，無人機(jī)的能耗不盡相同，如果單純限制其飛行距離或飛行時間，那么將導(dǎo)致無人機(jī)因電量不足而無法完成任務(wù)或未能充分利用電池電量，導(dǎo)致配送成本增加。而能耗計算模型，如線性能耗模型[34]與非線性能耗模型[37]計算結(jié)果相差9%。未來需要建立更加精確的能耗模型計算飛行過程所需能量,以便合理規(guī)劃飛行路線。

(2)設(shè)施設(shè)備。無人機(jī)飛行范圍有限，故多數(shù)學(xué)者將車與無人機(jī)組合運(yùn)行以擴(kuò)大其飛行范圍，因地面交通的復(fù)雜性，機(jī)車很難同時到達(dá)接駁地點(diǎn)，因此機(jī)車組合運(yùn)行時會面臨車時間延遲問題，可以通過設(shè)立中間服務(wù)點(diǎn)或充電點(diǎn)擴(kuò)大其飛行范圍，通過管理中間服務(wù)點(diǎn)或充電點(diǎn)的運(yùn)行，規(guī)劃無人機(jī)配送路徑，擴(kuò)大無人機(jī)飛行范圍。

(3)不確定環(huán)境。除了溫度、風(fēng)、雨等一些外部自然環(huán)境，其他動態(tài)因素如移動障礙物，顧客要求配送時段變化等都是所要面對的挑戰(zhàn)。目前研究中所有顧客需求及其配送時間窗全部已知，實(shí)際運(yùn)行中時間窗可能發(fā)生改變，同時也可能出現(xiàn)新的訂單，區(qū)域限制也會發(fā)生動態(tài)調(diào)整，如Jeong等[40]提出的某些區(qū)域會在一些特定時段限制飛行。Dayarian等[57]闡述了一種根據(jù)顧客的動態(tài)要求調(diào)度方法。如何動態(tài)調(diào)度無人機(jī)以達(dá)到成本最小總配送路徑最短也是一大挑戰(zhàn)。因此未來的研究應(yīng)考慮動態(tài)系統(tǒng)中無人機(jī)的運(yùn)行，加入與無人機(jī)有關(guān)的實(shí)際約束，提出解決此類問題的有效算法。

(4)空中運(yùn)行管理。隨著無人機(jī)技術(shù)的發(fā)展，未來必將有大量無人機(jī)為客戶提供服務(wù)，為保證空中與地面安全，需合理規(guī)劃航線，考慮無人機(jī)優(yōu)先級設(shè)置，墜落與碰撞風(fēng)險。目前多數(shù)論文在規(guī)劃無人機(jī)路徑時未考慮無人機(jī)沖突如何解脫且飛行路線多為點(diǎn)對點(diǎn)式，但在實(shí)際運(yùn)行中規(guī)劃無人機(jī)飛行路線應(yīng)考慮無人機(jī)之間的碰撞風(fēng)險，同時飛行路線應(yīng)盡量避開人口稠密區(qū)以及危險區(qū)等。甄然等[58]提出基于量子遺傳算法，以解決實(shí)時運(yùn)行的兩架無人機(jī)之間的沖突。Clothier等[59]、Hian等[60]和Shelley等[61]通過考慮因無人機(jī)失效對人造成傷害完善航跡預(yù)測模型，減小因無人機(jī)墜落而引發(fā)一系列事故概率。為減少或避免大量無人機(jī)運(yùn)行可能會引發(fā)的安全事故，需建立考慮更多因素的風(fēng)險評估模型[62-64]，根據(jù)模型動態(tài)規(guī)劃UAV配送路線。