李紹斌， 姜大立， 楊西龍， 劉書俊

(1. 陸軍勤務(wù)學(xué)院軍事物流系， 重慶 401311； 2. 陸軍勤務(wù)學(xué)院油料系， 重慶 401311)

當(dāng)前，戰(zhàn)時前線部隊(duì)的物資保障主要采取車輛配送方式，由于車輛的機(jī)動能力不足且極易受戰(zhàn)場交通環(huán)境的限制，難以滿足緊急情況下物資保障任務(wù)的要求；而且在情況緊急下出動直升機(jī)完成物資器材的配送任務(wù)時，由于目標(biāo)暴露大，對直升機(jī)與機(jī)組人員的安全威脅也大。無人機(jī)配送是解決戰(zhàn)場物資“最后一公里”保障的有效方式，其既能完成戰(zhàn)時需求物資器材的應(yīng)急配送，同時又可最大限度地保證后勤保障人員的生命安全，因此未來戰(zhàn)場物資的保障將越來越趨向于無人化配送。其中，多無人機(jī)配送任務(wù)分配決策是提升無人機(jī)配送能力的核心基礎(chǔ)之一，其目的是將戰(zhàn)場物資保障任務(wù)在時間和空間上最優(yōu)地分配到具體的各架無人機(jī)，以充分利用現(xiàn)有資源快速高效地完成物資配送任務(wù)，實(shí)現(xiàn)最佳的物資配送效能，最大限度地提高和維持部隊(duì)的戰(zhàn)斗力。

目前，國內(nèi)外學(xué)者對無人機(jī)任務(wù)分配問題的研究已取得了一定的研究成果。如：符小衛(wèi)等[1]研究了通信約束對偵察無人機(jī)多機(jī)協(xié)同搜索任務(wù)分配的影響，提出了一種通信約束條件下的多無人機(jī)協(xié)同偵察目標(biāo)分配方法；李原等[2]對存在偵察時間窗口與偵察器材限制的多基地、多無人機(jī)協(xié)同偵察任務(wù)進(jìn)行規(guī)劃，對無人機(jī)基地、偵察器材類型以及偵察目標(biāo)序列同時進(jìn)行優(yōu)化；周小程等[3]重點(diǎn)研究了分布式控制結(jié)構(gòu)的無人機(jī)任務(wù)分配，針對分布式控制結(jié)構(gòu)的特點(diǎn)，提出了基于拍賣機(jī)制原理的動態(tài)任務(wù)分配算法；SHETTY等[4]對單基地不同型號打擊無人機(jī)的任務(wù)分配進(jìn)行求解，同時考慮目標(biāo)點(diǎn)的優(yōu)先級，應(yīng)用禁忌搜索算法求解了模型；楊尚君等[5]以偵察、攻擊、毀傷評估3類無人機(jī)的任務(wù)協(xié)同為目標(biāo)，建立了以最大航程與最長任務(wù)時間為目標(biāo)的任務(wù)分配優(yōu)化模型，并采用改進(jìn)魚群算法求解模型；馬焱等[6]對打擊無人機(jī)的目標(biāo)分配進(jìn)行研究，建立了以目標(biāo)價(jià)值收益、飛行距離、耗彈量成本以及目標(biāo)覆蓋度為目標(biāo)的任務(wù)分配模型，并采用自適應(yīng)煙花算法求解模型。配送無人機(jī)作為當(dāng)前新興的技術(shù)裝備，現(xiàn)有文獻(xiàn)對其配送任務(wù)分配的研究報(bào)道較少，只有少部分文獻(xiàn)對民用物流無人機(jī)的配送任務(wù)規(guī)劃進(jìn)行了研究，如：SONG等[7]對無人機(jī)實(shí)施島嶼貨物配送進(jìn)行了研究，以配送任務(wù)總成本最小為目標(biāo)構(gòu)建了混合整數(shù)優(yōu)化模型；HA等[8]對單基地的無人機(jī)配送任務(wù)分配進(jìn)行了研究，將無人機(jī)配送過程轉(zhuǎn)換為傳統(tǒng)的旅行商問題(Traveling Salesman Problem,TSP)，以配送成本最小化為目標(biāo)構(gòu)建了單基地的無人機(jī)配送任務(wù)分配模型，并以貪婪隨機(jī)自適應(yīng)搜索算法求解了模型；RABTA等[9]對無人機(jī)在應(yīng)急救援“最后一公里”配送中的應(yīng)用進(jìn)行了研究，在無人機(jī)有效載荷和航程的約束下，以無人機(jī)總行駛距離最小化為目標(biāo)，構(gòu)建了混合整數(shù)線性規(guī)劃模型并進(jìn)行了求解。

