城市區域多物流無人機協同任務分配

李 翰, 張洪海, 張連東, 劉 皞

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

0 引 言

隨著社會生活節奏的加快,城市物流需求量越來越大,對配送要求越來越高,物流無人機這種低成本、高靈活的運輸載具越來越受到人們的青睞。同時,當前正處于新冠病毒肆虐期間,減少不必要的外出和人際接觸成為阻斷疫情傳播的重要方式,進一步促進了無人機物流配送的發展,無人機物流已經成為全球物流業發展的重大趨勢之一[1-2]。相較于單無人機,多無人機通過協同能夠更高效地完成任務,符合城市無人機物流配送發展趨勢。而多機執行任務往往具有范圍大、數量多等特點,因此必須要考慮協同任務分配問題,其本質為建立無人機與任務目標之間的對應關系[3-5],實現全局層面的路徑規劃。

國內外眾多專家學者對多無人機協同任務分配問題進行過研究。文獻[6]提出了一種以無人機總巡航距離和使用無人機數量最少為目標的優化模型,并提出了多目標進化算法進行求解。文獻[7]針對多無人作戰飛機協同任務分配問題建立了一種擴展的多目標整數規劃模型,采用量子粒子群優化(quantum particle swarm optimization, QPSO)算法求解最優方案。文獻[8]針對異構多無人機完成攻擊和毀傷評估任務的協同任務分配問題,提出了一種引力搜索算法與遺傳算法相結合的混合算法,仿真結果表明,該算法可以快速、穩定地找到最佳解決方案。文獻[9]以無人機能耗最小為目標函數,采用改進的聚類算法求解,通過數值模擬和物理實驗表明,該方法可以為多無人機任務分配提供一種合理可行的解決方案。文獻[10]建立協同多任務分配問題模型,采用多余負載競拍方案減少非法劣解,通過實數編碼建立粒子和實際分配方案之間的映射關系,解決實際分配問題。文獻[11]針對反雷達作戰中異構無人機編隊協同任務分配的特點,提出了一種考慮時間窗的改進混合整數線性規劃任務分配算法。文獻[12]將多無人機協同任務分配問題轉化為車輛路徑規劃問題,采用一種基于神經網絡的自組織特征映射方法來解決任務分配問題,并與蟻群算法進行比較,結果表明了該方法具有可行性和有效性。文獻[13]采用分布式任務規劃策略,同時無人機在規劃過程中進行評估,對不合理的任務分配結果進行重新規劃。文獻[14]考慮無人機可在站點進行充電的特點,提出了混合整數線性規劃模型和滾動任務分配啟發式算法,并在島嶼區域進行了驗證。文獻[15]建立帶有時間窗約束和無人機性能約束的物流運輸任務分配模型,并改進粒子群算法求解。文獻[16]針對多架無人機進行載貨運輸的協同任務分配場景,提出了分布式控制器來保證固定的編隊,仿真結果驗證了該方法能夠保障多無人機安全運輸貨物。文獻[17]考慮了有限通信帶寬條件下的多無人機組隊任務分配問題,改進了基于一致性的競拍算法(consensus-based bundle algorithm, CBBA),增加判斷機制來確保任務分配的唯一性,以達到將多無人機分配給同一任務的目的。文獻[18]提出了一種新的匈牙利方法來解決多任務分配問題,其中無人機的數量小于任務的數量,仿真結果表明該算法在所有情況下的性能均優于CBBA。文獻[19]針對反雷達作戰中異構無人機編隊協同任務分配的特點,提出了一種考慮時間窗的改進混合整數線性規劃任務分配算法。文獻[20]針對異構固定翼多無人機協同任務分配問題,提出了一種多類型基因染色體編碼策略的改進遺傳算法,通過與隨機搜索法、蟻群算法和粒子搜索算法相比,表明該算法具有更好的優化性能。文獻[21]研究了一個基于無人機/無人值守地面車輛混合系統的復雜多任務問題,以完成任務所消耗的時間和能量最小化為目標,并提出了一種改進的動態規劃算法,仿真結果表明該方法能夠有效地減少時間和能量消耗。文獻[22]針對應急救援下多無人機任務分配問題,提出了一種新的魚類啟發的多無人機任務分配算法(簡稱為FIAM),實驗結果表明FIAM算法能夠保持穩定的運行時間和減少平均救援時間,并大幅增加獲救幸存者的百分比。文獻[23]主要研究多無人機動態任務的實時分配問題,提出了一種基于agent的無人機群動態任務實時分配算法,根據大量的實驗結果表明,該算法能夠解決動態任務的實時任務分配問題,實現無人機群最佳作戰性能。文獻[24]針對有限時間約束下的三維多任務規劃問題,提出了一種改進的蟻群算法,該算法通過引入變維向量系數和轉移概率的時間自適應因子,降低了算法在次解集中的搜索概率,提高了算法的收斂速度。文獻[25]提出了一種新的基于自適應參數調整和雙向搜索的蟻群優化算法以求解多無人機協同任務分配問題,仿真結果表明該方法不僅可以有效地規劃合理的航跡,而且可以解決不確定性問題,提高了多無人機的協同作戰能力。

