基于改進變鄰域搜索算法的多批次協同任務規劃

呂東許，李少梅，周炤，馬京振，溫伯威

基于改進變鄰域搜索算法的多批次協同任務規劃

呂東許，李少梅，周炤，馬京振，溫伯威

（信息工程大學，鄭州 450001）

對多批次協同任務進行分析與建模，并研究任務規劃的求解算法。以車載裝備多批次協同執行任務為例，綜合考慮時間協同、任務區域協同和補給區域協同約束，以暴露時間最短為目標函數建立模型，并提出一種改進變鄰域搜索算法進行求解，該方法根據鄰域的優化能力自動調整迭代時選擇該鄰域的概率。仿真結果表明，改進策略在不降低最優解質量的情況下，能夠避免標準變鄰域搜索算法后期易出現某些鄰域長時間無法尋找到最優解的情況，有效提高了算法的效率。變鄰域搜索算法可以解決多批次任務規劃問題，改進后的算法減少了后期對優化能力不強的鄰域的搜索次數，有效提升了算法效率。

多批次協同任務；變鄰域搜索；自適應鄰域選擇；任務分配；路徑規劃

多批次協同任務指根據一組特定的約束條件，為實現某個目標函數最優，將某項任務分解成多個子任務并分配給系統中的各個實體分批次完成的過程。多批次協同策略被廣泛應用于多個領域，例如工業生產線物料配送[1]、特種精細化工生產[2]、物流配送[3]、多武器協同火力打擊[4]、無人機集群偵查搜索[5]和通信保障[6]等。由于各領域的個性化需求不同，相對應的約束條件也不盡相同，多批次協同任務規劃問題呈現出多樣性特點。文中以車載裝備多批次協同執行某任務為例，通過考慮時間協同、任務區域協同和補給區域協同約束，以暴露時間最短為目標，基于道路網探討多批次協同任務規劃問題。

對于協同任務規劃，國內外學者近年來進行了廣泛的研究。姚軍等[7]針對多無人機協同目標搜索進行研究，提出了基于粒子群遺傳算法的多無人機不確定區域協同路徑搜索方法，該算法中的協同策略是指無人機搜索過程中實時分享傳感器捕捉的目標信息，以減少重復搜索。董晨等[8]針對多傳感器–多武器協同防空任務規劃，設計了基于時段優選拼接和分支定界法的協同任務規劃算法，該算法是精確式算法，對大規模應用場景的求解需要消耗很長時間，因此，僅適用于小規模規劃或者對實時性要求不高的大規模場景。Qin等[9]針對大型車間生產調度問題進行研究，提出了一種混合禁忌搜索的離散多目標灰狼算法，但該算法中的時間窗是固定時間窗，無法根據生產進度對時間窗進行靈活調整。Zhu等[10]針對云制造環境下跨區域分布式制造的特點，提出了大規模多批次任務協同執行的服務組合，將大量任務轉換為并行的多批次子任務執行，并設計了基于差分進化和教與學的混合改進優化算法進行求解。

在軍事上，許多學者針對車載裝備多批次協同任務也從不同方面進行了研究。針對單車多目標導彈發射的路徑規劃，劉偉等[11]提出了基于圖論的多重運算法、首輪淘汰法與基于模糊理論的算法。對于多車多批次導彈火力打擊行動規劃問題，吳閏平等[12]提出了雙層Voronoi圖模型，首先對發射點進行了聚類，由專門的轉載點對其發射點轉載服務，將多中心優化問題轉化為單目標優化問題，但此方法沒有考慮路網結構對車輛行駛時間的影響。Chen等[13]將兩批次火力打擊問題轉化為三階段過程建立模型，并采用0—1規劃分階段進行求解，該方法根據階段順序依次求各階段行駛時間最小的任務方案，其割裂了2次火力打擊的聯系，求得的解不具有全局最優性。

變鄰域搜索算法（Variable Neighborhood Search, VNS）是Mladenovi?等[14]提出的一種元啟發式搜索算法，它在搜索過程中通過對當前解的不同鄰域結構進行深度搜索尋優，并在每次鄰域搜索前通過擾動操作擴展搜索范圍，能夠有效跳出局部最優解，具有較好的魯棒性和有效性，在設施選址[15]、任務調度[16]、路徑規劃[17]等問題的解決中取得了良好的效果。在變鄰域搜索算法后期階段，易出現某些鄰域長時間無法尋找到最優解的情況。為提高變鄰域搜索算法的優化性能，文中提出一種改進變鄰域搜索算法，并通過車載裝備多批次協同執行某任務為實例進行實驗驗證。