綜上所述，現(xiàn)有研究對戰(zhàn)場物資無人機(jī)配送任務(wù)分配問題鮮有報(bào)道，配送無人機(jī)在戰(zhàn)場執(zhí)行物資配送任務(wù)的獨(dú)特性，決定了其與偵察無人機(jī)、通信無人機(jī)、打擊無人機(jī)以及民用物流無人機(jī)的任務(wù)分配問題存在差異，配送無人機(jī)具有航時限制、載荷約束，配送過程時效性強(qiáng)、面臨需求點(diǎn)多等實(shí)際情況。因此，針對復(fù)雜戰(zhàn)場環(huán)境下多基地、多無人機(jī)保障多需求點(diǎn)的任務(wù)分配開展研究具有重要的現(xiàn)實(shí)意義。為了更加真實(shí)地描述戰(zhàn)場物資無人機(jī)配送的過程，以多約束條件下的多車場車輛路徑問題(Multi-De-pots Vehicle Routing Problem with Multiple Constraints，MDVRPMC)為基礎(chǔ)，建立符合實(shí)際的戰(zhàn)場物資無人機(jī)配送任務(wù)分配模型。由于傳統(tǒng)算法的計(jì)算量大，求解效率不高，筆者以遺傳算法為基礎(chǔ)，引入克拉克-懷特節(jié)約里程法(Clarke and Wright saving me-thod，C-W saving method，簡稱節(jié)約里程法)和最近鄰算法(the Nearest Neighbor Heuristic，NNH)，有效提升了模型求解的效率，解決了實(shí)際戰(zhàn)場環(huán)境下的多無人機(jī)配送任務(wù)分配問題，實(shí)現(xiàn)了多基地、多無人機(jī)的配送協(xié)同。

1 問題描述與分析假設(shè)

1.1 問題描述

考慮戰(zhàn)場前沿的應(yīng)急補(bǔ)給任務(wù)多、強(qiáng)度大，通常同時面臨多個作戰(zhàn)力量的物資需求。為了緩解單個無人機(jī)保障基地的壓力，以更高效地完成物資配送任務(wù)，通常在戰(zhàn)場前沿的野戰(zhàn)倉庫配屬多個無人機(jī)保障基地，以集群保障模式及時響應(yīng)作戰(zhàn)力量的物資需求。在戰(zhàn)場物資無人機(jī)配送任務(wù)分配問題中，無人機(jī)基地的數(shù)量與位置是確定的，每個無人機(jī)基地都儲存了足量的保障物資，基地內(nèi)配備具有一定載荷的無人機(jī)，來負(fù)責(zé)為各作戰(zhàn)單元補(bǔ)給物資，作戰(zhàn)單元的物資需求以及位置坐標(biāo)可通過指揮信息系統(tǒng)獲得。為了更加直觀地描述戰(zhàn)場物資無人機(jī)配送的過程，將多基地、多無人機(jī)的配送過程進(jìn)行簡化，如圖1所示。

在該戰(zhàn)場物資配送問題中，共有B1、B2兩個無人機(jī)基地，其地理坐標(biāo)已知，配送無人機(jī)的最大載荷為14個標(biāo)準(zhǔn)單位，各作戰(zhàn)單元的物資需求量以及地理坐標(biāo)也是確定的，其中5號作戰(zhàn)單元的地理坐標(biāo)為(10,15)，其物資需求量為8個標(biāo)準(zhǔn)單位。在該示例中，需求點(diǎn)1-6的保障任務(wù)由基地B1完成，需求點(diǎn)7-12的保障任務(wù)由基地B2完成，2基地都分別形成了2個閉環(huán)路線，其中每個閉環(huán)路線代表一架配送無人機(jī)保障任務(wù)的集合，閉環(huán)路線中的箭頭方向代表無人機(jī)在單次配送任務(wù)中的保障順序。由示例可以看出:2個無人機(jī)基地共派出了4架配送無人機(jī)，按順序完成了12個需求點(diǎn)的物資保障任務(wù)。

