混合蚁群算法求解无人靶车路径问题研究

丁雨康

摘要：针对无人靶车路径过程中效率低成本高的问题，构建了无人靶车路径问题（Routing Problem of Unmanned Target Vehicle， RPUTV）的混合整数优化模型，该模型以无人靶车行驶路径距离最小化为优化目标。首先，为了提高算法的求解效率和求解质量，在算法的初始阶段引入贪心算法来构建初始解，同时在蚁群算法中引入了邻域搜索算法组成了混合蚁群算法（Hybrid Ant Colony Algorithm，HACA）来提高算法的局部搜索能力。其次，采用标准数据集来验证算法，同其他求解算法进行对比显示，HACA算法求解RPUTV具有更高效性。

关键词：无人靶车 蚁群算法 邻域搜索算法 路径规划

中图分类号：U469.691

Research on Solving the Routing Problem of Unmanned Target Vehicles by the Hybrid Ant Colony Algorithm

DING Yukang

（Anhui Cusp Intelligent Technology Co.， Ltd.， Chuzhou， Anhui Province， 239299 China）

Abstract： In order to solve the problem of low efficiency and high cost in the process of unmanned target vehicle routing， a mixed integer optimization model for the routing problem of unmanned target vehicles （RPUTV） is constructed， which takes the minimization of the driving route distance of unmanned target vehicles as the optimization goal. Firstly， in order to improve the solving efficiency and quality of the algorithm， in the initial stage of the algorithm， the greedy algorithm is introduced to build an initial solution， and the neighborhood search algorithm is introduced into the ant colony algorithm to form a hybrid ant colony algorithm （HACA） to improve the local search ability of the algorithm. Then， the standard data set is used to verify the algorithm， and compared with other solving algorithms， the HACA is more efficient in solving the RPUTV.

Key Words： Unmanned target vehicle; Ant colony algorithm; Neighborhood search algorithm; Path planning

无人靶车路径问题（Routing Problem of Unmanned Target Vehicle， RPUTV）是组合优化领域中热点问题。无人靶车路径问题是由经典车辆路径问题的泛化问题。谢高杨等人[1]首先建立了速度可变的无人靶车路径规划问题，其次将航脚与圆弧形搜索算法结合，提出了改进的A*算法，最后通过仿真实验研究，结果表明：改进的A*算法可以解决不同世俗下的无人靶车路径规划问题。成海飞[2]针对靶车行驶的场景提出了面向越野环境下的无人靶车路径规划问题，同时为了提高路径的搜索质量和效率，使用DWA算法进行算法的全局优化，并根据实时路况进行动态情况设计，最后为了验证所提模型和算法的可靠性，通过MATLAB/Simulink和Carsim联合仿真平台进行仿真实验。肖楠[3]针对移动靶车以传统的轨道行驶，行驶路线单一的问题，设计了基于嵌入式的惯导技术的移动靶车设计，最后通过实验仿真验证了所提方法的有效性。PRUTV现已被证明为NP-hard问题，当前广大学者在求解此类问题上常采用精确算法[4-6]、传统启发式算法[7-8]和元启发式算法[9]。

1问题描述

RPUTV可以描述为一个中心具有多辆靶车，靶车可以自由选择路径移动到目标点，其次本问题以靶车行驶路径最短为求解目标故作出以下假设：（1）所有靶车均从中心出发，执行完作战任务后回到作战中心；（2）一个作战点由一辆靶车服务一次即可。

定义一个作战中心具有台无人靶车，无人靶车集合为，集合中的元素为无人靶车的编号，作战目标点集合为，其中在，定义无人靶车行驶路径为一个无向图，为，其中0为作战中心，为无人靶车行驶路径边的集合，。综上所述无人靶车的模型如下所示。

• RPUTV的目标函数，其中为无人靶车行驶的距离，为二进制变量，时无人靶车路过两个点，反之则不经过。为之间的距离。

• 每个目标点只可以访问一次。

• 完成作战任务后返回作战中心。

• 禁止无人靶车行驶路径中产生回环。

在公示（4）中M为极大数，为决策变量，继而引入约束。

• HACA算法

2.1贪心算法

贪心算法（Greedy Algorithm）是一种解决问题的算法范式，它以一种贪心的策略来选择每一步的最优解，希望通过每一步的局部最优选择最终达到全局最优解。因此本文为了提高算法的求解效率使用贪心算法来构建初始解其算法步骤如下。

步骤1：读取当前的数据点的坐标，标记路径为。

步骤2：判断是否已经访问过所有坐标点，若已经将所有点访问结束则停止算法输出解，若没有访问完所有的目标点则将未访问的目标点记为。

步骤3：随机产生的基点，接着将放入。

步骤4：挑选目标点，比较路径，若路径短则保留，执行完任务后返回步骤2。