上述研究均提出了多無人機任務分配方法,但多是從軍用作戰無人機角度開展研究[7-8,10-11,14,19-20,23-25],部分研究則是轉化為物流配送車輛調配規劃問題[6,12,15,21],考慮影響因素較為單一。而在城市環境中進行物流配送需要考慮多種影響因素:一方面,城市物流配送任務點多、時效性強,需要充分發揮無人機靈活性強、速度快的優勢,降低配送成本;另一方面,城市環境復雜,人口密集,作為新興運載工具,在利用無人機進行配送時更要注重安全問題。如何綜合考慮這些因素以對多無人機進行合理的任務分配仍然有待研究。

本文基于城市物流配送實際,考慮物流無人機性能、物流配送時效性、無人機飛行可靠性等影響因素,以最小化經濟成本、時間損失、飛行風險為目標函數,構建代價最小的多約束多無人機物流任務分配模型,設計改進的QPSO (improved QPSO, IQPSO)算法,以獲得最佳的任務分配方案。

1 物流無人機任務分配模型

1.1 問題描述與相關假設

假設某城市區域存在若干個物流需求點且位置已知,采用多架性能各異、可垂直起降的充電旋翼無人機進行物流配送。每架執行配送任務的無人機均從同一配送中心出發,完成所有任務后均返回配送中心。無人機出發后路徑固定不變,不再接受新的任務指派。為了將物流配送任務在時間上和空間上最優地分配給多架無人機,需要在執行任務前進行合理的任務分配。城市區域多目標多機配送示意圖如圖1所示。

圖1 城市區域多目標多物流無人機配送示意圖Fig.1 Schematic diagram of multi-target and multiple logisticsUAVs distribution in urban areas

1.2 多機協同任務分配模型

1.2.1 決策變量

多無人機多目標任務分配的實質是為每架執行任務的無人機分配一條任務執行序列。設所有可被選用的無人機集合為U={U1,U2,…,UN}(簡記為Ui);所有任務集合為T={T1,T2,…,TM,T0}(簡記為Tj),其中T0為第(M+1)個任務(即有TM+1=T0),表示執行任務的無人機最終必須返回配送中心;{T1,T2,…,TM}表示需要執行的M個物流配送任務(M>N)。因此模型任務分配決策變量xij為

(1)

1.2.2 任務分配目標函數

(1) 經濟成本

追求更低的配送成本是城市物流配送的重要目標,經濟性是物流無人機配送的優勢之一。無人機配送經濟成本Cs包括無人機配送運輸成本Cs1和無人機管理成本Cs2。

配送運輸成本是指無人機在配送過程中產生的費用,包括電池能耗、折舊維護等費用,表達式為

(2)