無人機(jī)的多任務(wù)協(xié)同分配模型有2個常用的目標(biāo)函數(shù)：各無人機(jī)總的飛行航程最小和實(shí)施所有配送任務(wù)的時間最短[10]。前者能有效降低基地內(nèi)執(zhí)行配送的無人機(jī)數(shù)量，使戰(zhàn)場物資的配送能同時兼顧經(jīng)濟(jì)性和軍事性，參與保障的配送無人機(jī)數(shù)目越少，則相應(yīng)所需的人力、物力也就越少，保障成本相應(yīng)也越低，同時，可以最大限度地為后續(xù)保障任務(wù)預(yù)留無人機(jī)，增加后續(xù)可利用的配送無人機(jī)數(shù)。但該目標(biāo)函數(shù)將使部分無人機(jī)執(zhí)行的配送任務(wù)要比其他無人機(jī)多，從而使距任務(wù)點(diǎn)較遠(yuǎn)的無人機(jī)分配不到保障任務(wù)，導(dǎo)致完成所有配送任務(wù)的時間增加。后者追求完成所有配送任務(wù)的總時間最短，以最短的時間完成各戰(zhàn)術(shù)單元的緊急保障任務(wù)，確保戰(zhàn)場物資配送的效率，但該目標(biāo)函數(shù)將造成除最后完成配送任務(wù)的無人機(jī)之外，其余無人機(jī)的航程均變長，而且使參與配送的無人機(jī)數(shù)量大幅增多。由此可見：2個目標(biāo)函數(shù)相互之間是互斥的，因此在實(shí)際戰(zhàn)場物資配送過程中，決策者需視具體的情況權(quán)衡2個目標(biāo)的權(quán)重，在滿足供需平衡以及無人機(jī)性能約束的條件下，優(yōu)化無人機(jī)配送任務(wù)的分配方案，使物資資源能按需、保質(zhì)、保量地完成配送，同時使完成配送任務(wù)的時間最短，且出動配送無人機(jī)的數(shù)量也最少。

1.2 模型假設(shè)

多基地、多無人機(jī)戰(zhàn)場物資配送任務(wù)的分配是一個復(fù)雜的NP-Hard(Non-deterministic Polynomial-Hard)問題，涉及的目標(biāo)多、影響因素復(fù)雜，為了更加方便地進(jìn)行定量化研究，同時最大限度地確保與戰(zhàn)場物資無人機(jī)配送的實(shí)際相符合，對模型構(gòu)建作如下合理的假設(shè)：

1) 配送無人機(jī)基地作為戰(zhàn)術(shù)補(bǔ)給的前沿陣地，應(yīng)具備滿足該作戰(zhàn)方向物資保障的能力，其儲備有足夠的補(bǔ)給物資，不存在配送時物資缺額的情況。

2) 戰(zhàn)術(shù)型配送無人機(jī)相對輕便，運(yùn)送的物資量小，在作戰(zhàn)后勤保障中執(zhí)行應(yīng)急保障任務(wù)。為滿足所有作戰(zhàn)分隊(duì)的物資緊急需求，通常保證基地內(nèi)配備的無人機(jī)數(shù)量足夠。因此，假設(shè)基地內(nèi)擁有足夠的無人機(jī)可隨時應(yīng)對物資的緊急需求，同時基于無人機(jī)單次運(yùn)輸?shù)奈镔Y量相對較小，對基地內(nèi)的物流設(shè)備能力不會產(chǎn)生太大壓力，在模型中暫不考慮物資備貨、裝卸的時間。

3) 戰(zhàn)時無人機(jī)的配送能夠通過后勤保障指揮信息系統(tǒng)實(shí)時地感知戰(zhàn)場保障態(tài)勢，結(jié)合實(shí)時的物資需求信息，在無人機(jī)實(shí)施配送任務(wù)前已將不同的物資資源進(jìn)行組套化包裝，因此模型將不考慮物資的種類區(qū)分，以基數(shù)化、標(biāo)準(zhǔn)化的物資量進(jìn)行計(jì)算。