1 問題描述與建模

1.1 車載裝備多批次協同執行任務

現代戰爭中，飽和攻擊、批次協同的打擊策略是重要的作戰樣式[18]。車載裝備未受領任務前分布在等待區域，受領任務后行駛至指定任務區域執行第1批次的任務。完成第1批次的任務后每臺車輛需要行駛至補給區域進行補給，完成補給后再行駛至下一批次指定的任務區域執行第2批次任務，之后的任務流程與第1批次任務到第2批次任務的流程一致。具體任務流程見圖1。

車輛在其行駛過程中面臨著衛星、無人機和遠程雷達的偵察威脅。一般而言，被發現概率與被偵察時間是成正比的，因此，在任務籌劃時，需要合理安排各個車輛的行駛路徑與相應區域，使暴露時間最短，降低被偵查設備發現的幾率，以增大生存概率，因此，合理規劃行駛路線以減少暴露時間是車載裝備順利執行任務的關鍵問題。

出于突防和提高目標毀傷效果的需要，同一批次的任務要求同時執行。由于任務執行后可能被偵查到執行任務的區域進而摧毀，為減少損失，應避免使用上一批次使用過的任務區域。另外，在整個任務過程中，要求整體暴露時間最短。

圖1 車載裝備多批次協同執行任務流程

1.2 模型構建

由于第2批次之后每批次的任務流程與第1至第2批次任務一致，故文中以兩批次協同任務為例構建模型，可根據實際情況推廣至任意批次任務。假設參與任務的車輛共臺，平均分布在個等待區域，任務區共有個任務區域、個補給區域。符號說明見表1。

表1 符號說明

Tab.1 Symbol description

1.2.1 條件假設

在實際任務過程中，影響車輛行進的因素很多且不可控，這些不是規劃階段考慮的重點，故作出如下假設：車輛油量足夠，無須在任務時間內加油；不考慮車輛、區域可能發生故障的情況；所有車輛在道路上均以同一速度勻速行駛；不考慮道路轉彎、會車時間；忽略在任務區域執行任務耗費的時間；1個補給區域最多同時對1臺車輛進行補給作業。

1.2.2 決策變量

式中：為階段編號，1,2,3；為車輛編號；為任務區域編號；為補給區域編號。

1.2.3 約束條件

在車載裝備多批次協同任務規劃中，約束條件主要有時間協同約束、任務區域使用協同約束和補給區域使用協同約束。

1）時間協同約束。每一批次所有車輛同時在不同的任務區域執行任務，即臺裝備2個批次執行任務的時刻同為1,2。

2）任務區域使用協同約束。每一批次每臺車輛分配一個任務區域：

每一批次每個任務區域最多只能安排一臺車輛：

連續2個批次每個任務區域最多只能選擇一次：

3）補給區域使用協同約束。在第1批次和第2批次中間必須經過補給區域：

同一時刻，補給區域最多容納1臺車輛：

1.2.4 目標函數

目標函數為整體暴露時間最短，即：

2 算法設計

文中基于標準變鄰域搜索算法，針對兩批次協同任務特點，對算法進行改進。標準變鄰域搜索算法通常由2個部分組成：第1部分為變鄰域下降搜索，是基于鄰域的系統變化來尋找局部最優解；第2個部分為擾動過程，目的是擴展搜索范圍，跳出局部最優。因鄰域結構不同，每個鄰域尋優能力不同，所以在變鄰域搜索的后期階段，經常會有一些鄰域長時間找不到更好的可行解，反復搜索這些鄰域會降低算法的優化效率。文中提出一種鄰域選擇策略，該策略根據每個鄰域的優化情況，自適應調整選擇每個鄰域的概率，能夠減少無效搜索，提高算法效率。

2.1 算法流程

算法流程如圖2所示，步驟如下：

2）產生初始解。隨機或根據一定的策略生成一個初始解init，并將其傳遞給當前解cur，即令cur=init，初始化全局最優解best=init。

圖2 算法流程

2.2 編碼設計

根據車載裝備多批次協同執行任務模型特點，采用正整數編碼方式。編碼由2部分組成，分別對應每批次選擇的任務區域編號和批次間選擇的補給區域編號。每個可行解由一個位的任務區域編碼和一個位的補給區域編碼構成，任務區域編碼前2位表示兩批次分別采用的任務區域編號，其中奇數位表示第1批次使用的任務區域編號，偶數位表示第2批次使用的任務區域編號，若從不同的等待區域出發，則每一批次按照等待區域的順序進行編碼，后?2位表示未被選取的任務區域編號，這是為了使鄰域操作能夠涉及到所有的任務區域。位補給區域編碼表示第1批次和第2批次之間插入的補給區域編號。

