装备抢修车多目标路径优化

李众　谢晓东　余选召　吴迪

摘 要：针对战场抢修工作的特点，建立了考虑安全性、时间损耗等因素的多目标路径优化模型，采用蚁群算法对问题求解，并对蚁群算法进行改进，提升了算法的收敛速度。

关键词：抢修车；多目标；路径优化；蚁群算法

1 基于功效函数法[1]的抢修车路径优化模型

⑴优化目标：1）安全性：安全性表现为安全通过概率。2）道路状况：道路状况表现为路面良好程度。3）时间损耗：时效性是战时主要考虑的因素。4）机动距离：机动距离对应着机动费用。

⑵利用层次分析法确定指标权重，本文采用1～9标度。

⑶设有m条备选路段，n项评估指标，共有L条可选路线，共有p个节点。备选路段d的各项评估指标数值为：{cd}={cd（1），cd（2），…cd（e），…cd（n）}，e=1，2…n。

①指標无量纲化处理方法

显然，处理后的指标yd（e）越小，表明备选路段d的评估指标e评价越优。

②建立目标函数：

Sij、Rij、Tij、Eij分别为路段（i，j）的安全性、道路状况、时间损耗、机动距离；式（5）表示任意路段只通过一次，式（6）表示一系列路段连通性约束。

2 最短路算法[2]

改进蚁群算法[3，4]（采用蚁周系统）：

⑴选择概率改进：q和q0都是[0，1]之间的随机数。

⑵惩罚策略：引入惩罚因子pn对路段进行惩罚。

式中， 和 分别表示惩罚前后路段（i，j）上的信息素浓度。

3 算法验证与分析

抢修车由V1出发至V10对战损装备进行抢修，要求进行路径优化，寻找最优路径。

S、R、T、E的权重分别为：0.1268、0.2612、0.5224、0.0897。对各指标值进行无量纲化处理，采用功效函数法得出各路段的综合分数。

基本和改进蚁群算法求最优路径，得出最优路径：1->2->5->8->10，最优路径值：5.6748。参数设置：M=30、α=1、β=1、C=100、Q=10、ρ=0.65、pn=0.3、循环30次。

基本蚁群算法在第8次循环之后收敛，改进蚁群算法第1次循环即收敛，通过改进提高了蚁群算法的收敛速度。

4 结语

从战时角度出发，建立了基于功效函数的抢修车路径优化模型，改进了基本蚁群算法，通过实例验证，证明改进蚁群算法具有更快的收敛速度，适于求解最优路径问题。

[参考文献]

[1]百度百科.功效函数法.http：//baike.baidu.com/view/1796103.htm.

[2]施寅跃.城市道路网中蚁群最短路径算法研究[D].南京理工大学，2010.06.

[3]段海滨.蚁群算法原理及其应用[M].北京：科学出版社，2005.12.

[4]Badr A，Fahmy A.A proof of convergence for ant algorithms[J].International journal of Intelligent Computing and Information，2003，3（1）：22-32.