【www.zhangdahai.com--其他范文】
吕东许，李少梅，周炤，马京振，温伯威
基于改进变邻域搜索算法的多批次协同任务规划
吕东许，李少梅，周炤，马京振，温伯威
（信息工程大学，郑州 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 车载装备多批次协同执行任务
现代战争中，饱和攻击、批次协同的打击策略是重要的作战样式[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个部分组成：第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.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，可以看出，改进变邻域搜索算法在计算效率方面具有明显优势。由于改进变邻域搜索算法中每次迭代选择邻域的个数与生成的随机数有关，因此运行时间不稳定，但均比标准变邻域搜索算法的运行时间短，这将有效提升大规模算例的求解效率。
文中针对多批次协同任务规划问题，以车载装备批次协同执行任务为例进行了研究。
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—），女，博士。
责任编辑：曾钰婵
猜你喜欢搜索算法邻域算子与由分数阶Laplace算子生成的热半群相关的微分变换算子的有界性数学物理学报(2022年5期)2022-10-09拟微分算子在Hp(ω)上的有界性数学物理学报(2021年2期)2021-06-09改进的和声搜索算法求解凸二次规划及线性规划烟台大学学报（自然科学与工程版）(2021年1期)2021-03-19各向异性次Laplace算子和拟p-次Laplace算子的Picone恒等式及其应用应用数学(2020年2期)2020-06-24稀疏图平方图的染色数上界吉林大学学报（理学版）(2020年3期)2020-05-29一类Markov模算子半群与相应的算子值Dirichlet型刻画数学年刊A辑(中文版)(2018年2期)2019-01-08基于邻域竞赛的多目标优化算法自动化学报(2018年7期)2018-08-20关于-型邻域空间周口师范学院学报(2016年5期)2016-10-17基于汽车接力的潮流转移快速搜索算法电测与仪表(2015年15期)2015-04-12基于逐维改进的自适应步长布谷鸟搜索算法河北科技大学学报(2015年5期)2015-03-11本文来源：http://www.zhangdahai.com/shiyongfanwen/qitafanwen/2023/0917/655448.html
