无人靶车路径规划及其算法研究

魏振亚 崔国梁 宁涛 丁雨康

（安徽卡思普智能科技有限公司 安徽滁州 239299）摘要：靶车路径问题（Target Vehicle Routing Problem，TVRP）是组合优化领域的热点问题。首次提出了无人靶车路径问题（Unmanned Target Vehicle Routing Problem，UTVRP），建立了以最小化运输成本为优化目标的整数规划模型。接着提出一种带成本最优法的变邻域搜索算法（Variable Neighborhood Search with Cost Optimal Method，VNSCOM）。算法的初始阶段对目标问题进行单基因染色体编码操作，首先提出成本最优法对问题的初始解进行构造。接着，在单基因染色体编码下进行邻域变化，最后通过大量实验仿真，验证了提出算法的有效性。

关键词：无人靶车 变邻域搜索算法 染色体 算法研究

Research on Path Planning for Unmanned Target Vehicles and Its Algorithm

WEI Zhenya* CUI Guoliang NING Tao DING Yukang

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

Abstract： The target vehicle routing problem （TVRP） is a hot problem in the field of combinatorial optimization. The unmanned target vehicle routing problem （UTVRP） is proposed for the first time， an integer planning model with the optimization objective of minimizing transportation costs is established， and then a variable neighborhood search with cost ptimal method （VNSCOM） is proposed. In the initial stage of the algorithm， the single-gene chromosome coding operation is performed on the target problem. The cost optimal method is first proposed to construct the initial solution of the problem， then the neighborhood change is performed under single-gene chromosome coding， and finally the effectiveness of the proposed algorithm is verified through a large number of experimental simulations.

Key Words： Unmanned target vehicle; Variable neighborhood search algorithm; Chromosome; Algorithm research

无人靶车路径问题（Unmanned Target Vehicle Routing Problem，UTVRP）是经典车辆路径问题（Vehicle Routing Problem，VRP）[1]的变体。无人靶车路径问题与传统的车辆路径问题的主要的联系是将车辆路径问题的思想运用到无人靶车路径规划上。根据全球能源部门的相关文件表明[2]应对气候变化，设定零排放目标。因此合理优化靶车路径对环境具有重要意义。

广大学者分别从建模和求解方面对UTVRP展开深入研究。谢高杨等人[3]建立了不同车速下的无人靶车的数学模型，改进了A*算法将航向角与圆弧形搜索算法相结合最后应用于不同速度下的无人靶车路径问题上。史发[4]建立了地图模型，接着分析了主流算法Dijkstra路径规划算法和A*路径规划算法的工作原理和流程，最后编写了代码进行了两种算法的仿真。郑锐等[5]为了提高无人机航路规划效率和精度，重新设计了遗传算法，加快了搜索速度，提高了规划效率。

UTVRP是一个NP-hard问题，难在多项式时间内求得最优解。当前，该问题的求解算法可以分为精确算法传统启发式算法和元启发式算法三种。精确算法是利用数学方法或数据结构方法求得问题的最优解，精确算法可以为问题到最优解，但是在大规模问题上会存迭代时间过长的问题。传统启发式算法从一个解出发，在其邻域空间内不断搜索最优解，但是传统的启发式算法容易陷入局部最优。元启发式算法在处理各类路由问题上表现出显著的效果。元启发式算法分为模拟退火算法[6-7]、蚁群算法[8-9]、变邻域搜索算法[10-12]、遗传算法[13-16]等。

本文提出无人靶车路径问题（Unmanned Target Vehicle Routing Problem，UTVRP），此问题以靶车行驶成本最小为优化目标，接着提出一种带成本最优法的混合变邻域搜索算法来求解UTVRP。以下是本文的具体工作：第一部分将UTVRP建立混合整数规划模型，第二部分对UTVRP进行染色体编码，第三部分进行算法设计以及求解，第四部分为分析总结。

1无人靶车混合整数模型

