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

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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

1.2.1 決策變量

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

(1)

1.2.2 綜合優(yōu)先級(jí)

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

(2)

(3)

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

1.2.3 目標(biāo)函數(shù)

(1) 運(yùn)輸成本

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

(4)

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

(2) 延誤成本

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

(5)

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

minC=

(6)

1.2.4 約束條件

(1) 空域可用時(shí)間

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

(7)

(2) 起飛時(shí)間間隔

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

(8)

(9)

(3) 到達(dá)時(shí)間間隔

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

(10)

(11)

式中:ΔTarr表示起降點(diǎn)連續(xù)兩架無人機(jī)的到達(dá)時(shí)間間隔。

(4) 交叉時(shí)間間隔

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

(12)

(5) 唯一性

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

(13)

(14)

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

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

(15)

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

(7) 無人機(jī)性能

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

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

(16)

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

(17)

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

2 算法設(shè)計(jì)

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

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

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

步驟 2生成無沖突時(shí)刻表。

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

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

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

3 算例仿真與分析

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

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

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

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

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

3.2 仿真結(jié)果分析

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

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

表2 航路R1時(shí)刻表Table 2 Schedules of R1

表3 航路R2時(shí)刻表Table 3 Schedules of R2

表4 航路R5時(shí)刻表Table 4 Schedules of R5

表5 航路R6時(shí)刻表Table 5 Schedules of R6

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

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

3.2.2 算法分析

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

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

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

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

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

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

3.2.3 參數(shù)分析

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

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

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

4 結(jié) 論

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

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