式中:ηi表示無人機Ui的單位距離的運輸成本;Lij為無人機Ui從當前位置飛至任務Tj的歐氏距離;特別地,無人機返回配送中心的任務TM+1所產生的運輸成本也需要考慮在內。

此外,根據民航局發布的《輕小無人機運行規定咨詢通告》,用于物流配送的無人機應予以有效管控,需要考慮無人機管理成本,表達式為

(3)

式中:cfi是指無人機Ui的管理成本;vi是指無人機Ui的飛行速度。

因此,采用物流無人機進行物流配送的經濟成本Cs表達式為

Cs=Cs1+Cs2

(4)

(2) 延遲懲罰

配送時效性是物流運輸所必須考慮的因素,顧客對物流配送的投訴多集中于時間超時。在城市實際物流配送中,顧客往往希望下單之后能夠盡快送到,因此設置為單邊軟時間窗,若配送晚于客戶要求的最晚時刻則存在延遲懲罰。設物流配送任務Tj可接受的時間窗為[0,Timej](返回配送中心無時間窗),若無人機在時間窗內將貨物送達(到達并完成卸貨),則無延遲懲罰;若無人機晚于最晚送達時間則存在懲罰,且延誤時間越長,延遲懲罰越大。延遲懲罰Cτ的表達式為

(5)

(6)

(7)

(3) 安全風險

作為一種新興的運載工具,安全性是采用無人機進行物流配送時必須要考慮的因素。需要從整個配送線路層面進行分析。編號為U1、U2的兩架無人機從配送中心出發后,其配送路線之間相互獨立,互不影響彼此的可靠性,類似于并聯系統;而對于某一架無人機而言,飛行可靠性受配送線路上任務點數量和配送距離的影響,任務數量越多,飛行距離越長則剩余電量越少,可靠性越低,類似于串聯系統。物流無人機配送串并聯線路系統示意圖如圖2所示。

圖2 物流無人機配送系統串并聯線路示意圖Fig.2 Schematic diagram of series and parallel lines of logisticsUAVs’ distribution system

設無人機可靠性為Cr,風險性為Cd,無人機配送安全風險表達式為

Cd=1-Cr

(8)

(9)

(10)

綜上所述,本模型的目標函數C為

minC=α1Cs+α2Ct+α3Cd

(11)

式中:α1、α2、α3分別表示經濟成本、延遲懲罰、安全風險的權重系數,且有α1+α2+α3=1。

1.2.3 任務分配約束條件

(1) 配送任務約束

物流無人機需要完成所有物流配送任務,同時每個物流配送任務只能由某一架無人機執行一次,滿足約束為

(12)

(13)

(2) 貨物載重約束

物流無人機在執行任務時所載貨物質量不能超過載荷限制,滿足約束為

(14)

式中:qj表示任務Tj貨重;qi表示無人機Ui的載荷;qi(max)表示無人機Ui的最大載重。

(3) 飛行距離約束

每架無人機的航程有限,飛行距離不能超過最大航程,滿足約束為

(15)

2 IQPSO算法

2.1 QPSO算法

QPSO算法[26]是孫俊于2004年提出的優化算法,借鑒量子力學中粒子行為特點,通過蒙特卡羅隨機模擬方式來獲得粒子位置,較好地改進了粒子群優化(particle swarm optimization, PSO)算法[27]搜索效率低、易陷入局部最優的缺陷。算法表達式為

(16)

pij(t)=ρpin(t)+(1-ρ)pg(t)

(17)

(18)

式中:u、ρ是在[0,1]上均勻分布的隨機數;pmbest是種群平均最好位置;pξ(t)是第t次迭代時粒子個體的最優位置;pg(t)是第t次迭代時群體的最優位置;pij(t)是第t次迭代時粒子個體最優位置與粒子群體最優位置之間一個隨機位置;Q是種群粒子的數目;W是粒子的維度;β是慣性權重(也稱為收縮-擴張參數),是影響QPSO算法收斂速度的一個重要參數,可以為固定值,也可隨著迭代次數動態變化。目前大多數學者對慣性權重采用線性遞減策略得到迭代時的慣性權重值,表達式如下:

