基于蚁群算法在VRP中的应用研究*——以呼和浩特A物流公司为例

□ 文宗川，王 慧

(1.内蒙古工业大学 经济管理学院,内蒙古 呼和浩特 010051；2.内蒙古工业大学 人文学院,内蒙古 呼和浩特 010081;3.内蒙古创新方法研究中心,内蒙古 呼和浩特 010051)

物流作为最终成本的削弱边界，是继增加生产、节约成本，提高效率、降低损耗两大利润源之后的第三利润源，其经济意义不言而喻。而配送作为现代物流管理中的七大要素之一，它是现代市场的新经济系统、当代新兴科学方法和系统供应链思想的综合产物，其中车辆路径问题(Vehicle Routing Problem,以下简称VRP)是配送中的主要研究方向。基于VRP的相关研究主要概括为精确式算法与启发式算法[1]，如遗传算法、蚁群算法、禁忌搜索算法、模拟退火算法、粒子群算法等。其中多数学者都是基于有时间约束的VRP模型，改进蚁群算法提高收敛速度，降低车辆使用量使运行距离变短[2-4]。也有学者通过禁忌搜索算法求解车辆路径问题，如构建邻域算子和邻域交换点禁忌表，测试数据结果[5-6]。针对车辆运输路径(Vehicle Routing)与车辆运输速度(VehicleSpeed)的相关性，经营成本与收益的线性关系比，采用科学合理的方法确定车辆运输的路线规划是物流配送活动重中之重，通过对传统的配送系统进行路径优化，可以大幅度提高资源的利用率。

本文以呼和浩特市新城区A物流公司的派送网点为例，基于蚁群算法对车辆路径问题进行优化，针对不同配送路线的车辆路径问题构造相应数学模型并进行MATLAB仿真模拟。

1 蚁群算法求解模型

1.1 蚁群算法原理

蚁群算法的基本原理可以通过Dorigo M研究蚁群寻找食物过程的例子进行解释，图1(图中d代表长度，T代表时间段，ant代表蚂蚁数量)是蚁群寻找食物的简化示意图。假设X是蚁群的蚁巢，Y是蚁群目标食物源，N与M分别是假设障碍物，由于障碍物的原因，蚁群不能直接抵达Y目标，蚁群只能由N经过A到达Y，或者由M经过A到达Y。假设一个时间单位分别有100只蚂蚁由A到Y或者由X到B，由于开始没有蚁群形成信息浓度差，蚁群在抵达B时，选择两条路线的概率相等，所以每一条路径都有50只蚂蚁。随着时间的推移，蚁群的选择路径上有信息素的积累，B-M、A-M路径的信息素浓度是B-N、A-N路径的两倍左右，又根据不同蚁群数量的移动，B-M-A的路径信息素浓度越来高，会导致更多的蚂蚁选择该路线，从而找出蚁巢到食物源的最短路径。根据以上的蚁群路线模拟，可知蚁群之间的信息素浓度差与信息交换是一个正反馈的过程。

图1 不同时间段的信息素浓度对蚂蚁选择路径的影响

1.2 蚁群算法路径运输模型

(1)

在式(1)中，Aa为蚂蚁k尚未寻找的食物点集合，这个集合在进化过程中不断调整。α，β分别表示蚂蚁在运动过程中所积累的信息素和启发式因子在蚂蚁路径选择中所起的不同作用。相关信息素更新规则如下：

τnm(t+t1)=ρ·τnm(t)+△τnm

(2)

(3)

式中，ρ为信息残留程度。

式中，△τnm为本次循环中留在路径n和m上的总信息素量，有三种计算方法：

蚁群循环系统(Ant-cycleSystem)模型信息素增量的计算公式

(4)

蚁群数量系统(Ant-quantitySystem)模型信息素增量的计算公式

(5)

蚁群密度系统(Ant-densitySystem)模型信息素增量的计算公式

(6)

基本蚁群算法实现流程如图2。

图2 蚁群算法实现流程图

2 仿真验证与结果分析

2.1 在呼和浩特市A物流公司车辆派送点的地理信息采集与处理

以内蒙古呼和浩特市新城区为车辆路径问题信息处理区，基于蚁群算法解决现实VRP问题模拟A物流公司在该区域进行小区与社区间的快递配送路径规划问题，规划最短路径配送路线，以达到降低车辆油耗、配送等待时间最短的目的。为优化处理信息，减少其他路径规划影响因素，故忽略在配送途中出现的天气、环境、其他车辆等影响因素。各小区与社区之间距离以直线距离为实验模拟距离。通过信息采集，选取小区与社区数共计10处。

对采集信息区测量实际直线距离，并绘制直线路径，选取一点为派送起始点，为使计算精确，对该调查社区点进行坐标化处理，以公主府公园坐标为原点(0，0)，并对其他坐标赋值，见表1。

表1 小区点位具体坐标与赋值表

2.2 MATLAB仿真模拟

2.2.1 实验坐标与参数设置

①实验坐标。

图3 在MATLAB中的模拟坐标点

②参数设置。

表2 参数设置表

2.2.2 实验结果

通过蚁群算法求解模型在MATLAB中运算得出不同迭代次数中所获的求解结果。注：这些结果都是在迭代中选取的较优解，由于蚁群算法本身就是一种随机搜索算法，每次实验都会产生不同的解，所以选取的解都是随机的。但是，通过多次的实验与迭代次数可以看到随机值的趋势。

2.3 实验结果分析

通过不同迭代次数的运输发现最短路径有多种选择方式，在实际配送路径中也应该考虑实时状况选择合适的配送路线。

①实验比照。

表3 各迭代次数对照表

图4 各迭代次数中的车辆路径最优解

②分析对比。

通过实验数据的验证对比，能够更加清晰、直观地看到不同迭代后的最短路径与最短长度。综合所有结果发现，迭代次数越多，长度越短，得到的较优解也越佳，在经过更多的迭代后且在迭代结果相同时会得出最优解，在相同解中，路径规划也有不同，更加符合蚁群算法的随机性，在选择过程中也应该落实现实情况。在不同迭代次数的解中，每种解也构造了不同的审美视角，在解决VRP问题中，实现快速求解路径也应当实现在配送途径中。

3 结论

本文引述当前物流的配送问题以VRP为研究方向，在旅行商问题的基础思想上运用VRP实现方法进行可行性研究，利用蚁群算法验证呼和浩特新城区配送路径可行性，与常规方法相比该方法具备较好地路径规划方案的最短路径以及运算时间短的特点，在配送中能较好的节省成本和时间。通过验证，在相同最短路径规划中会出现不同规划路径，配送者可结合配送出发点、途中具体情况，如出现路段维修、交通堵塞、天气状况等其他情况进行合理选择。车辆路径规划不仅仅是物流领域，还可以拓展到其他领域中，可进行城市交通的优化与升级，对于生产企业中的选址建厂问题也可广泛应用。