UTVRP描述为一个靶车车厂拥有多台靶车，它可以移动到多个目标点。其中该问题的目标是实现所有靶车到达目标点路径最短即成本最小。为了明确研究适用的范围，做出以下假设：（1）所有靶车需从靶车车厂出发完成任务后返回靶车车厂；（2）每个目标点仅可以达到一次；（3）靶车总成本为靶车行驶距离。

定定义一个靶车车厂拥有台靶车，靶车集合为，其中为靶车编号。目标点集合为，为目标点个数。此外，靶车路径可定义为无向图，为节点集合其中为靶车车厂编号。为边的集合。UTVRP的混合整数模型如下所示。

UTVRP目标函数如公式（1）所示，其中F为目标问题成本即靶车运行的总距离，另外目标点之间的距离为。为决策变量，时，靶车通过点，否则。

每个目标点只可以到达一次，公式为

每辆靶车完成任务后返回靶车车厂，公式为

禁止靶车路径回路中含有子回路，公式为

式中，，为正整数集，对每个节点引入决策变量建立MTZ[17]约束，取值范围为。另外为极大数，有实验表明M取紧贴的上界，效果更好，因此本文取，n为目标点个数，因此我们将约束拉紧为

决策变量的约束为

2染色体编码方案

解的编码是求解UTVRP的关键的工作。该方案将添加若干个虚拟目标点用来分隔靶车的路径，并将目标点和靶车拟合成个体，图1中表示了UTVRP问题的一个可能的解，其中插入两个虚拟目标点即目标点12以及目标点13用来分配目标点，同时加入靶车车厂0。这样的自然数序列构成了一个解并且可以表述一个靶车路径分配方案。

那么图1解对应的目标点分配方案为：靶车1的访问顺序为；靶车2的访问顺序为；靶车3的访问顺序为1。

3算法步骤

3.1成本最优法

成本最优法的思想是以成本最小的方式去构建目标问题的可行解，并且在构建初始解的同时不违背目标问题的约束，已有实验表明[18]成本最优法的算法复杂度为。为了提高算法求解效率，本文采用成本最优法生成初始解，具体步骤如下。

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

步骤2：判断是否访问过所有目标点，如果访问完所有目标点则算法结束，输入处理后的路径并计算当前成本。若货物点未被访问完则算法继续，记未被访问的目标为。

步骤3：由轮盘赌随机产生基点，加入中并且标记已经被服务。

步骤4：挑选为被服务的目标点和，计算其成本标记为和比较、。若则将添加至，反之，将添加至。跳转至步骤2。

3.2变邻域搜索算法

变邻域搜索算法的基本思想是通过在搜索过程中系统改变邻域变换结构来拓宽搜索范围，来获得局部最优解，同时通过得到的局部最优解后重新改变邻域结构，寻求另一部分的最优解。变邻域搜索算法具有算法迭代速度快和局部搜索能力强的特点。为了提高搜索能力，本文采用单点插入、两段交换、2-opt来实现变邻域搜索算法。算法的具体步骤如下：

3.2.1 单点插入操作

单点插入操作作用于相同和不同的靶车之间这两种情况。同一辆靶车和不同靶车之间所有位置均可插入。图2和图3是两种单点插入情况的示意图。图2将目标点4插入到第四个点位，再将目标点7放置第三个点位更新路径得到新路径为路径2。在不同靶车之间将目标点8取出放置第二条路径的目标点4处，将目标点4放置目标点8处，更新路径为路径2，如图3所示。

3.2.2两段交换操作

两段交换操作亦可以作用于相同和不同靶车之间。在相同靶车之间目标点段2、8和7、6交换位置得到新路径记为路径2，如图4所示。不同靶车之间目标点段2、8、7和3、4、9交换的到新路径记为路径2如图5所示。

3.2.3 2-opt操作

2-opt操作将两条不相邻的边断开新连接得到新路径，具体操作如图5所示：将0-2和7-6断开并重新连接上两条边生成新的路径记为路径2。

4实验结果分析