如圖3所示，車輛臺數=4，等待區域個數2，任務區域個數10，補給區域個數=3，初始狀態為2個等待區域分別有2臺車輛。現有一個可行解為[2,6,5,9,3,8,1,7,4,10][1,3,2,1]，則表示4臺車輛的路徑分別為1→2→1→6,1→5→3→9,2→3→2→8,2→1→1→7。

圖3 編碼設計

2.3 初始解構造

變鄰域搜索算法的求解性能受初始解的影響較大，根據模型構造一個質量相對較高的初始解能夠有效減少需要的迭代次數。通過模型分析可知，執行第1批次任務前無等待時間，因此，優化目標主要為減少車輛從執行完第1批次任務至執行完第2批次任務耗費的時間。為了得到一個好的初始解，文中采用基于補給區域與任務區域之間時空距離的貪心算法生成，其步驟如下：

1）采用Dijkstra算法，結合車輛行駛速度，計算裝備車輛從各補給區域和等待區域到任務區域的最短時間。

2）初始化已選取任務區域和補給區域為空序列，遍歷補給區域到任務區域的時間矩陣，找到最小時間對應的補給區域和任務區域編號，加入到序列第1批次任務區域位置以及補給區域序列中，并將該任務區域從時間矩陣刪除。用相同的方法遍歷剩余的時間矩陣，依次加入到，直至補給區域序列長度達到，此時補給區域序列初始化完畢。

3）根據補給區域序列，依次在序列第2批次任務區域位置加入到當前補給區域時間最短的任務區域，直至序列長度達到2，最后再把未選擇的任務區域依次加入到。

2.4 鄰域結構設計

在進行鄰域搜索時，按照補給區域替換算子、任務區域交換算子、任務區域逆轉算子、任務區域插入算子的順序進行搜索，擾動過程也使用這些算子。

1）補給區域替換算子。補給區域替換算子指隨機選取補給區域序列中的一個補給區域替換為其他補給區域，若替換后總暴露時間減少，則保留替換操作；否則，取消替換操作。替換操作見圖4。

圖4 補給區域替換操作

2）任務區域交換算子。任務區域交換算子是指隨機選取任務區域序列中的2個任務區域進行互換，若交換后總暴露時間減少，則保留交換操作；否則，取消交換操作。交換操作見圖5。

圖5 任務區域交換操作

3）任務區域逆轉算子。任務區域逆轉算子是指隨機選取任務區域序列中的2個任務區域，對2個位置之間的序列進行逆轉排序，若逆轉后總暴露時間減少，則保留逆轉操作；否則，取消逆轉操作。逆轉操作見圖6。

圖6 任務區域逆轉操作

4）任務區域插入算子。任務區域插入算子指隨機選取任務區域序列中的2個任務區域，將第1個選擇的任務區域插入第2個位置的后面，若插入后總暴露時間減少，則保留插入操作；否則，取消插入操作。插入操作見圖7。

圖7 任務區域插入操作

2.5 自適應鄰域選擇策略

每一輪迭代后，根據各個鄰域變化后的概率進行歸一化處理。為保證每輪迭代至少有1個鄰域被選擇，文中采用當前概率除以各鄰域概率最大值的方法進行歸一化，即：

下一輪迭代時，根據該概率隨機選擇某一個或幾個鄰域進行局部搜索。

3 實驗驗證

3.1 算例設計

3.2 算例求解

采用Matlab編程語言對算法進行實現，根據算例規模進行反復實驗，確定算法參數設置：最大迭代次數為50次，每次迭代各鄰域最大搜索次數為50次。

初始解采用2.3節中的貪心算法生成，初始解對應的目標函數值為171.35 h。分別使用標準變鄰域搜索算法和改進后的變鄰域搜索算法進行10次實驗，記錄每次的最優解和計算時間。實驗從最優解和計算時間兩方面進行對比。

1）最優解對比。20次實驗的最優解對應的總暴露時間、執行兩批次任務的時刻以及運行程序的計算時間如表2—3所示。標準變鄰域搜索算法和自適應變鄰域搜索算法取得的最優解對應的總暴露時間均為108.76 h，且10次最優解的范圍基本一致。限于篇幅，列出最優方案部分路徑如表4所示。表明，雖然經自適應改進后的變鄰域搜索算法在后期跳過了一些鄰域，但對最優解的質量幾乎沒有影響。

圖8 道路網及各點位分布

表2 標準變鄰域搜索算法實驗結果

Tab.2 Experimental Results of standard VNS algorithm

