城市區(qū)域多物流無人機(jī)協(xié)同任務(wù)分配

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

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

0 引 言

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

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

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

本文基于城市物流配送實(shí)際,考慮物流無人機(jī)性能、物流配送時(shí)效性、無人機(jī)飛行可靠性等影響因素,以最小化經(jīng)濟(jì)成本、時(shí)間損失、飛行風(fēng)險(xiǎn)為目標(biāo)函數(shù),構(gòu)建代價(jià)最小的多約束多無人機(jī)物流任務(wù)分配模型,設(shè)計(jì)改進(jìn)的QPSO (improved QPSO, IQPSO)算法,以獲得最佳的任務(wù)分配方案。

1 物流無人機(jī)任務(wù)分配模型

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

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

圖1 城市區(qū)域多目標(biāo)多物流無人機(jī)配送示意圖Fig.1 Schematic diagram of multi-target and multiple logisticsUAVs distribution in urban areas

1.2 多機(jī)協(xié)同任務(wù)分配模型

1.2.1 決策變量

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

(1)

1.2.2 任務(wù)分配目標(biāo)函數(shù)

(1) 經(jīng)濟(jì)成本

追求更低的配送成本是城市物流配送的重要目標(biāo),經(jīng)濟(jì)性是物流無人機(jī)配送的優(yōu)勢之一。無人機(jī)配送經(jīng)濟(jì)成本Cs包括無人機(jī)配送運(yùn)輸成本Cs1和無人機(jī)管理成本Cs2。

配送運(yùn)輸成本是指無人機(jī)在配送過程中產(chǎn)生的費(fèi)用,包括電池能耗、折舊維護(hù)等費(fèi)用,表達(dá)式為

(2)

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

此外,根據(jù)民航局發(fā)布的《輕小無人機(jī)運(yùn)行規(guī)定咨詢通告》,用于物流配送的無人機(jī)應(yīng)予以有效管控,需要考慮無人機(jī)管理成本,表達(dá)式為

(3)

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

因此,采用物流無人機(jī)進(jìn)行物流配送的經(jīng)濟(jì)成本Cs表達(dá)式為

Cs=Cs1+Cs2

(4)

(2) 延遲懲罰

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

(5)

(6)

(7)

(3) 安全風(fēng)險(xiǎn)

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

圖2 物流無人機(jī)配送系統(tǒng)串并聯(lián)線路示意圖Fig.2 Schematic diagram of series and parallel lines of logisticsUAVs’ distribution system

設(shè)無人機(jī)可靠性為Cr,風(fēng)險(xiǎn)性為Cd,無人機(jī)配送安全風(fēng)險(xiǎn)表達(dá)式為

Cd=1-Cr

(8)

(9)

(10)

綜上所述,本模型的目標(biāo)函數(shù)C為

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

(11)

式中:α1、α2、α3分別表示經(jīng)濟(jì)成本、延遲懲罰、安全風(fēng)險(xiǎn)的權(quán)重系數(shù),且有α1+α2+α3=1。

1.2.3 任務(wù)分配約束條件

(1) 配送任務(wù)約束

物流無人機(jī)需要完成所有物流配送任務(wù),同時(shí)每個(gè)物流配送任務(wù)只能由某一架無人機(jī)執(zhí)行一次,滿足約束為

(12)

(13)

(2) 貨物載重約束

物流無人機(jī)在執(zhí)行任務(wù)時(shí)所載貨物質(zhì)量不能超過載荷限制,滿足約束為

(14)

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

(3) 飛行距離約束

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

(15)

2 IQPSO算法

2.1 QPSO算法

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

(16)

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

(17)

(18)

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

(19)

式中:βmax與βmin分別表示慣性權(quán)重的上下邊界;t表示當(dāng)前迭代次數(shù);tmax表示最大迭代次數(shù)。通常β從1線性遞減至0.5時(shí)能取得較好的結(jié)果。

2.2 IQPSO算法設(shè)計(jì)

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

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

2.2.1 均勻化級聯(lián)Logistic映射

1963年美國氣象學(xué)家Edward Norton Lorenz提出混沌理論,指出混沌系統(tǒng)最重要的特性是具有隨機(jī)性和遍歷性。隨機(jī)性使得搜索能夠避免陷入局部最優(yōu),遍歷性能夠使迭代產(chǎn)生的解覆蓋目標(biāo)區(qū)域內(nèi)所有的點(diǎn),可以實(shí)現(xiàn)以任意精度逼近真實(shí)的最優(yōu)解[28-29]。由于混沌系統(tǒng)的隨機(jī)性、遍歷性等特點(diǎn),可以將混沌理論與QPSO算法相結(jié)合,以此提高算法的性能。Logistic映射是一種經(jīng)典的混沌映射,數(shù)學(xué)表達(dá)式如下:

rn+1=μrn(1-rn)

(20)

式中:rn∈[0,1];μ∈[0,4]稱為Logistic參數(shù),當(dāng)μ=4時(shí),序列呈現(xiàn)出滿映射狀態(tài),數(shù)值遍布整個(gè)值域空間。但是普通Logistic映射分布還不夠均勻,所以本文在此基礎(chǔ)上采用改進(jìn)的均勻化級聯(lián) Logistic映射方式[30],對每個(gè)粒子位置進(jìn)行初始化,表達(dá)式為

(21)

(22)

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

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

針對粒子的聚集導(dǎo)致算法陷入局部最優(yōu)解的問題,通過高斯概率分布來引入粒子擾動(dòng),進(jìn)行粒子變異。表達(dá)式如下:

pm(t)=pmbest+εH