2.2蚁群算法

蚁群算法（Ant Colony Optimization， ACO）是一种仿生学算法其原理是通过模拟蚂蚁寻找食物过程中会释放信息素的行为来获得路径最优解。其具体步骤如下。

步骤1：初始化信息素，在通过贪心算法得到的路径中，随机放置“蚂蚁”，每一对蚂蚁分配一个初始问题的信息素。表示“蚂蚁”在两个目标点汇总的可行性。

步骤2：根据选择概率，“蚂蚁”选择下一个需要移动的目标点，在此过程中会释放出信息素，信息素浓度为

步骤3：“蚂蚁”选择下一移动的目标点并及时地更新走过的信息素。

步骤4：在每次迭代后更新无人靶车路径可行解中的信息素浓度。通常使用蒸发和新信息素的沉积来模拟信息素的更新。

步骤5：比较解的质量，即“蚂蚁”走过的路径最短

步骤6：重复步骤2到步骤5。直到满足停止条件，输出最优解。

2.2.1邻域搜索算法

由于蚁群算法容易陷入局部最优，因此在算法的求解过程中加入相应的邻域变换如单点插入和2-opt操作，算法步骤具体如下。

2.2.2单点操作

单点插入操作作用于无人靶车行驶路径中，如图1所示将Route1目标点3插入到Route2目标点1的位置形成Route2。

• 2-opt操作

2-opt是局部搜索（Local search）算法，同时局部搜索算法是在目标问题的一组可行解上进行邻域搜索得到新的可行解。图2为2-opt操作的实例，将中的1插入到3的位置，2插入到1的位置，3插入到2的位置，形成新的路径

3 实验仿真

本文涉及的所有算法采用Python语言编程，在Win10操作系统下，硬件为设备名称DESKTOP-NTUFG2K Intel（R） Core（TM） i5-8350U CPU @ 1.70GHz   1.90 GHz， RAM16.0 GB 的机器上运行，实验数据采用Solomon数据库，实验仿真结果如下所示。

本文采用一种混合蚁群算法（Hybrid Ant Colony Algorithm，HACA）来解决RPUVT问题。算法的初始阶段使用贪心算法对问题的初始解进行构建，接着在蚁群算法的搜索过程中引入邻域搜索的操作，来加强算法的邻域搜索能力。为了验证所提算法的可靠性，本文将HACA与遗传算法（Genetic Algorithm， GA）和模拟退火算法（Simulated Annealing，SA）。进行仿真比较，算法均设定运行30次，运行时间设定为50s。各算法数据对比如下所示，为行驶总路径，为平均值，其中较好的数据均用粗体表示，综合表1所示HACA算法求得的解优于GA和SA。

4结语

本文提出了一种并求解了一种无人靶车路径规划问题，首先综合考虑了无人靶车的行驶距离，同时构建了无人靶车路径规划问题的混合整数规划模型，其次提出了一种混合蚁群算法，算法的初始阶段为了提高算法的求解效率，提出使用贪心算法构建目标问题的初始解，接着在蚁群算法中为了防止算法过早收敛，插入邻域搜索的策略来提高解的质量，最后将该算法通过对比实验验证了该算法较GA、SA更加有效。

参考文献

• 谢高杨，房立清，苏续军，等.无人靶车在不同车速下的路径规划方法[J].电子测量与仪器学报，2023， 37（2）： 39-47.
• 成海飞.面向越野环境的无人靶车路径规划研究[D].南京：南京林业大学，2023.
• 肖楠.基于嵌入式惯导技术的移动靶车设计[D].西安：西安工业大学，2023.
• YU Y， WANG S， WANG J， et al. A branch-and-price algorithm for the heterogeneous fleet green vehicle routing problem with time windows[J]. Transportation Research Part B： Methodological， 2019， 122（4）： 511-527.
• XIAO Y， KONAK A. The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion[J].Transportation Research Part E：Logistics and Transportation Review，2016，88（4）：146-166.
• CIMEN M，SOYSAL M.Time-dependent green vehicle routing problem with stochastic vehicle speeds： An approximate dynamic programming algorithm[J]. Transportation Research Part D Transport & Environment，2017，54：82-98.
• 吕飞，王力，黄石磊.基于混合C-W节约与遗传算法的多AMR拣选路径规划优化方法研究[J].工业控制计算机，2023，36（11）：81-84.
• 崔焕焕，官礼和.优先配送绿色VRP的混合启发式求解算法[J/OL].系统仿真学报：1-12[2023-12-18].https：//doi.org/10.16182/j.issn1004731x.joss.223-1125.
• 黄雄，史长胜，曹祺.基于改进模拟退火算法的校车路径规划研究[J].淮南职业技术学院学报，2023，23（3）：131-133.