城市低空物流無人機飛行計劃預(yù)先調(diào)配

張洪海, 任真蘋, 馮謳歌, 王 非, 劉 皞

(南京航空航天大學(xué)民航學(xué)院, 江蘇 南京 211106)

0 引 言

無人機物流運輸近年逐漸興起,在末端配送過程中不受地面交通狀況的局限,具備時間短、效率高等優(yōu)勢,可發(fā)展為未來城市空中交通“最后一公里”物流配送的主力。無人機在飛行任務(wù)獲批起飛時刻后才能執(zhí)行任務(wù),因此飛行管制部門應(yīng)考慮飛行計劃預(yù)先調(diào)配,以避免空域使用和時間沖突,確保飛行安全。

國內(nèi)外學(xué)者對城市低空物流無人機與飛行計劃管理進行過研究。在城市空中交通發(fā)展方面,文獻[1]指出未來將會有大量電推進垂直起降型航空器服務(wù)于全球低空市場的發(fā)展。文獻[2]認為未來城市空中交通的全球發(fā)展規(guī)模在2040年預(yù)計達到1.5萬億美元。文獻[3]認為無人機將作為城市低空物流市場的主力服務(wù)于“最后一公里”配送,預(yù)計2030年將滿足5億單運輸需求。文獻[4]分析了墨爾本的城市交通方式,結(jié)果表明城市空中交通因其時間優(yōu)勢未來將擁有較大市場。

在低空物流無人機運行方面,文獻[5]考慮了無人機在人道主義物流最后一英里配送中的應(yīng)用,提出一種通過無人機將輕型救援物品(如疫苗、純凈水等)運送到受災(zāi)地區(qū)的優(yōu)化模型。文獻[6]提出利用無人機完成醫(yī)療保健運輸更加及時、高效和經(jīng)濟,設(shè)計了無人機醫(yī)療網(wǎng)絡(luò)運輸?shù)臎Q策模型。文獻[7]關(guān)注了無人機在物流配送中區(qū)別于普通地面物流的基本特征,考慮無人機飛行時間、裝載能力、貨物重量對飛行能力的影響,提出一種混合整數(shù)線性規(guī)劃公式和任務(wù)分配啟發(fā)式算法,并通過數(shù)值示例進行測試。文獻[8]研究了無人機在人口稠密的城市環(huán)境中的運行風(fēng)險,利用空間模擬系統(tǒng)進行風(fēng)險評估。文獻[9]指出越來越多的物流公司都在研究使用無人機進行快遞交付,針對無人機投送的容量限制問題,提出一種混合元啟發(fā)式方法,仿真結(jié)果證實了所提算法的有效性。文獻[10]考慮權(quán)重系數(shù)、時間窗約束、無人機約束等建立了無人機物流任務(wù)分配模型,采用改進粒子群優(yōu)化算法求解,仿真結(jié)果表明該算法能夠有效解決無人機物流任務(wù)分配問題。文獻[11]提出基于改進人工勢場-快速擴展隨機樹算法,以實現(xiàn)無人機在物流配送中準確、快速的路徑規(guī)劃。文獻[12]使用牛頓運動定律和伽利略自由落體評估無人機碰撞概率密度,通過路徑規(guī)劃保證無人機避開人口密集區(qū)域。

