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

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

0 引 言

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

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

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

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

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

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

1 飛行計劃預先調配問題建模

1.1 問題描述與相關假設

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

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

1.2 無人機飛行計劃預先調配模型

1.2.1 決策變量

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

(1)

1.2.2 綜合優(yōu)先級

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

(2)

(3)

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

1.2.3 目標函數

(1) 運輸成本

在實際貨物配送過程中,基于無人機物流運輸的經濟性,追求較低的運輸成本是飛行計劃預先調配的重要目標之一,運輸成本是指無人機在配送過程中產生的費用,包括電池能耗、折舊維護等費用[31],表達式為

(4)

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

(2) 延誤成本

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

(5)

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

minC=

(6)

1.2.4 約束條件

(1) 空域可用時間

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

(7)

(2) 起飛時間間隔

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

(8)

(9)

(3) 到達時間間隔

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

(10)

(11)

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

(4) 交叉時間間隔

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

(12)

(5) 唯一性

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

(13)

(14)

(6) 待分配任務數量

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

(15)

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

(7) 無人機性能

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

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

(16)

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

(17)

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

2 算法設計

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

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

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

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

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

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

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

3 算例仿真與分析

3.1 參數設置

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

表1 參數設置Table 1 Parameter setting

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

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

3.2 仿真結果分析

3.2.1 調配結果

以西區(qū)為例,R1、R2、R5和R6共用同一個配送點,R1和R2在返回配送點航段存在交叉,對20條飛行任務進行預先調配。在安排無人機執(zhí)行物流運輸任務之前,向管理部門申請空域使用時間,在規(guī)定的可用時間范圍內,生成4條航路的無沖突時刻表,如表2～表5所示,表內包含無人機預計起飛時間、預計送達時間、預計返程時間、預計經過交叉點時間和預計返回配送點時間。本文提出的基于綜合優(yōu)先級的調配結果如表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的無人機經過交叉點處的時間為[08:01:45, 08:02:05, 08:02:25,…],滿足間隔10 s的安全約束。每條航路無人機的起飛間隔為40 s,返程間隔為40 s,返回配送點間隔為40 s,均滿足10 s的安全約束。因此,無人機在航路網絡中運行時,飛行路徑上的沖突可以通過飛行時刻的調配進行解脫,使得無人機可以在起降點和航路交叉口順序通行。

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

3.2.2 算法分析

基于6條航路信息得到08:00-10:00時刻表最大可安排數量Ca,航路R1有175條時刻,航路R2有174條時刻,航路R3有234條時刻,航路R4有233條時刻,航路R5有175條時刻,航路R6有174條時刻。采用對照實驗法對參數取值進行分析,取每條航路Ca數量的飛行計劃作為初始實驗數據,為每條飛行計劃分配一組可用時刻?；诒疚奶岢龅娘w行計劃預先調配算法,對于每條航路,生成無沖突時刻表,將每條飛行計劃的任務屬性量化為綜合優(yōu)先級并排序,依據排序結果由高到低分配時刻。根據目標函數,預先調配過程考慮每條飛行計劃的運輸、延誤成本和綜合優(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)先級高的計劃會先進行排序,分配到較早的時刻,出現延誤的可能性小,因此成本低。對于每條航路,待分配計劃的數量越多,每條飛行計劃的成本越高,由于航路R5距離最短,每條計劃的成本最低,航路R6距離最長,每條計劃的成本最高。

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

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

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

3.2.3 參數分析

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

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

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

4 結 論

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

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