4) 配送無人機(jī)只有在其載荷超過需求點(diǎn)的需求時才實(shí)施配送保障行動，當(dāng)需求點(diǎn)的物資需求量超過無人機(jī)的載荷時，可將該需求點(diǎn)分解為多個具有相同參數(shù)的子需求點(diǎn)，因此，假設(shè)任一戰(zhàn)場需求點(diǎn)只能由一架無人機(jī)負(fù)責(zé)配送保障，且各配送無人機(jī)完成配送任務(wù)后需回到原出發(fā)基地。

2 模型構(gòu)建

MDVRPMC是在多約束條件下將運(yùn)輸物資由多輛車從多個車場向多個需求點(diǎn)運(yùn)輸?shù)膯栴}[11]。本文借鑒MDVRPMC問題對多基地、多無人機(jī)配送任務(wù)分配問題進(jìn)行建模，具體的模型參數(shù)設(shè)置如下：

設(shè){B1,B2,…,BM}為M個無人機(jī)基地的集合，Bm(m=1,2,…,M)之間既可以是上級加強(qiáng)的配送力量，也可以是友鄰保障力量；{A1,A2,…,AN}為N個任務(wù)需求點(diǎn)(任務(wù)節(jié)點(diǎn))的集合，其中Ai、Aj表示2個不同編號的任務(wù)節(jié)點(diǎn)；有k架配送無人機(jī)；dij為任務(wù)節(jié)點(diǎn)Ai與Aj間的距離；Ci為任務(wù)節(jié)點(diǎn)Ai的物資需求量；Q為配送無人機(jī)的最大載荷；v為無人機(jī)的飛行速度；D為配送無人機(jī)的最大航程數(shù)。

1) 決策變量為

2) 約束條件為

(1)

(2)

(3)

(4)

(5)

(6)

其中：式(1)表示任一物資需求點(diǎn)只由一架無人機(jī)進(jìn)行保障；式(2)表示任一無人機(jī)的保障任務(wù)量不能超過其最大載荷；式(3)表示任一無人機(jī)保障任務(wù)行程不能超過其最大航程；式(4)-(6)表示每架配送無人機(jī)均是從基地出發(fā)按順序完成保障任務(wù)后，最終返回基地，確保了每架無人機(jī)配送任務(wù)的連續(xù)性。

記滿足上述配送約束的方案為有效分配方案φ={φ1,φ2,…,φM}，其中φm(m=1,2,…,M)為基地Bm的配送任務(wù)方案;c(s)為有效分配方案的單一保障路線中各任務(wù)節(jié)點(diǎn)的先后順序；nk為保障無人機(jī)k路線上的任務(wù)節(jié)點(diǎn)數(shù)量；gm為基地Bm中無人機(jī)路線的數(shù)量。則

配送無人機(jī)的多任務(wù)協(xié)同分配是在符合戰(zhàn)場實(shí)際的情況下，實(shí)現(xiàn)多無人機(jī)的整體保障效能最大化，通常采用各無人機(jī)飛行的總航程最小和完成所有配送任務(wù)的時間最短來評價(jià)無人機(jī)的協(xié)同保障效能，因此，筆者將其作為評價(jià)配送無人機(jī)協(xié)同保障任務(wù)分配方案優(yōu)劣的重要指標(biāo)。

1) 多無人機(jī)配送的總航程數(shù)最小。多無人機(jī)配送的總航程數(shù)為各基地內(nèi)各架無人機(jī)航程數(shù)之和，即

(7)

式中：c(0)為無人起飛的基地。

2) 多無人機(jī)完成所有配送任務(wù)的時間最短。多基地、多無人機(jī)完成所有配送任務(wù)的時間以各基地中完成配送任務(wù)時間最長的基地進(jìn)行計(jì)算，其中單個基地完成配送任務(wù)的時間以基地內(nèi)配送時間最長的無人機(jī)進(jìn)行計(jì)算，因此以各基地中最長的配送時間作為多基地多無人機(jī)完成所有配送任務(wù)時間最短指標(biāo)指標(biāo)值，即

(8)

各基地中最長的配送時間決定了完成所有配送任務(wù)的時間，假設(shè)無人機(jī)的飛行速率為恒定的，則無人機(jī)完成配送任務(wù)的時間與其飛行距離成正比，因此式(8)中的無人機(jī)配送時間可采用飛行里程來表征。