在飛行計劃調(diào)配方面,文獻[13]闡述了采用直接法和插值法劃設(shè)調(diào)配區(qū)域的預(yù)先飛行調(diào)配系統(tǒng),輔助管制員自動生成調(diào)配建議。文獻[14]設(shè)計了由安全高效的空域調(diào)度系統(tǒng)構(gòu)成的路徑規(guī)劃模型和路徑查找算法,可避免航班申請的沖突。文獻[15]考慮綜合優(yōu)先級的影響建立飛行計劃調(diào)配模型,提出一種飛行計劃調(diào)配方法。文獻[16]研究了一種飛行計劃調(diào)配系統(tǒng)來動態(tài)申請、批復(fù)和監(jiān)視空域,通航用戶依托系統(tǒng)可與管理部門進行信息交流。文獻[17]提出一種基于飛行計劃集中處理的預(yù)戰(zhàn)術(shù)飛行流量預(yù)測方法,利用飛行計劃預(yù)測航空器航跡進而預(yù)測航路點流量。文獻[18]以網(wǎng)絡(luò)交通流的運營成本最小為目標,通過調(diào)配飛行計劃估計航空器最佳計劃到達時間。文獻[19]提出一種空中交通航路系統(tǒng)模型以解決飛行中調(diào)度問題。文獻[20]提出一種飛行序列分配模型,以解決不同航空公司飛行計劃在安全標準時間表上的沖突。文獻[21]針對協(xié)調(diào)擁擠機場網(wǎng)絡(luò)的時刻分配問題,考慮時刻請求的優(yōu)先級、最短周轉(zhuǎn)時間等,提出一種啟發(fā)式方法為每個機場生成可行且連貫的時隙。文獻[22]考慮到高峰時段低優(yōu)先級機場需要讓位高優(yōu)先級機場的出發(fā)活動,提出一種雙目標整數(shù)規(guī)劃模型,以解決較低優(yōu)先級航班的起飛調(diào)度問題。

借鑒航班時刻分配的有關(guān)研究,文獻[23]分析了雙目標資源約束調(diào)度來解決戰(zhàn)略機場時刻分配問題,提出一種新型混合啟發(fā)式算法,并以希臘機場的實際時隙數(shù)據(jù)驗證了所提算法的準確性。文獻[24]介紹了一種協(xié)助人工進行初始時隙分配的優(yōu)化決策支持工具,該工具在可接受的時間內(nèi)生成有效的時隙解決航班分配問題。文獻[25]研究了阻塞緩解策略,提出一種航班時隙分配模型和解決方案,通過調(diào)度時刻來緩解機場擁堵。文獻[26]提出一種考慮時刻調(diào)度效率和公平性的雙目標機場時刻調(diào)度模型,研究了考慮歷史時隙使用權(quán)和不考慮歷史時隙使用權(quán)的機制下時隙調(diào)度效率-公平的權(quán)衡,以實現(xiàn)航班時隙調(diào)度。文獻[27]在文獻[26]的基礎(chǔ)上提出了考慮效率、公平性和航空公司偏好的多目標兩階段時刻分配機制。文獻[28]提出一種整數(shù)線性規(guī)劃模型,通過周轉(zhuǎn)時間限制飛機輪轉(zhuǎn),用于在歐洲范圍內(nèi)優(yōu)化機場時刻分配。文獻[29]提出一種符合全球航班時刻指南的優(yōu)化模型,將機場時刻分配給航空公司。

目前,面向低空物流無人機的研究多集中于任務(wù)分配與路徑規(guī)劃[5-12],面向飛行計劃的研究集中于飛行調(diào)度[15,17-21]和管理系統(tǒng)[13-14,16],但面向低空無人機運輸中飛行計劃調(diào)配流程的研究較少。無人機飛行計劃預(yù)先調(diào)配可從高度、航路和時間的角度出發(fā),由于調(diào)整高度和航路存在局限,一是城市低空可供調(diào)整的飛行空間有限,往往不允許無人機產(chǎn)生大幅度空間變動;二是無人機電量、承重等性能有限,執(zhí)行任務(wù)的空間變動會降低運輸效率。因此,本文研究基于實際運輸需求,從時間調(diào)整的角度出發(fā),以飛行計劃成本最低為調(diào)配目標,建立無人機飛行計劃預(yù)先調(diào)配模型,設(shè)計考慮綜合優(yōu)先級的飛行計劃預(yù)先調(diào)配算法求解,生成無沖突的時刻表,為飛行任務(wù)排序后分配起飛時刻,以實現(xiàn)飛行計劃的預(yù)先調(diào)配。