本文涉及的所有算法采用Python语言编程，在Windows 10操作系统下，硬件为设备AMD Ryzen 5 3500U with Radeon Vega Mobile Gfx@2.10 GHz（16.00GB RAM）的机器上运行，实验数据采用Solomon数据库，实验仿真结果如下所示：

本文将一种带成本最优法的混合变邻域搜索算法（Variable Neighborhood Search with Cost Optimal Method，VNSCOM）与蚁群算法（Ant Colony Optimization，ACO）进行仿真比较，算法均设定运行20次运行，运行40 s。各算法对比如表1所示。表1中表示靶车行驶的总路径，为行驶结果的平均值。其中较好的数据均以粗体表示。综合表1和图6所示VNSCOM的数据均优于ACO，且平均值亦优于ACO。

5结论

本文提出并研究了一种靶车路径规划问题，综合考虑了靶车行驶成本最小化为优化目标，同时构建了靶车路径规划的混合整数模型。接着提出一种带成本最优法的混合变邻域搜索算法。算法的初始阶段为了加快算法迭代速度使用成本最优法对初始解进行探索，为了求得靶车路径问题的最优解本文使用不同邻域变换的搜索算法。通过实验对比表明：VNSCOM与ACO算法相比较，VSNCOM求得的路径最短即成本最小。由于本文算法在避障方面没有合适的方案，所以在后续工作中，还要对避障进行下一步的优化，以便于算法更贴近实际问题。

参考文献

DANTZIG G B，RAMSER J H.The Truck Dispatching Problem[J].Management science，1959（1）：80-91.

张雅欣，罗荟霖，王灿.碳中和行动的国际趋势分析[J].气候变化研究进展，2021（17）：88-97.

谢高杨，房立清，苏续军，等.无人靶车在不同车速下的路径规划方法[J].电子测量与仪器学报，2023（2）：39-47.

史发.无人靶车自动导航技术研究[D].西安：西安工业大学，2023.

郑锐，冯振明，陆明泉.基于遗传算法的无人机航路规划优化研究[J].计算机仿真，2011（6）：88-91.

LIU G，HU J，YANG Y，et al.Vehicle routing problem in cold chain logistics：a. joint distribution model with carbon trading mechanisms[J].Resources conservation and recycling，2020（156）：104715.

SUZUKI，YOSHINORI.A Dual-Objective Metaheuristic Approach to Solve Practical Pollution Routing Problem[J].International journal of production economics，2016（10）：143-153.

周鲜成，吕阳，贺彩虹，等.考虑时变速度的多车场绿色车辆路径模型及优化算法[J].控制与决策，2022，37（1）：473-482.

陈迎欣.基于改进蚁群算法的车辆路径优化问题研究[J].计算机应用研究，2012，29（6）：2031-2034.

王征，张俊，王旭坪.多车场带时间窗车辆路径问题的变邻域搜索算法[J].中国管理科学，2011，19（2）：99-109.

陈萍，黄厚宽，董兴业.求解多车型车辆路径问题的变邻域搜索算法[J].系统仿真学报，2011，23（9）：1945-1950.

赵灿华，侍洪波.基于自适应变邻域搜索的大规模电动车辆路径优化[J].华东理工大学学报（自然科学版），2020，46（5）：694-701.

张丽萍，柴跃廷.车辆路径问题的改进遗传算法[J].系统工程理论与实践，2002（8）：79-84.

赵燕伟，吴斌，蒋丽，等.车辆路径问题的双种群遗传算法求解方法[J].计算机集成制造系统，2004（3）：303-306.

邹彤，李宁，孙德宝，等.多车场车辆路径问题的遗传算法[J].计算机工程与应用，2004，40（21）：82-83.

常见，任雁.基于改进遗传算法的机器人路径规划[J].组合机床与自动化加工技术，2023（2）：23-27.

DESROCHERS M，LAPORTE G.Improvements and extensions to the miller-tucker-zemlin subtour elimination constraints[J].Operations Research Letters，1991，10（1）：27-36.

饶卫振，金淳.求解大规模CVRP问题的快速贪婪算法[J].管理工程学报，2014，28（2）：45-54.