基于改进ACO 的战后物资回收车辆路径优化*

孟小玲，温海骏，曾艾婧，邵延君

（中北大学，太原 030051）

0 引言

随着信息化时代的推进和新军事战争变革的深入，信息化战争已逐步成为当今世界主要的战争形态［1］。现代武器装备结构复杂，技术含量高，随着战争的进程和战争强度的提高，战后军事基地留下的高损毁可回收再制造的武器装备、物资器材、弹药品种多样，数量巨大，损坏状态不一，给各国军事后勤带来了前所未有的压力［2］。战后物资回收属于逆向物流问题，如何做到快速、高效地回收抢修可再制造军用物资，合理地规划回收车辆逆向物流路径以及降低运输成本，已成为当今各军队后勤保障急待解决的一个突出问题。军事物流是军事后勤的核心部分，军事物资回收又是军事物流的一个缩影［3］。为此，从逆向物流角度出发研究以信息化战争为背景的战后可回收再制造的军事物资具有重要的理论和现实意义。

针对再制造物资回收、逆向物流网络设计等问题，不同学者从不同角度展开了研究。陈希琼［4］等建立了同时考虑车辆容量和距离约束的VRPSPD双目标模型；王勇［5］等研究了用蚁群算法和单纯形法对单辆货物配送路径模型进行了优化；殷佳林［6］等针对送取货车辆路径问题构建了一种蚁群算法与禁忌搜索算法的新混合算法；Shaobo Li，Kangqi Mu［7］等提出了一种基于蚁群算法而改进的粒子群优化自适应参数获取算法；翟辉［8］研究了采用蚁群算法对废旧手机回收逆向物流路径进行优化；Shan Xiao［9］提出了一种基于蚁群优化算法的最优出行路径规划和实时预测方法；Chen Guoliang，Liu Jie［10］提出了一种基于网格映射的混合人工势场和蚁群优化路径规划的方法。但目前运用改进蚁群算法对废旧武器装备的车辆路径优化，以及降低运输成本问题的研究还不是很完善，需要进一步的探讨和研究。

本文研究的主要内容是基于蚁群算法对战后军用物资回收站的车辆路径优化，同时建立计算最小化成本的数学模型，提出对原始蚁群算法进行概率模型和信息素浓度的优化方案，加速蚂蚁循环的收敛效果，缩短蚂蚁寻径的距离，之后针对目前战后军事基地的物流路径进行分析，找寻优化点与优化方向。

1 数学模型

1.1 问题描述

正常的物资配送是按客户的需求定性定量地供货，其客户的需求量、物资尺寸等都是提前已知的，配送中心可根据订单信息合理安排车辆容载量，物流路径等；而战后物资回收面临着很多不确定性因素（如废旧装备是否可回收、供应数量、时间窗、装备尺寸），多源多目标的回收不仅需要后勤部队对战损装备进行损伤特征初判以识别是否可修复，而且战争态势的瞬息万变对后勤回收的时间性要求极为苛刻［11-13］。

战后军事物资回收再制造的车辆路径优化问题可描述为：某区域战后军事基地使用军用车辆回收废旧的武器装备，已知回收点位置、数量、回收中心位置、回收车辆数量和最大承载量。在符合车辆的最大负载、行车距离和其他服务需求的同时，安排合理的路径规划，尽可能实现多目标优化效果，如空间利用率和成本等。

为了更好地界定所要研究的问题，方便模型建立和求解，需要对实际问题进行一些简化和抽象，提出以下假设：1）此次回收的装备均为磨损度小、可再制造的装备；2）假设有一个武器装备回收运营中心和若干个回收点；3）派出一辆车对各个回收点的废旧武器装备进行回收；4）后勤部队对各个军事基地的废旧装备供应数量不确定，假设供应数量服从一定的概率分布；5）各个点的回收总量在单位运输车的最大载重范围内；6）在回收过程中每个回收点有且只有一辆运输车经过。

决策变量定义如下：

1.2 模型建立

目标函数

约束条件

式（1）和式（2）为目标函数，即总路径最短和运输成本最少，分别用D 和Z 表示；式（3）为车辆能力约束，式（4）、式（5）表示回收基地被且仅被一辆车服务，式（6）表示车辆从i 到j 的运输量大于回收点j 的供应量。

2 蚁群算法及其优化

2.1 基本蚁群算法

其中，α 为信息素重要程度因子，β 为启发函数重要程度因子，allowedk为蚂蚁k 下一步即将访问的点。

蚂蚁完成一次循环后，各回收路径上的信息素浓度需进行实时更新，设参数ρ 为信息素挥发系数，具体公式为：

其中，Q 为信息素强度；Lk为蚂蚁在本次循环中走过的路径长度。

2.2 改进蚁群算法

2.2.1 概率模型优化