1 飛行計劃預(yù)先調(diào)配問題建模

1.1 問題描述與相關(guān)假設(shè)

某城市片區(qū)的物流配送點,利用無人機裝載小批量貨物運輸至收貨點,貨物運輸過程擬采用可垂直起降的充電旋翼無人機,無人機任務(wù)執(zhí)行完畢后返回配送中心。現(xiàn)有配送點對即將執(zhí)行的飛行任務(wù)向管制部門提交飛行申請,為保證城市空域范圍內(nèi)無人機避免沖突有序飛行,管制部門需要在空域使用前進行飛行計劃審批與飛行時刻調(diào)配,盡可能確保飛行安全。本模型的主要假設(shè)如下:① 物流配送點和各個收貨點的位置已知;② 每架無人機需要從配送點的不同起降點出發(fā),沿既定航路飛往收貨點,完成其配送任務(wù)后返回配送點;③ 每個起降點有多架無人機等待起飛,每架無人機單次只服務(wù)一對起降點;④ 無人機滿電狀態(tài)出發(fā),飛行速度預(yù)先設(shè)定,出發(fā)后不再接受新的任務(wù)安排。城市低空物流無人機配送模式如圖1所示。

圖1 城市低空物流無人機配送模式Fig.1 Logistics unmanned aerial vehicle distribution mode in urban low-altitude airspace

1.2 無人機飛行計劃預(yù)先調(diào)配模型

1.2.1 決策變量

無人機飛行計劃預(yù)先調(diào)配的實質(zhì)是對每條飛行任務(wù)依據(jù)綜合優(yōu)先級排序后,依次分配一組無沖突的飛行時刻,無人機按照分配的時刻執(zhí)行。設(shè)I表示所有飛行任務(wù)集合,i表示集合中一條飛行任務(wù);J表示所有可分配時刻集合,j表示集合中一組飛行時刻。因此,調(diào)配模型決策變量xij表達式為

(1)

1.2.2 綜合優(yōu)先級

飛行計劃調(diào)配優(yōu)先級主要包括貨物類型優(yōu)先、物流公司優(yōu)先和配送時間優(yōu)先。貨物類型優(yōu)先是指為緊急程度高的任務(wù)優(yōu)先分配時刻,物流公司優(yōu)先是指為顧客滿意度高[30]的物流公司優(yōu)先分配時刻,配送時間優(yōu)先是指為顧客期望送達時間早的任務(wù)優(yōu)先分配時刻。因此,本文提出的綜合優(yōu)先級由貨物類型優(yōu)先級、物流公司優(yōu)先級和配送時間優(yōu)先級這三部分組成,優(yōu)先級取值由飛行任務(wù)決定,分別給予每個部分不同的權(quán)重。在進行無人機飛行計劃調(diào)配時,每條任務(wù)的綜合優(yōu)先級λi描述為

(2)

(3)

式中:λmax和λmin分別表示每種優(yōu)先級的最大值和最小值;λ表示每種優(yōu)先級的實際值;λ′表示每種優(yōu)先級歸一化后的值。

1.2.3 目標函數(shù)

(1) 運輸成本

在實際貨物配送過程中,基于無人機物流運輸?shù)慕?jīng)濟性,追求較低的運輸成本是飛行計劃預(yù)先調(diào)配的重要目標之一,運輸成本是指無人機在配送過程中產(chǎn)生的費用,包括電池能耗、折舊維護等費用[31],表達式為

(4)

式中:qi表示第i條任務(wù)的貨物重量;di表示第i條任務(wù)中配送點至收貨點的距離;λi′表示第i條任務(wù)標準化后的綜合優(yōu)先級;Cd表示無人機單位距離單位載重的成本。

(2) 延誤成本

