基于蚁群算法的装备保障路径规划模型*

张 星，杜晓明，蔡纪伟，张志学

（1.军械工程学院，石家庄 050003；2.解放军66010部队，石家庄 050000）

基于蚁群算法的装备保障路径规划模型*

张 星1，2，杜晓明1，蔡纪伟1，张志学2

（1.军械工程学院，石家庄 050003；2.解放军66010部队，石家庄 050000）

现代战争中装备保障路径规划中路径网络节点多和要优化的制约因素等问题成为装备保障仿真的难点，传统的蚁群算法寻找最优解，往往找不到满意的解。为了提高寻优效率，尽量减少装备保障中待保障装备战斗力恢复等待总时间，对基本蚁群算法进行改进。首先建立装备保障路径规划模型，然后基于基本蚁群算法，重新设计了启发信息的计算方法和信息素的更新函数，对路径节点的选择方法进行改进，最后通过一个具体的装备保障路径规划问题对传统的和改进的算法进行算例分析。计算结果表明，所采用的改进的蚁群算法可以更好地解决装备保障路径规划问题，有效减少待保障装备恢复战斗力之前等待的时间和保障分队经过的总路程。

蚁群算法，装备抢修，路径规划，模型

0 引言

装备保障活动的基础要素之一是畅通的交通运输网，而在此基础之上的保障路径优化是提高装备保障时效性的重要手段。以往装备保障路线的选取，是参谋人员依据保障对象、供应仓库、供应分队以及修理分队的分布，结合战时交通运输规则和工作经验，在纸质地图上手工完成，这种选取过程时间长、任务重、实时性差，而且以往的装备抢修任务执行顺序也多是靠个人的主观感觉、拍脑袋。显然这种方法已经不能满足现代战争突发性、速决性急剧增强的特点。如何快速、科学地选择装备保障路径和保障任务的执行顺序，已经严重影响着保障潜力的挖掘和装备保障能力的发挥［1］。蚁群算法是近年来才广泛应用的一种针对难解的离散优化问题的启发式优化算法，它是从对蚁群行为研究中产生的。西北工业大学的王振华等学者在文献［2］中引入了各路径段与起始点至目标点连线的夹角信息作为新的启发信息，加快了算法的搜索速度；高虹霓在文献［3］中针对军用物资供应道路的特点，给出了基于启发函数下的最短路标号搜索算法及程序流程图，对Dijkstra算法进行了改进，最终找出最佳路径。但是，他们大多是从路径搜索角度对蚁群算法进行应用考虑的，在多节点以及多制约因素方面分析的较少。本文是在现有蚁群算法的基础上，综合考虑抢修任务节点之间的距离及抢修任务的修复时间和完成时间的问题，建立了两个目标函数的优化问题，重新设计启发信息的计算方法和信息素的更新函数，使它们成为路径长度和战损装备战斗力恢复等待时间的二元函数，从而更方便地从最优解集中选择一条路径，减少待保障装备恢复战斗力之前等待的时间和保障分队经过的总路程。

1 基本蚁群算法

下面以商旅问题为例给出基本蚁群算法的思想。

假设蚁群中蚂蚁数量为M，城市数量为N，各个城市之间有许多条不同的路径。则在t时刻，第k只蚂蚁从城市i转到j的转移概率Pijk（t）为

蚂蚁每走过一个路径都要在该路径上留下信息素，为了避免算法陷入局部最有，引入了信息素挥发机制。这样，信息素的更新按照以下方式进行：

2 装备保障路径规划问题分析

2.1 装备保障路径规划问题原理描述