在蚂蚁选择下一个回收点的概率计算模型上，设定一个新参数ω，当ω0大于ω，蚂蚁寻找下一个节点的概率只依据节点间路径长度计算；当ω0小于或等于ω 时，蚂蚁选择下一个回收点的概率根据回收点之间信息素浓度和路径长度两种因素共同计算生成，其中，ω0为［0，1］之间均匀分布的数。改进后概率公式如下：

改进后的算法使得蚂蚁在选择下一个回收点时有一定概率只考虑回收点之间的路径长度，不受其他蚂蚁留下的信息素浓度影响，通过这种优化方式在一定程度上抵消了由于正反馈系统导致误差加大的问题。

2.2.2 信息素浓度优化

原始蚁群算法信息素的更新除了最优路线上信息素逐渐增多，其他非最优路线上的信息素浓度越来越低，这样使得蚁群算法的特性因没有充分利用蚂蚁寻径中的全部信息而没有完全发挥出来，容易陷入局部最优。在信息素浓度改进中，引入一个信息素减少系数θ，改进后的公式如下：

通过对信息素更新公式的优化，使得蚂蚁在寻径过程中获得更为优化的信息参考，这样弥补了原始蚁群算法蚂蚁循环信息利用率低的问题。

3 算法仿真测试及分析

为了验证改进后蚁群算法的有效性和可行性，本次实验分别对两种算法在迭代次数不同的情况下各求解20 次，进而分析结果。

3.1 算法寻优能力

算法寻优能力主要测试两种算法的路径长度、程序运行时间及车辆运输成本来评定。表1 为测试路径最优值及平均值的对比结果，表2 为程序运行时间对比结果，表3 为运行结果最优值的车辆运输成本对比结果。

表1 算法路径对比结果

表2 算法运行时间对比结果

表3 车辆运输成本对比结果

通过表1 两种算法运行的最优值和平均值可以看出，在基本参数设置相同的条件下，改进后的蚁群算法运行得到的结果均优于基本蚁群算法，当迭代50 次时，改进前后的最优值和平均值分别相差2.74 和1.21；当迭代100 次时，改进前后的最优值和平均值分别相差6.62 和3.98；当迭代200 次时，改进前后的最优值和平均值分别相差2.27 和0.03。而在迭代次数100 次时出现全局最优值403.30 km，此时最优值与改进前的相差最大，平均值也相对其他迭代次数为最优。

表2 程序运行时间结果显示，改进后的蚁群算法相比基本蚁群算法运行时间更短。表3 可以看出，当迭代50 次时，改进前后的运输成本相差13.7；当迭代100 次时，改进前后的运输成本相差33.1；当迭代200 次时，改进前后的运输成本相差11.3。运输成本在迭代100 次时出现最低值为2 816.5 元。所以将改进蚁群算法应用到战后军用物资回收的车辆路径问题中更容易搜索到较优路径。图1 为两种算法在迭代100 次时的路径最优值对比图。

3.2 算法可靠性与收敛效果

算法的可靠性通过算法运行成功率来说明，成功率是指在预先设定一个路径临界值的基础上，算法未达到临界值的次数与总的运行次数之比，这里临界值设为每个算法在不同迭代次数下的平均值；算法的收敛效果通过最短距离与平均距离对比得到。表4 为算法求解可靠性的对比结果，图2 为迭代100 次两种算法最优值的收敛效果对比图。

图1 路径最优值对比图

表4 可靠性对比结果

图2 迭代收敛效果对比图

通过表4 可以发现，在可靠性方面，改进后的蚁群算法在运行20 次时求解结果未达到临界值的成功率明显高于基本蚁群算法。图2 收敛效果对比图显示算法迭代100 次时，基本算法在40 多次达到最优，而改进后的算法在迭代不到20 次时就可达到最优；基本算法在一开始陷入了局部最优，而改进算法避免了这一缺陷。综上说明改进后的算法迭代效果更优，平均距离相对更稳定一些，不容易陷入局部最优解。

3.3 算法稳定性

算法的稳定性用每次求解结果的标准差来表示。表5 为改进前后的算法连续求解20 次所得的标准差对比结果。

表5 稳定性对比结果

从表5 对比结果可以看出，改进蚁群算法对迭代次数不同的3 个测试数据集求解结果所得的标准差均小于基本蚁群算法，表明改进后蚁群算法的稳定性优于基本蚁群算法。

4 结论

本文以可再制造武器装备回收的车辆最短路径和运输成本最低为目标，针对基本蚁群算法收敛速度低和容易陷入局部最优的缺陷，提出了一种对寻径概率公式和信息素更新公式进行改进的算法，并比对改进前后两种算法在算法寻优能力、算法可靠性与收敛效果、算法稳定性方面的性能。实验证明，相比基本蚁群算法，优化后的蚁群算法求解TSP问题具有很好的稳定性、可行性和有效性，为战后军事物资回收再制造的车辆路径物流问题提供了一种优化的途径。