配送點申請的飛行任務(wù)包含顧客期望送達時間段的信息,無人機獲得時刻后要在既定時間窗內(nèi)完成任務(wù),追求較低的延誤成本也是飛行計劃預(yù)先調(diào)配的重要目標之一,延誤成本是指實際送達時間超出期望送達時間而產(chǎn)生的成本,表達式為

(5)

綜上所述,本模型的目標函數(shù)飛行計劃成本C表示為

minC=

(6)

1.2.4 約束條件

(1) 空域可用時間

每條飛行任務(wù)的起飛時間和返回時間不得超出空域允許使用的時間范圍,即

(7)

(2) 起飛時間間隔

同一起降點連續(xù)起飛的兩架無人機須保持安全間隔,即

(8)

(9)

(3) 到達時間間隔

同一起降點連續(xù)到達的兩架無人機須保持安全間隔,即

(10)

(11)

式中:ΔTarr表示起降點連續(xù)兩架無人機的到達時間間隔。

(4) 交叉時間間隔

前后依次經(jīng)過同一航路交叉點的無人機須保持安全間隔,即

(12)

(5) 唯一性

每條任務(wù)只能分配到一組時刻,每組時刻最多被一條任務(wù)占用,即

(13)

(14)

(6) 待分配任務(wù)數(shù)量

待分配任務(wù)的數(shù)量不能超過可用飛行時刻的數(shù)量,即

(15)

式中:Ca表示時刻表可用飛行時刻的最大數(shù)量。

(7) 無人機性能

貨物重量不能超過載荷限制,飛行距離不能超過最大航程,即

xijqi≤qmax, ?i∈I;?j∈J

(16)

xijdi≤dmax, ?i∈I;?j∈J

(17)

式中:qi表示第i條任務(wù)的貨物重量;qmax表示無人機最大載重;di表示第i條任務(wù)中配送點至收貨點的距離;dmax表示無人機最遠航程。

2 算法設(shè)計

本文設(shè)計了基于綜合優(yōu)先級的飛行計劃預(yù)先調(diào)配算法,具體步驟如下,流程如圖2所示。

圖2 基于綜合優(yōu)先級的飛行計劃預(yù)先調(diào)配算法流程Fig.2 Algorithm flow of flight plan pre-allocation based on comprehensive priority

步驟 1尋找最優(yōu)配送路徑。依據(jù)配送點S與收貨點G的位置,獲取各航路點坐標于Location表中,采用A*算法在航路網(wǎng)絡(luò)中搜索到無人機要執(zhí)行任務(wù)的最短路徑。

步驟 2生成無沖突時刻表。

步驟 3獲取飛行任務(wù)。建立飛行任務(wù)Plan表,每條任務(wù)包含物流公司、貨物類型、貨物重量qi、期望送達時間和航路點等基本信息,此時還未向飛行任務(wù)分配時刻。

步驟 5判斷飛行任務(wù)是否已全部排序。判斷Plan表,若?i∈I均已完成排序,則Plan為空,進入步驟6,否則返回步驟4,i=i+1。

步驟 7判斷飛行任務(wù)是否已全部獲得時刻。判斷Order表,若?i∈I均已完成時刻分配,則Order為空,算法結(jié)束;否則返回步驟6。

3 算例仿真與分析

3.1 參數(shù)設(shè)置

為驗證本文模型和方法的有效性,基于Python3.8仿真模擬平臺進行實例驗證,由于當(dāng)前物流無人機末端配送基礎(chǔ)設(shè)施建設(shè)不全面,缺乏實際案例數(shù)據(jù),為盡量真實模擬運輸過程,參考文獻[31]設(shè)置仿真參數(shù)。選取南航江寧校區(qū)驛站配送點,08:00至10:00期間任務(wù)執(zhí)行完畢,相關(guān)參數(shù)設(shè)置如表1所示。

表1 參數(shù)設(shè)置Table 1 Parameter setting