一般的路径优化问题，通常就是通过一定的算法，选取最短的路径，即最短路问题。但在装备保障中的路径规划问题中，路径的选择首先应从军事效益出发（尤其是战时），由于路径规划决定着装备保障任务的执行顺序，所以应该优先考虑保障任务的紧迫性，其次才能考虑运输的经济效益，即运输里程的最短问题［3］。具体而言，一般的路径规划问题，路径中各个节点的访问先后次序是无关紧要的，而在装备保障路径规划问题中，对路径上一些任务所在节点的访问时间有着严格要求，而且一般还要求按照先易后难的顺序执行装备保障任务，这要求在一定的经济效益基础上更早访问这些任务节点。装备保障路径规划虽然在很多方面可以借鉴车辆路径选择问题的研究结果，但是有其自身的特点。

①路径网络节点多。战时装备保障的地域为战区范围内所有可通行的路径构成交通网，该网络由已存在路径和战时临时开辟的道路构成。其路径网络节点非常多，如果通过搜索枚举所有的路线来找出所需要的满意解，显然是不现实的。

②要优化的制约因素多。这些制约因素包括军事效益、运输里程、运输时间、运输安全和运输耗费等，在进行路径优选时应当根据战时战场环境情况和装备保障系统情况进行综合考虑并作出决策［6-7］。

因此，在装备保障路径规划问题上，应针对上述特点，提出符合指挥实体任务规划实际需要的路径搜索规划模型。

2.2 装备保障问题路径优化问题的数学描述

针对装备保障路径规划问题的特点，设定某战术级装备保障小组要根据装备保障指挥员的要求，完成n项战损装备保障任务。此n项战损装备保障任务位于n个不同的地点p1、p2…pn，dij表示pi和pj之间的距离，p0为保障小组的出发地点，出发地点没有保障任务。这里不妨假设任意两点之间的路况是一样的，保障小组的平均行进速度为v，保障小组在pi和pj之间的机动时间为tij=dij/v，完成保障任务i需要的时间TiRepair，而且根据作战任务的需要，保障任务i需要的在时间TiLimit之前完成。根据前文分析知道，应该先执行较为容易的保障任务，使战损装备尽早恢复战斗能力，争取最优的保障效果。所以需要优化目标有两个：一个是待保障装备恢复战斗力之前等待的时间最短，一个是保障小组经过的总路程最短，显然这是一个多目标优化的问题。

2.3 模型建立

根据以上分析，建立如下多目标优化模型：