根據(jù)式(7)、(8)，可得目標(biāo)函數(shù)為

(9)

式中：w1,w2∈[0,1]，為2個子目標(biāo)的權(quán)重系數(shù)，且w1+w2=1。

以式(9)為目標(biāo)函數(shù)對每次生成的有效分配方案φm進(jìn)行評估，其中目標(biāo)函數(shù)值最小的為最優(yōu)配送無人機(jī)協(xié)同保障任務(wù)分配方案。

3 模型求解流程

遺傳算法(Genetic Algorithm，GA)是在模擬自然界生物的遺傳與進(jìn)化過程中,形成的自適應(yīng)全局優(yōu)化搜索算法，能夠自動獲取和積累有關(guān)搜索空間的知識，并自適應(yīng)地控制搜索過程以求得最優(yōu)解。其搜索尋優(yōu)的自組織、自適應(yīng)和自學(xué)習(xí)性等特點(diǎn)，使其成為求解NP-Hard問題的有效方法[12]。應(yīng)用GA求解多基地、多無人機(jī)的戰(zhàn)場物資配送任務(wù)分配問題，首先，需將其分解細(xì)化為3部分：1)將保障任務(wù)分配給各無人機(jī)基地，主要解決各任務(wù)節(jié)點(diǎn)分群問題；2)對歸屬同一保障基地的各任務(wù)節(jié)點(diǎn)進(jìn)行分組，主要解決基地內(nèi)各無人機(jī)的任務(wù)分工問題；3)確定同一組中各任務(wù)節(jié)點(diǎn)的保障順序，主要解決無人機(jī)保障任務(wù)的順序問題，具體如圖2所示。

由此可知：多基地、多無人機(jī)的戰(zhàn)場物資配送任務(wù)分配問題是由任務(wù)分組、任務(wù)分工以及任務(wù)順序3個子問題組成，其中任何一個子問題都較為復(fù)雜，以至于求解難度較大。由于傳統(tǒng)遺傳算法的求解效率不高，筆者將遺傳算法與節(jié)約里程法、最近鄰算法相結(jié)合，形成混合遺傳算法(Hybrid Genetic Algorithm，HGA)來提升模型求解的效率，求解流程如圖3所示。

由圖3可知，HGA算法與GA算法的主要區(qū)別在于初始解與初始種群的生成:在GA算法中，每個初始解均隨機(jī)產(chǎn)生，生成的初始種群也是隨機(jī)的；在HGA算法中，初始解的生成過程引入了節(jié)約里程法與最近鄰算法，針對性地優(yōu)化提升了初始解的質(zhì)量，生成的初始種群更接近最優(yōu)解。遺傳算法求解的實(shí)質(zhì)是隨機(jī)化搜索尋優(yōu)的過程，初始種群相對較優(yōu)，意味著算法尋優(yōu)的空間與范圍大大縮小，尋優(yōu)的方向性得到增強(qiáng)。因此，在相同條件下，HGA算法得到最優(yōu)解的概率將大大增加，同時收斂的速度更快。

4 模型求解步驟

4.1 產(chǎn)生初始解與初始種群

為使模型解能直觀地反映各基地、各無人機(jī)的保障任務(wù)順序，首先以無人機(jī)保障任務(wù)的順序?qū)θ旧w進(jìn)行編碼，每條保障路線代表1架無人機(jī)的任務(wù)安排。以單架無人機(jī)基地為例，某時刻對編號1-6的任務(wù)節(jié)點(diǎn)進(jìn)行物資配送，優(yōu)化的無人機(jī)保障方案為(0 2 5 3 0 6 1 4 0)，由此可知：需要2架無人機(jī)實(shí)施物資配送(或者單架無人機(jī)實(shí)施2階段的物資配送)，其中一架無人機(jī)從基地(以0表示)出發(fā)，按順序完成任務(wù)節(jié)點(diǎn)2、5、3的任務(wù)后返回基地；另一架無人機(jī)的保障路線也是從基地出發(fā)，按順序完成6、1、4的保障任務(wù)后也返回基地。同理，當(dāng)有m個無人機(jī)基地參與保障時，每條染色體中將包含著m個子片段序列，多基地的染色體實(shí)數(shù)編碼如圖4所示。

圖4 染色體編碼