根據(jù)配送點和收貨點在航路網(wǎng)絡(luò)中的位置,搜索從配送點至收貨點避讓障礙物的低空飛行路徑即為無人機配送路線。因兩校區(qū)之間存在高速公路,經(jīng)天橋相連,無人機只可在天橋上方低空空域往返兩區(qū),且去程與回程分別在保持縱向間隔的不同高度層,不存在航路沖突。如圖3所示,其中綠色圓點表示配送點,白色圓點表示收貨點,配送點和收貨點的藍色航路表示無人機去程,綠色航路表示無人機回程。

圖3 某校園配送航路示意圖Fig.3 Schematic diagram of a campus distribution routes

3.2 仿真結(jié)果分析

3.2.1 調(diào)配結(jié)果

以西區(qū)為例,R1、R2、R5和R6共用同一個配送點,R1和R2在返回配送點航段存在交叉,對20條飛行任務(wù)進行預(yù)先調(diào)配。在安排無人機執(zhí)行物流運輸任務(wù)之前,向管理部門申請空域使用時間,在規(guī)定的可用時間范圍內(nèi),生成4條航路的無沖突時刻表,如表2～表5所示,表內(nèi)包含無人機預(yù)計起飛時間、預(yù)計送達時間、預(yù)計返程時間、預(yù)計經(jīng)過交叉點時間和預(yù)計返回配送點時間。本文提出的基于綜合優(yōu)先級的調(diào)配結(jié)果如表6所示。

表2 航路R1時刻表Table 2 Schedules of R1

表3 航路R2時刻表Table 3 Schedules of R2

表4 航路R5時刻表Table 4 Schedules of R5

表5 航路R6時刻表Table 5 Schedules of R6

4條航路的無人機從同一個公共配送點出發(fā),飛至收貨點等待顧客取貨完成后起飛返程,最終回到公共配送點。由上述時刻表可知,所有航路無人機在公共配送點的起飛時間為[08:00:00, 08:00:10, 08:00:20,…],滿足間隔10 s的安全約束;返回配送點的到達時間為[08:02:15, 08:02:25, 08:02:35,…],滿足間隔10 s的安全約束。航路R1和R2的無人機經(jīng)過交叉點處的時間為[08:01:45, 08:02:05, 08:02:25,…],滿足間隔10 s的安全約束。每條航路無人機的起飛間隔為40 s,返程間隔為40 s,返回配送點間隔為40 s,均滿足10 s的安全約束。因此,無人機在航路網(wǎng)絡(luò)中運行時,飛行路徑上的沖突可以通過飛行時刻的調(diào)配進行解脫,使得無人機可以在起降點和航路交叉口順序通行。

表6對20條飛行任務(wù)進行時刻調(diào)配,并為每條航路上的飛行計劃安排起飛順序,由時刻分配結(jié)果可以得出,考慮綜合優(yōu)先級調(diào)配的排序結(jié)果兼顧物流時效性與運行安全性,如航路R2中計劃P6運輸文件,任務(wù)重要程度高優(yōu)先分配,航路R6中計劃P16運輸?shù)氖称飞r類易腐,時效性強也優(yōu)先分配。

3.2.2 算法分析

基于6條航路信息得到08:00-10:00時刻表最大可安排數(shù)量Ca,航路R1有175條時刻,航路R2有174條時刻,航路R3有234條時刻,航路R4有233條時刻,航路R5有175條時刻,航路R6有174條時刻。采用對照實驗法對參數(shù)取值進行分析,取每條航路Ca數(shù)量的飛行計劃作為初始實驗數(shù)據(jù),為每條飛行計劃分配一組可用時刻。基于本文提出的飛行計劃預(yù)先調(diào)配算法,對于每條航路,生成無沖突時刻表,將每條飛行計劃的任務(wù)屬性量化為綜合優(yōu)先級并排序,依據(jù)排序結(jié)果由高到低分配時刻。根據(jù)目標函數(shù),預(yù)先調(diào)配過程考慮每條飛行計劃的運輸、延誤成本和綜合優(yōu)先級。不同航路中,每條飛行計劃的成本為該航路所有飛行計劃成本的平均值,每條飛行計劃的綜合優(yōu)先級為該航路所有飛行計劃綜合優(yōu)先級的平均值,如圖4所示。