(19)

式中:βmax與βmin分別表示慣性權重的上下邊界;t表示當前迭代次數;tmax表示最大迭代次數。通常β從1線性遞減至0.5時能取得較好的結果。

2.2 IQPSO算法設計

傳統QPSO算法雖然在一定程度上提升了算法性能,但依然存在以下問題:① 未對粒子種群初始值的選取做出規定。粒子初始化位置非常重要,合理的初始化可以增強搜索的多樣性,有利于搜尋最優解;若選取不當則會使得算法很難搜索到全局最優解。② 在進行多次迭代時,易出現大量粒子趨同性,從而陷入局部最優解。③ 單個粒子搜索能力不強,算法全局搜索效率不高。

針對傳統算法存在的不足,本文設計了以下改進方案:① 借鑒混沌理論,采用均勻化級聯Logistic映射來初始化粒子,增強粒子的多樣性和搜索遍歷性;② 通過高斯概率分布引入擾動,對粒子進行變異;③ 設計自適應慣性權重處理方法,根據粒子的適應度好壞賦予不同粒子不同的慣性權重,以此提高粒子整體的搜索效率。

2.2.1 均勻化級聯Logistic映射

1963年美國氣象學家Edward Norton Lorenz提出混沌理論,指出混沌系統最重要的特性是具有隨機性和遍歷性。隨機性使得搜索能夠避免陷入局部最優,遍歷性能夠使迭代產生的解覆蓋目標區域內所有的點,可以實現以任意精度逼近真實的最優解[28-29]。由于混沌系統的隨機性、遍歷性等特點,可以將混沌理論與QPSO算法相結合,以此提高算法的性能。Logistic映射是一種經典的混沌映射,數學表達式如下:

rn+1=μrn(1-rn)

(20)

式中:rn∈[0,1];μ∈[0,4]稱為Logistic參數,當μ=4時,序列呈現出滿映射狀態,數值遍布整個值域空間。但是普通Logistic映射分布還不夠均勻,所以本文在此基礎上采用改進的均勻化級聯 Logistic映射方式[30],對每個粒子位置進行初始化,表達式為

(21)

(22)

采用均勻化級聯Logistic映射在[0,1]上完全遍歷而且分布均勻,故可以有效提高種群的多樣性和搜索的遍歷性。

2.2.2 基于高斯分布的粒子變異

針對粒子的聚集導致算法陷入局部最優解的問題,通過高斯概率分布來引入粒子擾動,進行粒子變異。表達式如下:

pm(t)=pmbest+εH

(23)

式中:pm(t)是種群平均最好位置變異后的位置;ε是預先規定的參數;H是滿足均值為0,方差為1的高斯分布。則原粒子位置表達式(16)變為

(24)

本文設置粒子群的變異范圍隨著代數的增加而降低,即在尋優初期作用于所有粒子,中期作用于部分粒子,后期則不再變異,促使粒子能夠在最優解鄰近區域進行精細搜索。高斯變異粒子作用范圍與迭代次數關系如圖3所示。

圖3 高斯變異粒子作用范圍與迭代次數關系Fig.3 Relationship between the action range of Gauss mutation particles and iteration number

2.2.3 自適應慣性權重

在QPSO算法中慣性權重的大小影響全局搜索能力與局部搜索能力。傳統上對慣性權重的取值方式有固定取值、線性遞減、非線性遞減等。目前最常用的方法為線性遞減,如式(19)所示。這種方法可以在迭代后期改善局部搜索的精度,存在合理性。但是在該方法中,同一代的粒子具有相同的慣性權重,不存在搜索能力的區分;如果算法在迭代過程中發生早熟,會使粒子很難跳出局部最優點,因此存在缺陷。