由圖3可知，HGA初始化階段分為3個步驟：

1) 完成所有任務(wù)節(jié)點(diǎn)的分組工作，要求模型目標(biāo)函數(shù)中完成配送任務(wù)的時間最短，因此基于任務(wù)節(jié)點(diǎn)與基地之間的距離遠(yuǎn)近將各任務(wù)節(jié)點(diǎn)分配至距離最近的無人機(jī)基地，即

(1) 當(dāng)d(Ai,Bm)=min(d(Ai,B1),d(Ai,B2),…,d(Ai,BM)), 其中，m=1,2,…,M,i=1,2,…,N時，Ai分配給Bm基地；

(2) 當(dāng)d(Ai,B1)=d(Ai,B2)=…=d(Ai,BM)時，Ai隨機(jī)分配給任一基地 。

其中：

(10)

為任務(wù)節(jié)點(diǎn)Ai至基地Bm的距離。

2) 解決同屬于一個基地的保障任務(wù)分工問題，使完成配送任務(wù)的總航程數(shù)最小。采用節(jié)約里程法將各個基地負(fù)責(zé)的任務(wù)節(jié)點(diǎn)分配給基地內(nèi)各架無人機(jī)。節(jié)約里程法的經(jīng)典節(jié)約量計(jì)算公式為[13]

S(Ai,Aj)=d(Ai,Bm)+d(Aj,Bm)-d(Ai,Aj)，

(11)

式中：S(Ai,Aj)為節(jié)約的航程數(shù)。

計(jì)算各基地中所有任務(wù)節(jié)點(diǎn)兩兩之間節(jié)約的航程數(shù)，在滿足無人機(jī)載荷與航程約束的條件下，將節(jié)約航程數(shù)較大的2個節(jié)點(diǎn)安排在同一架無人機(jī)的單次保障路線中。

3) 解決單架無人機(jī)保障路線中各任務(wù)節(jié)點(diǎn)的保障順序，即明確具體無人機(jī)的保障任務(wù)順序，這實(shí)質(zhì)上是一個典型的TSP問題。采用最近鄰算法(NNH)確定無人機(jī)保障任務(wù)的順序，最近鄰算法(NNH)的原理是在同屬于一個保障基地、一條保障路線的任務(wù)節(jié)點(diǎn)中，隨機(jī)選擇一個任務(wù)節(jié)點(diǎn)作為初始任務(wù)節(jié)點(diǎn)，在剩下的任務(wù)節(jié)點(diǎn)中選擇與初始任務(wù)節(jié)點(diǎn)距離最近的任務(wù)節(jié)點(diǎn)作為第2個節(jié)點(diǎn)；依次類推，直至該路線中最后一個任務(wù)節(jié)點(diǎn)的任務(wù)完成，無人機(jī)返回基地。以圖1為例說明HGA初始可行解的產(chǎn)生過程，如圖5所示，生成的一個初始可行解為(5 4 1 3 6 2 8 9 12 10 7 11)。按照初始可行解的生成方法，隨機(jī)生成一個規(guī)模為R的初始種群，并以種群中的初始可行解作為迭代的初始點(diǎn)。

4.2 選擇操作

以目標(biāo)函數(shù)為適應(yīng)度函數(shù)，計(jì)算種群中各染色體的適應(yīng)度值，根據(jù)適應(yīng)度值的大小選擇染色體。筆者采用輪盤賭的方法選擇染色體，通常適應(yīng)度值越大的染色體，其被選中的概率越大。設(shè)fg為第g個染色體的適應(yīng)度值，則第g個染色體被選擇的概率

(12)

4.3 交叉操作

交叉算子是遺傳算法中最重要的操作之一。對染色體上的基因進(jìn)行重組生成新的個體，通過交叉操作可大幅提升遺傳算法的尋優(yōu)能力。在混合遺傳算法中，每次按一定的概率pc，采用傳統(tǒng)順序交叉(order crossover)方式產(chǎn)生2個子代，具體步驟如圖6所示。首先，在父代染色體1中隨機(jī)選擇一段基因(6 2 8 9)，將該段基因復(fù)制于子代染色體1的相同位置；然后，將父代染色體2中相同的基因剔除，剩下的基因片段從左至右重新排列；最后，將重新排列的基因組按從左至右的順序，依次填入子代染色體1中的空缺位置，形成完整的子代染色體1：(1 4 7 10 6 2 8 9 5 12 3 11)。同理，選擇父代染色體2中相應(yīng)位置的一段基因，復(fù)制至子代染色體2的相同位置，剔除父代染色體1中相同的基因，采用相同的方法產(chǎn)生子代染色體2。