表3 改進變鄰域搜索算法實驗結果

Tab.3 Experimental results of improved VNS algorithm

表4 最優方案中部分車輛行駛路徑

Tab.4 Part of the vehicle maneuvering path in the optimal scheme

2）計算時間對比。標準變鄰域搜索算法10次運行平均用時為24.99 s，改進變鄰域搜索算法10次運行平均用時為12.41 s，可以看出，改進變鄰域搜索算法在計算效率方面具有明顯優勢。由于改進變鄰域搜索算法中每次迭代選擇鄰域的個數與生成的隨機數有關，因此運行時間不穩定，但均比標準變鄰域搜索算法的運行時間短，這將有效提升大規模算例的求解效率。

4 結語

文中針對多批次協同任務規劃問題，以車載裝備批次協同執行任務為例進行了研究。

1）建立了兩批次協同任務模型。以總暴露時間最短為目標函數，綜合分析了任務過程中的批次時間協同、任務區域及補給區域使用協同等約束條件。

2）使用變鄰域搜索算法進行求解，并對原算法進行了改進。根據任務區域到補給區域的時間矩陣，使用貪心算法生成初始解，設計了替換、交換、逆轉、插入等鄰域算子進行局部搜索，為每個鄰域設置了選擇概率，并根據鄰域的優化性能進行更新，提高了算法的效率。

3）通過實例驗證了算法的有效性。實驗結果表明，自適應鄰域選擇策略對最優解的質量沒有影響，但能夠有效地提高算法的效率，這對大規模算例的求解具有重要意義。

4）文中的模型和求解方法具有較強的實際意義和理論意義，對物流配送、無人機協同搜索等其他場景下的多批次協同任務規劃有一定的參考價值。

[1] 方景芳, 葉波, 劉軍. 面向最短路徑的工業包裝生產線時間成本研究[J]. 包裝工程, 2019, 40(9): 120-126.

FANG Jing-fang, YE Bo, LIU Jun. Time Cost of the Shortest Path-Oriented Industrial Packaging Production Line[J]. Packaging Engineering, 2019, 40(9): 120-126.

[2] 于蒙. 基于數據驅動的間歇化工過程批次內和批次間復合優化控制策略研究[D]. 北京: 軍事科學院, 2021: 3-4.

YU Meng. Research on Compound Optimal Control Strategy of Batch Chemical Process Based on Data-Driven[D]. Beijing: Academy of Military Sciences, 2021: 3-4.

[3] 魏江寧. 基于協同物流模式的多批次整車運輸問題與多階段庫存路徑問題研究[D]. 上海: 上海交通大學, 2010: 21-24.

WEI Jiang-ning. Research on Multi-Batch Vehicle Transportation and Multi-Stage Inventory Routing Problem Based on Collaborative Logistics Mode[D]. Shanghai: Shanghai Jiao Tong University, 2010: 21-24.

[4] 王中偉, 裘杭萍, 王智學, 等. 基于攻防博弈的多波次導彈發射路徑規劃[J]. 指揮與控制學報, 2019, 5(1): 63-68.

WANG Zhong-wei, QIU Hang-ping, WANG Zhi-xue, et al. Multi-Shot Missile Launching Path Planning Based on Attack-Defense Game[J]. Journal of Command and Control, 2019, 5(1): 63-68.

[5] CAO Yan, WEI Wan-yu, Bai Yu, et al. Multi-Base Multi-UAV Cooperative Reconnaissance Path Planning with Genetic Algorithm[J]. Cluster Computing, 2019, 22(S3): 5175-5184.

[6] ZHANG Song-ge, ZHOU Jian-shan, TIAN Da-xin, 等. Robust Cooperative Communication Optimization for Multi-UAV-Aided Vehicular Networks[J]. IEEE Wireless Communications Letters, 2021, 10(4): 780-784.

[7] 姚軍, 李思捷, 羅德林, 等. 基于粒子群遺傳算法的多無人機協同路徑搜索[J]. 火力與指揮控制, 2021, 46(8): 59-63.

YAO Jun, LI Si-jie, LUO De-lin, et al. Multiple UAVs Collaboration Path Search Based on Particle Swarm Genetic Algorithm[J]. Fire Control & Command Control, 2021, 46(8): 59-63.

[8] 董晨, 帥逸仙, 周金鵬, 等. 網絡化多傳感器-多武器協同防空任務規劃[J]. 系統工程與電子技術, 2022, 44(12): 3738-3746.

DONG Chen, SHUAI Yi-xian, ZHOU Jin-peng, et al. Cooperative Air Defense Task Planning of Networked Multi-Sensor-Multi-Weapon[J]. Systems Engineering and Electronics, 2022, 44(12): 3738-3746.