綜合以上討論,本文基于前人研究[31],采用自適應慣性權重的賦值方法,根據粒子適應度值的優劣來賦予不同粒子不同的適應度值。對于適應度好的粒子,慣性權重適當減小,注重尋找周圍值;適應度差的粒子,慣性權重適當增大,重點尋找其他位置。這樣每個粒子以不同的速度且有目標地向全局最優解的方向和位置移動,從而使算法的全局搜索能力與運行效率能夠得到提高,表達式為

(25)

式中:βmax為設定的慣性權重最大值;βmin為設定的慣性權重最小值;fit(x)是粒子當前的適應度;fitworst是種群最差粒子的適應度;fitbest是種群最好粒子的適應度。

2.2.4 粒子編碼方式

在粒子群算法中,每個粒子就是一個備選解,多個粒子協同進化尋優。尋求合適的編碼方式來建立物流無人機任務分配方案與粒子對應關系,是應用粒子群算法求解問題的關鍵。本文采用實數編碼的方式對粒子進行編碼:設粒子維度W等于任務數量M,每個維度代表一個待執行的任務;粒子數值在[1,N+1)內變化,相同的整數部分表示同一架無人機執行任務,小數部分數值越大執行順序越靠前;而每個任務只對應一架無人機。通過計算適應度值判定整個任務計劃分配的優劣。任務分配方案與粒子間的映射關系示意圖如圖4所示。

圖4 任務分配方案與粒子間的映射關系示意圖Fig.4 Schematic diagram of mapping relationship between task allocation scheme and particles

2.2.5 改進算法流程

IQPSO算法流程的具體步驟如下。

步驟 1建立粒子群,設定粒子群粒子數目Q、慣性權重上界βmax和下界βmin、迭代次數tmax等,采用均勻化級聯Logistic映射初始化每個粒子的位置。

步驟 2根據編碼方式對粒子進行解碼,根據多無人機任務分配數學模型,計算每個粒子的適應度值。

步驟 3尋找種群在搜索過程中所出現的個體最優位置pin和種群最優位置pg,記錄其對應的適應度值,并根據式(18)求得粒子群的平均最優位置pmbest。

步驟 4判斷是否滿足進行基于高斯分布的粒子變異的條件,若滿足則按照式(24)進行粒子位置變異和位置更新;否則轉到步驟5。

步驟 5不進行粒子變異,按式(16)更新粒子位置。

步驟 6判斷是否滿足結束條件(達到最大迭代次數),若滿足則退出循環,輸出粒子群所得的最優個體和對應的適應度值;否則轉到步驟2,進入下一次迭代。

3 仿真驗證

3.1 仿真環境及參數設置

為驗證本文模型和算法的有效性、合理性,使用Visual Studio 2019進行仿真實驗。由于當前物流無人機配送仍處于測試或試運行階段,各項成本的具體數據屬于各公司的保密范疇,故本文僅對無人機的配送成本作粗略估計,從理論層面對模型和算法進行仿真驗證。假設某配送中心共有8架性能各異的無人機可被選用,參數設置如表1所示;共需要執行20個任務點的物流配送,配送點分布如圖5所示，參數設置如表2所示;其他實驗參數設置如表3所示。

表1 無人機參數

表2 物流配送任務點參數

表3 其他參數

圖5 物流配送任務點布局Fig.5 Logistics distribution task point layout

因為所建模型的3個子目標函數的取值范圍存在較大的量級差別,所以在進行仿真實驗時,對每個子目標函數值采用min-max標準化方法,使其取值落在[0,1]之間,表達式為

(26)

式中:f(x)max和f(x)min分別是各個目標函數的最大值和最小值,f(x)是子目標函數實際值,f′(x)是歸一化后的數值。

3.2 仿真結果分析

為了比較算法性能,分別采用QPSO、IQPSO、遺傳算法3種算法對所建模型進行求解。為公平比較,所有算法迭代次數相同,算法的種群規模亦保持一致。為避免偶然性,每個算法獨立運行50次,每次進行200次迭代,取歸一化后的平均值,記錄每個算法所得最終結果如表4所示。

表4 3種算法實驗結果比較