4.4 變異操作

變異算子是對種群中的個體基因值進(jìn)行變動。變異算子具有局部隨機(jī)搜索能力，可加速向最優(yōu)解收斂；同時通過基因突變，生成的新的子代染色體，維持了種群的多樣性，進(jìn)而防止出現(xiàn)早熟收斂現(xiàn)象，因此設(shè)置合理的變異概率pm，可提高算法尋優(yōu)能力，同時也可避免陷入早熟收斂。由于單一變異算子存在一定的隨機(jī)性、盲目性，變異的效果得不到保證，為了在算法運(yùn)行過程中提升變異的質(zhì)量，筆者同時采取交換變異策略與倒置變異策略。

1) 交換變異策略。以一定的變異概率在種群中選擇一條父代染色體，隨機(jī)選擇3個基因；列出3個基因的所有排列組合，每一個排列組合都作為一個子代。設(shè)w1=w2=0.5，則交換變異策略操作過程如圖7所示。

2)倒置變異策略。以設(shè)定的變異概率在種群中選擇一條父代染色體，在父代染色體中隨機(jī)選擇一串基因片段，對基因片段的順序進(jìn)行倒置生成新的子代染色體，以確保種群的多樣性。倒置變異策略操作如圖8所示。

4.5 結(jié)束條件

當(dāng)達(dá)到設(shè)定的迭代次數(shù)時，算法終止。并對染色體進(jìn)行解碼，生成近似最優(yōu)解。

5 算例分析

為了驗(yàn)證模型與算法的合理性和有效性，通過仿真算例對GA與HGA兩種算法的計(jì)算效果進(jìn)行對比。隨機(jī)設(shè)置2種情況：30個、50個任務(wù)節(jié)點(diǎn)，2個無人機(jī)基地。無人機(jī)基地與各任務(wù)節(jié)點(diǎn)的位置分布如圖9所示，其中各任務(wù)節(jié)點(diǎn)的物資需求量已知，配送無人機(jī)的運(yùn)輸性能確定，無人機(jī)的性能約束以及供需平衡要求明確。

設(shè)置種群大小為100，當(dāng)任務(wù)節(jié)點(diǎn)數(shù)為30時，設(shè)置迭代次數(shù)為200；當(dāng)任務(wù)節(jié)點(diǎn)數(shù)為50時，設(shè)置迭代次數(shù)為500；交叉概率pc=0.8，變異概率pm=0.05。利用GA與HGA算法分別求解30個任務(wù)節(jié)點(diǎn)的任務(wù)分配，其收斂曲線對比如圖10所示，相對應(yīng)的任務(wù)分配結(jié)果如圖11所示。

由圖10可知：GA算法優(yōu)化的適應(yīng)度值始于297.65，在進(jìn)化至110代時收斂于183.22；HGA方法優(yōu)化的適應(yīng)度值始于196.81，在進(jìn)化至100代時收斂于172.98。由圖11可知，2種算法求解得到的任務(wù)分配結(jié)果不同，如：在GA優(yōu)化算法中任務(wù)節(jié)點(diǎn)2、18由同一架無人機(jī)保障，而在HGA算法中任務(wù)節(jié)點(diǎn)2、20由同一架無人機(jī)配送，任務(wù)節(jié)點(diǎn)18則與任務(wù)節(jié)點(diǎn)21由同一架無人機(jī)配送。圖11中的閉環(huán)表示1架無人機(jī)完成的配送任務(wù)，其中GA算法求解的任務(wù)分配結(jié)果顯示2個無人機(jī)基地共需出動無人機(jī)13架次，HGA算法求解的任務(wù)分配結(jié)果中2個無人機(jī)基地共需出動無人機(jī)12架次。

