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

任新惠， 武 彤

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

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

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

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

1 無人機配送模式

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

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

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

1.1 無人機與車輛協(xié)同運行

1.1.1 車輛參與配送

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

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

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

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

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

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

1.1.2 車輛不參與配送

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

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

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

1.2 無人機獨立運行

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

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

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

2.1 能量消耗

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

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

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

(1)

(2)

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

p(m)=αm+β

(3)

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

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

(4)

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

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

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

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

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

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

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

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

2.2 繞飛因素

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論與展望

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

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

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

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

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

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