基于混合遺傳算法的多基地多無人機戰場物資配送任務分配

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

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

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

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

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

1 問題描述與分析假設

1.1 問題描述

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

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

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

1.2 模型假設

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

1) 配送無人機基地作為戰術補給的前沿陣地，應具備滿足該作戰方向物資保障的能力，其儲備有足夠的補給物資，不存在配送時物資缺額的情況。

2) 戰術型配送無人機相對輕便，運送的物資量小，在作戰后勤保障中執行應急保障任務。為滿足所有作戰分隊的物資緊急需求，通常保證基地內配備的無人機數量足夠。因此，假設基地內擁有足夠的無人機可隨時應對物資的緊急需求，同時基于無人機單次運輸的物資量相對較小，對基地內的物流設備能力不會產生太大壓力，在模型中暫不考慮物資備貨、裝卸的時間。

3) 戰時無人機的配送能夠通過后勤保障指揮信息系統實時地感知戰場保障態勢，結合實時的物資需求信息，在無人機實施配送任務前已將不同的物資資源進行組套化包裝，因此模型將不考慮物資的種類區分，以基數化、標準化的物資量進行計算。

4) 配送無人機只有在其載荷超過需求點的需求時才實施配送保障行動，當需求點的物資需求量超過無人機的載荷時，可將該需求點分解為多個具有相同參數的子需求點，因此，假設任一戰場需求點只能由一架無人機負責配送保障，且各配送無人機完成配送任務后需回到原出發基地。

2 模型構建

MDVRPMC是在多約束條件下將運輸物資由多輛車從多個車場向多個需求點運輸的問題[11]。本文借鑒MDVRPMC問題對多基地、多無人機配送任務分配問題進行建模，具體的模型參數設置如下：

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

1) 決策變量為

2) 約束條件為

(1)

(2)

(3)

(4)

(5)

(6)

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

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

配送無人機的多任務協同分配是在符合戰場實際的情況下，實現多無人機的整體保障效能最大化，通常采用各無人機飛行的總航程最小和完成所有配送任務的時間最短來評價無人機的協同保障效能，因此，筆者將其作為評價配送無人機協同保障任務分配方案優劣的重要指標。

1) 多無人機配送的總航程數最小。多無人機配送的總航程數為各基地內各架無人機航程數之和，即

(7)

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

2) 多無人機完成所有配送任務的時間最短。多基地、多無人機完成所有配送任務的時間以各基地中完成配送任務時間最長的基地進行計算，其中單個基地完成配送任務的時間以基地內配送時間最長的無人機進行計算，因此以各基地中最長的配送時間作為多基地多無人機完成所有配送任務時間最短指標指標值，即

(8)

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

根據式(7)、(8)，可得目標函數為

(9)

式中：w1,w2∈[0,1]，為2個子目標的權重系數，且w1+w2=1。

以式(9)為目標函數對每次生成的有效分配方案φm進行評估，其中目標函數值最小的為最優配送無人機協同保障任務分配方案。

3 模型求解流程

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

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

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

4 模型求解步驟

4.1 產生初始解與初始種群

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

圖4 染色體編碼

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

1) 完成所有任務節點的分組工作，要求模型目標函數中完成配送任務的時間最短，因此基于任務節點與基地之間的距離遠近將各任務節點分配至距離最近的無人機基地，即

(1) 當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(Ai,B1)=d(Ai,B2)=…=d(Ai,BM)時，Ai隨機分配給任一基地 。

其中：

(10)

為任務節點Ai至基地Bm的距離。

2) 解決同屬于一個基地的保障任務分工問題，使完成配送任務的總航程數最小。采用節約里程法將各個基地負責的任務節點分配給基地內各架無人機。節約里程法的經典節約量計算公式為[13]

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

(11)

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

計算各基地中所有任務節點兩兩之間節約的航程數，在滿足無人機載荷與航程約束的條件下，將節約航程數較大的2個節點安排在同一架無人機的單次保障路線中。

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

4.2 選擇操作

以目標函數為適應度函數，計算種群中各染色體的適應度值，根據適應度值的大小選擇染色體。筆者采用輪盤賭的方法選擇染色體，通常適應度值越大的染色體，其被選中的概率越大。設fg為第g個染色體的適應度值，則第g個染色體被選擇的概率

(12)

4.3 交叉操作

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

4.4 變異操作

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

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

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

4.5 結束條件

當達到設定的迭代次數時，算法終止。并對染色體進行解碼，生成近似最優解。

5 算例分析

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

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

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

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

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

(13)

(14)

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

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

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

6 結論

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