采用GA與HGA算法分別求解50個任務(wù)節(jié)點(diǎn)的任務(wù)分配，其收斂曲線對比如圖12所示，相對應(yīng)的任務(wù)分配結(jié)果如圖13所示。由圖12可知：GA算法優(yōu)化的適應(yīng)度值始于525.68，在進(jìn)化至300代時收斂于330.76；HGA算法優(yōu)化的適應(yīng)度值始于345.26，在進(jìn)化至270代時收斂于313.02。由圖13可知：2種算法求解得到的配送任務(wù)分配方案不同，對應(yīng)的2個基地需出動無人機(jī)的數(shù)量均為21架次。

由圖10、12可以看出：HGA算法收斂曲線的始點(diǎn)均遠(yuǎn)遠(yuǎn)低于GA算法的收斂曲線，說明HGA算法可產(chǎn)生質(zhì)量更優(yōu)的初始解與初始種群。這是由于HGA算法中采用了節(jié)約里程法與最近鄰算法產(chǎn)生初始解，同時HGA算法的收斂曲線整體都遠(yuǎn)低于GA算法，HGA算法的優(yōu)化效果優(yōu)于傳統(tǒng)的GA算法。因此，節(jié)約里程法與最近鄰算法對初始解、初始種群的優(yōu)化在配送任務(wù)分配決策中起著至關(guān)重要的作用。為了更加直觀地反映HGA算法的優(yōu)勢，引入優(yōu)化率α與提升率β指標(biāo)，計(jì)算公式分別為

(13)

(14)

通過求解優(yōu)化率指標(biāo)α與提升率指標(biāo)β，得出2種方法的具體性能對比，如表1所示。

表1 HGA與GA算法性能的對比

由表1可以看出：HGA算法的優(yōu)化率分別為12.11%、9.34%，顯著低于GA算法的38.44%、37.08%。這主要是由于HGA算法的初始種群、初始解的質(zhì)量明顯優(yōu)于傳統(tǒng)GA算法隨機(jī)生成的初始解，使得HGA算法優(yōu)化的起點(diǎn)更高，更接近于全局最優(yōu)解，可優(yōu)化的幅度空間相對較小，因此，HGA算法優(yōu)化的幅度低于傳統(tǒng)GA算法。提升率指標(biāo)反映了保障30個任務(wù)節(jié)點(diǎn)時HGA算法提升解質(zhì)量的幅度達(dá)到5.59%，保障50個任務(wù)節(jié)點(diǎn)時HGA算法提升解質(zhì)量的幅度達(dá)到5.36%，在同等條件下HGA算法的尋優(yōu)能力更強(qiáng)。同時，從達(dá)到穩(wěn)定的進(jìn)化代數(shù)也可發(fā)現(xiàn)HGA算法的收斂速度更快，計(jì)算效率更高。綜上所述，混合遺傳算法能更好地求解多基地、多無人機(jī)戰(zhàn)場物資協(xié)同配送任務(wù)分配優(yōu)化問題。

6 結(jié)論

研究探索戰(zhàn)場物資無人機(jī)配送任務(wù)分配的優(yōu)化方法，提高無人機(jī)協(xié)同配送的效率效益，是實(shí)現(xiàn)無人機(jī)在未來戰(zhàn)場物資配送中常態(tài)化運(yùn)行的重要基礎(chǔ)。筆者重點(diǎn)研究了多基地、多無人機(jī)的戰(zhàn)場物資協(xié)同配送任務(wù)分配優(yōu)化問題，以多約束條件下的多車場車輛路徑問題為基礎(chǔ)，建立了多基地、多無人機(jī)的協(xié)同配送優(yōu)化模型，構(gòu)造了融合節(jié)約里程法、最近鄰算法的混合遺傳算法求解模型，并與傳統(tǒng)遺傳算法的收斂性、優(yōu)化質(zhì)量進(jìn)行了對比分析。結(jié)果表明：混合遺傳算法在相同條件下的求解質(zhì)量優(yōu)于傳統(tǒng)遺傳算法，在一定迭代代數(shù)下可得到更為滿意的解，這對于解決戰(zhàn)場物資無人機(jī)配送任務(wù)分配問題具有重要的參考意義。但該模型中未考慮實(shí)際戰(zhàn)場物資保障過程中多種運(yùn)輸工具協(xié)同配送的問題，下一步將重點(diǎn)圍繞無人機(jī)與傳統(tǒng)車輛聯(lián)合配送任務(wù)分配優(yōu)化問題展開研究。