[9] QIN Hong-bin, FAN Peng-fei, TANG Hong-tao, et al. An Effective Hybrid Discrete Grey Wolf Optimizer for the Casting Production Scheduling Problem with Multi-Objective and Multi-Constraint[J]. Computers & Industrial Engineering, 2019, 128: 458-476.

[10] ZHU Li-nan, LI Peng-hang, ZHOU Xiao-long. IHDETBO: A Novel Optimization Method of Multi-Batch Subtasks Parallel-Hybrid Execution Cloud Service Composition for Cloud Manufacturing[J]. Complexity, 2019, 2019: 1-21.

[11] 劉偉, 王雪梅, 張博, 等. 戰術導彈發射車最優路徑規劃算法研究[J]. 航空兵器, 2006, 13(5): 19-22.

LIU Wei, WANG Xue-mei, ZHANG Bo, et al. Research on Programming of Optimal Path Algorithm for Tactics Missiles Launch Vehicles[J]. Aero Weaponry, 2006, 13(5): 19-22.

[12] 吳閏平, 劉衛東, 楊萍, 等. 基于雙層Voronoi圖的常規導彈多波次打擊模型[J]. 火力與指揮控制, 2019, 44(12): 163-169.

WU Run-ping, LIU Wei-dong, YANG Ping, et al. Conventional Missile Multi-Strike Model Based on Double-Vononoi Diagram[J]. Fire Control & Command Control, 2019, 44(12): 163-169.

[13] CHEN Chun-mei, Yang Ping, Liu Su-bing. The Mission Planning of Multi-wave Missile Launching Based on 0-1 Integer Programming[C]// International Conference on Artificial Intelligence and Communication Technology., Chongqing, 2020: 260-265.

[14] MLADENOVI? N, HANSEN P. Variable Neighborhood Search[J]. Computers & Operations Research, 1997, 24(11): 1097-1100.

[15] NADAR R A, JHA J K, THAKKAR J J. Strategic Location of Ambulances Under Temporal Variation in Demand and Travel Time Using Variable Neighbourhood Search Based Approach[J]. Computers & Industrial Engineering, 2021, 162: 107780.

[16] LI Xin-yu, GAO Liang, PAN Quan-ke, et al. An Effective Hybrid Genetic Algorithm and Variable Neighborhood Search for Integrated Process Planning and Scheduling in a Packaging Machine Workshop[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2019, 49(10): 1933-1945.

[17] KARAKOSTAS P, SIFALERAS A. A Double-Adaptive General Variable Neighborhood Search Algorithm for the Solution of the Traveling Salesman Problem[J]. Applied Soft Computing, 2022: 108746.

[18] WANG Guang-hui, SUN Xue-feng, ZHANG Li-ping, et al. Saturation Attack Based Route Planning and Threat Avoidance Algorithm for Cruise Missiles[J]. 2011, 22(6): 948-953.

Multi-batch Collaborative Task Planning Based on Improved Variable Neighborhood Search Algorithm

LYU Dong-xu, LI Shao-mei, ZHOU Zhao, MA Jing-zhen, WEN Bo-wei

(Information Engineering University, Zhengzhou 450001, China)

The work aims to analyze and model multi-batch collaborative tasks, and to study the algorithm of task planning. In this work, vehicle-mounted equipment multi-batch collaborative task was analyzed and modeled. In the modeling process, the constraints of time collaboration, task area collaboration and replenishment area collaboration were integrated, and the minimum exposure time was taken as the objective function. The simulation results showed that the improved strategy could avoid the situation that some neighborhoods could not find the optimal solution for a long time in the later stage of the standard variable neighborhood search algorithm, and improve the efficiency of the algorithm without reducing the quality of the optimal solution. It is concluded that the variable neighborhood search algorithm can solve the multi-batch task planning problem. The improved algorithm reduces the search times of the neighborhood with weak optimization ability in the later stage, and effectively improves the efficiency of the algorithm.

multi-batch collaborative task; variable neighborhood search (VNS); adaptive neighborhood selection; task assignments; path planning

O221.6

A

1001-3563(2023)05-0222-08

10.19554/j.cnki.1001-3563.2023.05.028

2022?04?17

國家自然科學基金（42101454，42101455）；河南省中原學者資助項目（202101510001）；智慧中原地理信息技術河南省協同創新中心和時空感知與智能處理自然資源部重點實驗室基金資助項目（212102）

呂東許（1991—），男，碩士生。

李少梅（1974—），女，博士。

責任編輯：曾鈺嬋