其中ti表示保障小组到达第i个保障任务实施地点的时间，对于任意一条装备保障路径{P1'，P2'，…，Pn'}，有：

3 对蚁群算法的改进及其求解流程

3.1 对蚁群算法的改进

3.1.1 对算法设计的改进措施

①子路径构造过程的改进：在基本蚁群算法中，每只蚂蚁均要经过所有节点；而在改进蚁群算法中，每只蚂蚁并不需要遍历所有节点。因此，在改进后的蚁群算法的每次迭代中，每只蚂蚁移动次数是不确定的，只能将是否到达目标位置作为路径构造完成的标志。

②改进后的蚁群算法蚂蚁转移时不仅要考虑各任务点之间的距离，还要考虑各任务点抢修任务的修复时间和完成时间要求。

③改进后的蚁群算法中，每只蚂蚁所构造的回路可能能够组成一些可行解，也可能一个可行解都得不到。

3.1.2 对信息素更新及路径节点选择方法的改进

蚁群算法最大的特点就是创造性地使用了启发信息，通过应用信息素播撒的方法，将之前搜索到的最优解作为反馈来指导后续蚂蚁的路径搜索。但由于TSP问题中只有惟一的一个优化目标，即路径长度的最小化。所以传统蚁群算法中启发信息的计算和信息素的更新均为路径长度的函数。而对于本文建立的两个目标函数的优化问题，需要重新设计启发信息的计算方法和信息素的更新函数，使它们成为路径长度和战损装备战斗力恢复等待时间的二元函数。

多目标优化蚁群算法中的启发信息的计算方法为：

当所有蚂蚁都完成了路径搜索后，路径上信息素更新方法为：

其中Q为常量，Lk表示第k只蚂蚁在本次循环中经过的路线长度，Tk表示第k只蚂蚁在本次循环中得到的所有战损装备战斗力恢复等待时间的总和。其路径选择方法描述为：首先取一个随机数q0，判断是否满足q≤q0，q0为事先确定的一个参数，且0≤q0≤1。如果满足则按照式（12）来选择下一个路径节点，如果不满足则按式（13）取得的概率随机选择下一个路径节点［8-9］。

3.2 求解流程

Step 1：构造初始可行路径，用任意算法计算出一条可行路径，然后分别计算最短路径L0和最小的战斗力恢复等待时间T0，并把此可行解加入Pareto最优解集；

Step 2：算法开始前首先初始化信息素，为每条边赋予相等的信息素。同时初始化禁忌列表为空，设置信息素保留率为p；

Step 3：while（迭代步数＜预定的迭代次数）；

Step 3.1：初始化蚂蚁，将m只蚂蚁随机放在代表抢修小组的节点中；

Step 3.2：任取一只蚂蚁开始搜寻路径，循环1：for k=1 to m步长为1；

Step 3.2.1：蚂蚁开始搜寻路径，循环2：for k=1 to n步长为1；

Step 3.2.2：根据式（9）来计算不在禁忌列表中各个任务点的启发信息ηij；

Step 3.2.3：产生一个随机数q根据式（12）来选择取值最大的抢修任务点pj，否则根据式（13）确定的概率随机选择抢修任务点pj；

Step 3.2.4：判断tj+tjRepair≤TjLimit是否满足，如果不满足转到步骤3.2.1；

Step 3.2.5：把抢修任务点pj列入禁忌列表；

Step3.2.6：如果全部抢修任务点都在禁忌列表中，则循环2：end for；

Step3.3：用该蚂蚁得到的路线r计算Z1和Z2，同时和每一个Pareto最优解集里的解相比较，若r为解集的非支配解，则将此解加入Pareto最优解集，同时将被此解支配的解。

Step3.4：如果所有蚂蚁都搜寻完毕，则循环1：end for；

Step4：整理Pareto最优解集，开始下一次循环；

Step5：end while。

在得到Pareto最优解集后，决策者就可以根据自己的偏好和装备保障系统状态，对总路径长度和待保障装备战斗力恢复等待总时间进行权衡，很方便地从Pareto最优解集中选择一条路径，完成路径规划［10］。

4 算例实验及结果分析

这里应用某装备保障想定中的一个装备抢修路径规划问题来测试上述算法，路径中共有8个任务点，由于战斗进行比较激烈，所保障的单位中，其中第4个和第5个任务点的抢修任务紧急，需要在一定时间内完成，其他节点紧急情况一般。要求装备抢修分队在综合考虑任务点间距离以及各任务点抢修任务修复时间和完成时间的情况下，完成抢修任务。

8个访问节点的具体位置如图1所示。

战损装备抢修任务地点之间的距离如表1所示，其中∞表示两个任务地点之间没有直接相连的通路。

各个抢修任务的战损装备修复时间以及各个任务抢修完成的时间限制如表2所示：

如果仅考虑战损装备抢修任务地点之间的距离，运用基本蚁群算法进行计算，从初始点0开始搜索，从节点i转到j的转移概率根据式（1），蚂蚁每走过一个路径都要在该路径上留下信息素，为了避免算法陷入局部最优，引入了信息素挥发机制。这样，信息素的更新按照式（2）和式（3）进行，得出其最优路径为（如图2所示）：

将战损装备抢修任务地点之间的距离和各抢修任务的修复时间及完成时间综合考虑，运用改进的蚁群算法进行计算。

多目标优化蚁群算法中的启发信息的计算方法为式（10）和式（11），从任务点0开始搜索，其路径选择方法为：判断是否满足q≤q0，如果满足则按照式（12）来选择下一个路径节点，如果不满足则按式（13）取得的概率随机选择下一个路径节点，经改进算法求解，最后得到的最优路径为（如图3所示）：

在利用本文改进算法对此装备保障路径规划问题进行处理后，由于节点4和节点5的TjLimit分别为4.0和3.0，在改进算法中判断tj+tjRepair≤TjLimit是否满足，如果不满足则返回重新开始搜索。根据算例实验结果比较得知，改进算法可以有效解决需要综合考虑抢修任务节点之间的距离和抢修任务的修复时间和完成时间的问题，尽可能地减少待保障装备恢复战斗力之前等待的时间和保障分队经过的总路程。

5 结束语

从算法的仿真验证来看，本文设计的算法可以很快寻找到部分最优解，结果更接近现实，也证明了用这种方法具有一定的理论参考价值和实际意义。但是，算法本身还存在一些不足之处：首先当需求点数目较大时，整个算法的搜索时间较长，得出的最优解不稳定，严重限制了该算法的优势；其次，搜索过程中易陷入局部最优解，即在达到规定迭代次数之前很长时间内不再发生变化，搜索停滞；再次，启发因子α和β，挥发系数ρ以及常量Q的取值均会对算法结果产生影响。这些问题有待于进一步结合实际问题进行研究。

［1］董家瑞，王精业，王琴琴.装备保障路径选择算法研究［J］.装甲兵工程学院学报，2008（6）：9-12.

［2］王振华，章卫国，李广文.基于改进多目标蚁群算法的无人机路径规划［J］.计算机应用研究，2009，26（6）: 2104-2109.

［3］高虹霓，杨建军，曹泽阳.军用物资供应道路选择最优算法研究［J］.系统工程与电子技术，2002，24（3）:61-64.

［4］李士勇.蚁群优化算法及其应用研究进展［J］.IT技术论坛，2003，18（11）:911-917.

［5］石玉峰，金建军.战时不确定性运输路径优化［J］.空军工程大学学报，2005（6）:56-59.

［6］张最良，李长生，赵文志，等.军事运筹学［M］.北京:军事科学出版社，1993.

［7］黄坤，吴俊.一种改进的多目标蚁群优化算法［J］.微电子学与计算机，2011，23（10）:181-187.

［8］池元成，蔡国飚.基于蚁群算法的多目标优化［J］.计算机工程，2009，35（15）:168-172.

［9］李跃光，张远平.一种改进的蚁群算法在垃圾运输问题中的应用［J］.湖南师范大学自然科学学报，2010，26（6）：18-23.

［10］范路桥，姚锡凡，卞青青，等.蚁群算法及其在移动机器人路径规划中的应用 ［J］.机器人技术，2008，19（12）：257-261.

Equipment Support Route-planning Model Based on Ant Colony Algorithm

ZHANG Xing1，2，DU Xiao-ming1，CAI Ji-wei1，ZHANG Zhi-xue2
（1.Ordnance Engineering College，Shijiazhuang 050003，China；2.Troops 66010 of PLA，Shijiazhuang 050000，China）

The problem of the network node and the complex constraint in the route-planning of the equipment support during modern wartime becomes the difficulty in the equipment support simulation.The traditional ant colony algorithm will not introduce satisfied explain.In order to improve the optimizing efficiency，the traditional ant colony algorithm is improved.Firstly，the model of the route-planning in equipment support is built，devises the computing method and the updating function，and the choice of the path node is improved，at last，the improved algorithm is tested and verified by using a route-planning problem in some equipment support scenario，proves that the improved ant colony algorithm can solve the problem of the route-planning in equipment support，reduces the waiting time before the waiting equipment recovering fighting ability and the total distance the support elements passes.

ant colony algorithm，equipment rush repairing，route-planning，model

TP391

A

1002-0640（2015）09-0026-05

2014-08-20

2014-09-03

国家自然科学基金资助项目（60904071）

张 星（1985- ），男，河北石家庄人，硕士研究生。研究方向：装备保障指挥及自动化。