圖4 每條飛行計劃的成本和綜合優(yōu)先級變動Fig.4 Cost and comprehensive priority changes for each flight plan

由圖4可知,每條飛行計劃的成本與綜合優(yōu)先級變化趨勢相反,因為優(yōu)先級高的計劃會先進行排序,分配到較早的時刻,出現(xiàn)延誤的可能性小,因此成本低。對于每條航路,待分配計劃的數(shù)量越多,每條飛行計劃的成本越高,由于航路R5距離最短,每條計劃的成本最低,航路R6距離最長,每條計劃的成本最高。

為驗證本文基于綜合優(yōu)先級預(yù)先調(diào)配算法的有效性,分別采用本文算法、基于任務(wù)優(yōu)先調(diào)配和基于先到先服務(wù)調(diào)配對所建模型進行求解,繪制每條飛行計劃的成本變動對比結(jié)果如圖5所示。

圖5 不同算法求解對比Fig.5 Comparison of different algorithm solutions

由圖5可知,與傳統(tǒng)的基于任務(wù)優(yōu)先調(diào)配和先到先服務(wù)調(diào)配算法相比,基于綜合優(yōu)先級調(diào)配結(jié)果明顯最優(yōu)。針對航路網(wǎng)絡(luò)中平均每條計劃的成本,基于綜合優(yōu)先級調(diào)配比基于任務(wù)優(yōu)先調(diào)配和先到先服務(wù)調(diào)配分別降低了21.69%和26.58%,體現(xiàn)出本文調(diào)配算法的可行性。

3.2.3 參數(shù)分析

進一步研究權(quán)重對成本的影響,ω1、ω2和ω3以0.1為步長共設(shè)置36組對照實驗,取值ω1+ω2+ω3=1,每條航路在不同權(quán)重下每條飛行計劃的成本變動情況如圖6所示,其中圓點表示飛行計劃的成本(單位為元)。

圖6 不同權(quán)重對每條飛行計劃的成本影響Fig.6 Impact of different weights on cost of each flight plan

由圖6可知,點的大小表示飛行計劃成本的高低,隨著權(quán)重ω1、ω2和ω3取值變動,不同航路之間成本變動趨勢相似,取圖6中成本最小的點,如橙色標注所示,繪制其至3個坐標軸的垂線,可知使成本最低的綜合優(yōu)先級最優(yōu)權(quán)重組合為ω1=0.2,ω2=0.4,ω3=0.4,航路網(wǎng)絡(luò)中每條飛行計劃的成本為5.42元。

4 結(jié) 論

(1) 針對城市場景下物流無人機配送問題,提出的基于綜合優(yōu)先級飛行計劃預(yù)先調(diào)配模型的實驗結(jié)果表明:考慮運輸成本和延誤成本最小可有效滿足實際配送需求,生成無沖突飛行時刻表,實現(xiàn)飛行任務(wù)排序,并為每條任務(wù)分配飛行時間。

(2) 提出的基于綜合優(yōu)先級飛行計劃預(yù)先調(diào)配算法的成本比基于任務(wù)優(yōu)先調(diào)配和先到先服務(wù)調(diào)配的成本分別降低了21.69%和26.58%,調(diào)配優(yōu)勢顯著。提出的綜合優(yōu)先級由貨物類型優(yōu)先級、物流公司優(yōu)先級和配送時間優(yōu)先級構(gòu)成,具備實際意義,最優(yōu)權(quán)重參數(shù)為0.2、0.4和0.4,每條飛行計劃的成本為5.42元。