(23)

式中:pm(t)是種群平均最好位置變異后的位置;ε是預(yù)先規(guī)定的參數(shù);H是滿足均值為0,方差為1的高斯分布。則原粒子位置表達(dá)式(16)變?yōu)?/p>

(24)

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

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

2.2.3 自適應(yīng)慣性權(quán)重

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

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

(25)

式中:βmax為設(shè)定的慣性權(quán)重最大值;βmin為設(shè)定的慣性權(quán)重最小值;fit(x)是粒子當(dāng)前的適應(yīng)度;fitworst是種群最差粒子的適應(yīng)度;fitbest是種群最好粒子的適應(yīng)度。

2.2.4 粒子編碼方式

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

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

2.2.5 改進(jìn)算法流程

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

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

步驟 2根據(jù)編碼方式對粒子進(jìn)行解碼,根據(jù)多無人機(jī)任務(wù)分配數(shù)學(xué)模型,計(jì)算每個(gè)粒子的適應(yīng)度值。

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

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

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

步驟 6判斷是否滿足結(jié)束條件(達(dá)到最大迭代次數(shù)),若滿足則退出循環(huán),輸出粒子群所得的最優(yōu)個(gè)體和對應(yīng)的適應(yīng)度值;否則轉(zhuǎn)到步驟2,進(jìn)入下一次迭代。

3 仿真驗(yàn)證

3.1 仿真環(huán)境及參數(shù)設(shè)置

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

表1 無人機(jī)參數(shù)

表2 物流配送任務(wù)點(diǎn)參數(shù)

表3 其他參數(shù)

圖5 物流配送任務(wù)點(diǎn)布局Fig.5 Logistics distribution task point layout

因?yàn)樗Ｐ偷?個(gè)子目標(biāo)函數(shù)的取值范圍存在較大的量級差別,所以在進(jìn)行仿真實(shí)驗(yàn)時(shí),對每個(gè)子目標(biāo)函數(shù)值采用min-max標(biāo)準(zhǔn)化方法,使其取值落在[0,1]之間,表達(dá)式為

(26)

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

3.2 仿真結(jié)果分析

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

表4 3種算法實(shí)驗(yàn)結(jié)果比較

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

表5 最佳任務(wù)分配方案

圖6 物流無人機(jī)飛行時(shí)序Fig.6 Flight time sequential of logistics UAVs

3.3 參數(shù)設(shè)置分析

目標(biāo)函數(shù)權(quán)重{α1,α2,α3}和算法種群規(guī)模Q取值會(huì)對求解結(jié)果產(chǎn)生影響,因此采用對照實(shí)驗(yàn)法對參數(shù)取值進(jìn)行分析。

3.3.1 目標(biāo)函數(shù)權(quán)重分析

城市物流配送首先要保證安全,故安全風(fēng)險(xiǎn)權(quán)重α3不變,分析經(jīng)濟(jì)成本權(quán)重α1和延遲懲罰權(quán)重α2取值對結(jié)果的影響,進(jìn)行21組對照實(shí)驗(yàn),每組實(shí)驗(yàn)重復(fù)50次取平均值。將實(shí)驗(yàn)數(shù)據(jù)記錄于表6,繪制變化趨勢如圖7。結(jié)合表6和圖7進(jìn)行分析可知,隨著經(jīng)濟(jì)成本α1增大,經(jīng)濟(jì)成本在波動(dòng)中逐漸下降;延遲懲罰則表現(xiàn)為逐漸增加的變化;安全風(fēng)險(xiǎn)略有下降的趨勢;算法時(shí)長有所波動(dòng),但是變化不大?；跇?gòu)建模型的目標(biāo)函數(shù)并考慮算法時(shí)長,以實(shí)驗(yàn)10所得結(jié)果為最佳,則最優(yōu)代價(jià)權(quán)重值為α1=0.225,α2=0.275,α3=0.500。

圖7 目標(biāo)函數(shù)權(quán)重值的影響Fig.7 Influence of objective function weight value

表6 不同目標(biāo)函數(shù)權(quán)重對任務(wù)分配結(jié)果的影響

3.3.2 算法種群規(guī)模分析

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

表7 不同種群規(guī)模對任務(wù)分配結(jié)果的影響

圖8 算法種群規(guī)模權(quán)重值的影響Fig.8 Influence of algorithm population size on weight value

4 結(jié) 論

本文基于城市區(qū)域多無人機(jī)多配送目標(biāo)場景,構(gòu)建了以經(jīng)濟(jì)成本最小、延遲懲罰最少、安全風(fēng)險(xiǎn)最低為目標(biāo)函數(shù)的多機(jī)協(xié)同任務(wù)分配模型,貼合城市區(qū)域物流配送實(shí)際。在傳統(tǒng)QPSO算法的基礎(chǔ)上,融入均勻化級聯(lián) Logistics 映射、高斯擾動(dòng)和自適應(yīng)慣性權(quán)重等方式設(shè)計(jì)IQPSO算法。仿真實(shí)驗(yàn)表明,改進(jìn)算法較傳統(tǒng)算法所得結(jié)果更優(yōu),而且能夠跳出局部最優(yōu)解,可有效地獲得最佳任務(wù)分配方案。本文方法可用于多物流無人機(jī)任務(wù)分配,且規(guī)劃結(jié)果受目標(biāo)函數(shù)權(quán)重系數(shù)、算法種群規(guī)模等參數(shù)影響。在不同環(huán)境和規(guī)劃要求下,可采用本文參數(shù)設(shè)置分析方法進(jìn)行分析得到最佳參數(shù)值。