蚂蚁算法在配送运输问题上的路径优化研究∗

冯豪杰

（河南理工大学矿山空间信息技术国家测绘地理信息局重点实验室 焦作 454003）

1 引言

随着经济持续不断发展，我国物流需求规模只增不减，随之而来的是物流成本逐年攀升，配送车辆调度问题在企业运营中的作用越来越大，确切需要在物流配送成本方面制定新对策，去促进降低成本，从而提高其经营运营能力，这对物流业的发展具有重大的现实与实际意义［1～4］。车辆路径问题和车辆排程问题统称为物流配送车辆优化调度问题，该问题的提出，就受到、网络分析、图论、计算机应用、组合数学等学科的专家与运输计划制定者以及管理者的极大重视，并进行了大量的理论研究和实验验证，将其研究成果运用在运输、配送等系统中［5～6］。

2 蚂蚁算法的原理

根据仿生学家的长期研究发现：在觅食的过程中蚂蚁虽没有视觉，但会在走过的路径上释放一种特殊分泌物—信息素［7～8］，该信息素会被伙伴识别，碰到一个没有走过的路口时，会随机挑选一条路径行走，同时释放等量的信息素，路径越长则在这条路径上消耗的时间越多，信息素挥发的越多，相反，遗留的信息素浓度越低［9～12］。当后来的蚂蚁再遇到某个路口时，信息素浓度高的路径被选中的概率较大，这样便形成了一个正反馈机制［13～15］。最优路径上的信息素浓度越来越高，其他路径上信息素浓度会随着时间的流逝而逐渐消减，甚至消失，最终整个蚁群会找出最优路径［16～17］。图1为蚂蚁算法的最短路径与原理示意图。

图1中表示60只蚂蚁要经过障碍物寻找到食物。

T=0时刻：ABC与ADC两段路都是30只蚂蚁；

T=10时刻：ABC与ADC两段路分别为45、15只蚂蚁；

T=20时刻：ABC与ADC两段路分别为60、0只蚂蚁。

图1 蚂蚁算法原理

3 路径优化的蚂蚁算法设计与实现

传统蚂蚁算法是一种理想化状态，没有考虑到现实生活中诸多细节。在觅食过程中没有考虑到天气状况、路状、搜索时间过长以及挥发系数等，需要把这些因素综合全部考虑到该算法中。

3.1 相关系数的改进

蚂蚁算法虽具有全局性特征，但通常会忽略局部环境中的相关因素的影响，这也是在长时间路径选择中需要考虑的。路径选择次数的增多，路径上的信息素浓度会逐渐挥发掉，此时我们要考虑局部信息素浓度挥发程度，用挥发系数β来控制信息素浓度的挥发程度，β的大小直接关系到蚂蚁群算法的全局搜索能力及其收敛速度，因此通过自适应的调整β的大小来提高算法的全局性，0≤β≤1。

假设β的初始值为1，当蚁群算法求得的最优解在有限次循环内没有明显改进时，β以下式作自适应调整：

其中 βmin为 β的最小值，可以防止 β过小降低算法的收敛速度。

在经过时间t1后，蚁群会完成路径的一个循环选择，这时残留在每条路径上的信息素浓度为

式中Q表示信息素浓度，影响算法的收敛快慢，通常为常数；LK表示蚂蚁K在本次循环中走过的所有路径的总长度。

3.2 局部最优的改进

由于初始信息素浓度相等，导致开始时蚂蚁盲目搜索，产生大量无关路径，对信息素浓度局部更新产生误导。该问题不仅会导致初始搜索时间过长，并且无关路径信息素浓度被加强，阻碍最优路径搜索过程。本文根据无向图路径信息，在初始信息素浓度时加入方向性引导，初始化信息素公式修改如下：

其中Q表示信息素浓度，代表每次搜索分配的总信息素，一般为给定的参数；dij，djk分别表示节点j与起点i和终点k的直线距离。起点i与终点k的最短距离为两点之间的直线距离，从式（4）中可以得出，当节点j越趋于连线ik时，（dij+djk）越小，则X（0）越大，蚁群越倾向于选择该节点方向为移动的方向；反之，则偏离该节点。该算法在搜索起始点时对节点引入不同权值，对起始搜索产生很合理的方向引导，减弱了对较长路径的搜索，从而加速了寻找到全局最优解的速度。

3.3 配送运输路径优化算法的实现

物流业发展中，对车辆配送路径优化问题的求解方面，可借助人工蚂蚁替代车辆来服务客户点，返回到配送中心的标准是下一个服务客户点的运载总量比最远行驶距离或是汽车载重量多的时候，并不同车辆完成的此次运输，在此基础上，车辆可以对其他客户进行全方位服务，继而该车辆的人工蚂蚁就可以完成一次巡游标志，该标记是对客户进行的一次服务，一次服务也可以是一次循环，之后，需要根据蚂蚁巡游路径的时间长短将其他信息素进行分配，从而更好地对信息素增量进行不同程度的更新，以此进行不断的更新，得到最优路径或是选择相同路径，这样就可以完成求解了。

3.4 实例验证

为了验证本文改进算法的优越性与有效性，选择AutoCAD进行实例验证。将基本蚂蚁算法与本文改进的算法所得到的具体参数就行对比，可得到如表1的结果。

表1 两种算法的对比

从表1中可以看出，在使用的车辆是相同的情况下，本文的算法到达目的地所使用的行程更短，说明本文算法在通行效率上更具有优势。

4 结语

针对实际道路配送运输问题，本文提出了改进的蚂蚁算法，对相关系数的改进和对局部最优的优化为突破口。实例验证本文算法在行驶里程等方面更具有优越性。