由表4可知,3種算法的適應度值分別為0.145 5、0.136 9、0.146 1。與QPSO和遺傳算法相比,IQPSO算法的代價值分別下降了5.9%和6.3%,改進算法結果優勢顯著;而且改進算法在各個子目標函數均保持了較好結果,驗證了改進算法的有效性和合理性。將IQPSO算法仿真實驗中最優粒子對應的任務分配方案記錄于表5,可以看出該任務分配方案共選用了7架無人機,通過協同合作完成了物流配送任務,且各架無人機均滿足自身航程和載重約束要求,進一步驗證了算法的合理性。根據表5最佳任務分配方案,其中配送順序中0表示配送中心,飛行時長包括卸貨時間。為形象描述每架無人機的任務執行順序和飛行時間,繪制物流無人機飛行時序圖,如圖6所示。圖中橫坐標軸表示任務時間,從無人機自配送中心起飛后開始計時;縱坐標軸表示任務編號,所有無人機按照任務分配方案依序執行任務,較粗的條塊表示無人機在任務處的卸貨時長。

表5 最佳任務分配方案

圖6 物流無人機飛行時序Fig.6 Flight time sequential of logistics UAVs

3.3 參數設置分析

目標函數權重{α1,α2,α3}和算法種群規模Q取值會對求解結果產生影響,因此采用對照實驗法對參數取值進行分析。

3.3.1 目標函數權重分析

城市物流配送首先要保證安全,故安全風險權重α3不變,分析經濟成本權重α1和延遲懲罰權重α2取值對結果的影響,進行21組對照實驗,每組實驗重復50次取平均值。將實驗數據記錄于表6,繪制變化趨勢如圖7。結合表6和圖7進行分析可知,隨著經濟成本α1增大,經濟成本在波動中逐漸下降;延遲懲罰則表現為逐漸增加的變化;安全風險略有下降的趨勢;算法時長有所波動,但是變化不大。基于構建模型的目標函數并考慮算法時長,以實驗10所得結果為最佳,則最優代價權重值為α1=0.225,α2=0.275,α3=0.500。

圖7 目標函數權重值的影響Fig.7 Influence of objective function weight value

表6 不同目標函數權重對任務分配結果的影響

3.3.2 算法種群規模分析

固定上述最優目標函數權重系數不變,分析算法種群規模Q的取值對結果的影響。在該規劃環境下進行12組對照實驗,每組實驗重復50次取平均值,將實驗數據記錄于表7,繪制變化趨勢如圖8。結合表7和圖8進行分析可知,隨著種群規模Q增大,經濟成本、延遲懲罰和安全風險的數值雖有起伏,但是從整體看來均呈現逐漸下降的趨勢。與此同時,算法時長則表現為近似線性增加的變化。顯然種群規模越大,搜索的結果越多,越有可能獲得更好的任務分配結果,然而卻要付出算法時間的代價。而且從第5組之后的實驗組,各個子目標下降幅度很小,但是算法運行時間卻越來越長。綜合上述分析,基于構建模型的目標函數并合理考慮算法時長影響,以實驗6所得結果為最佳,則最優種群規模為Q=150。

表7 不同種群規模對任務分配結果的影響

圖8 算法種群規模權重值的影響Fig.8 Influence of algorithm population size on weight value

4 結 論

本文基于城市區域多無人機多配送目標場景,構建了以經濟成本最小、延遲懲罰最少、安全風險最低為目標函數的多機協同任務分配模型,貼合城市區域物流配送實際。在傳統QPSO算法的基礎上,融入均勻化級聯 Logistics 映射、高斯擾動和自適應慣性權重等方式設計IQPSO算法。仿真實驗表明,改進算法較傳統算法所得結果更優,而且能夠跳出局部最優解,可有效地獲得最佳任務分配方案。本文方法可用于多物流無人機任務分配,且規劃結果受目標函數權重系數、算法種群規模等參數影響。在不同環境和規劃要求下,可采用本文參數設置分析方法進行分析得到最佳參數值。