基于改进蚁群算法的物流配送路径规划算法∗

何亚辉

（河南公路项目管理有限责任公司 郑州 450045）

1 引言

路径规划是物流配送研究领域的热点问题［1］。物流配送路线规划的本质是在已知的道路网拓扑结构中，从初始点到结束点规划出合理路线的最优路径规划问题［2］。如何快速、有效地规划出最优路径具有重要意义。目前，基于最短路径的搜索方法已经不能满足实际物流配送的需求，而基于最优路径的规划不仅要求寻找最短路径，而且还要求严格的实时性［3］。在路径规划过程中，从应用的角度来看，合理规划路线并提高计算响应速度显得尤为重要。大量的专家学者对物流配送路线规划问题进行了深入的研究。如何及时规划出合理的路径对于研究问题具有非常现实的意义。关于路径规划算法的研究很多，如遗传算法［4］、粒子群算法［5］、神经网络［6］、图论［7］和群体优化［8］。文献［9］利用网格法对物流配送的运输环境进行建模，将蚁群算法应用于路径规划，并且结果表明蚁群算法能够很好地求解路径规划问题。

鉴于蚁群算法具有分布式计算和启发式搜索等诸多优点，本文将蚁群算法与物流配送路径规划有效结合，在分析蚁群算法原理的基础上，建立了针对物流配送的路径规划模型，提出了改进的蚁群算法来进行更合适的路径规划。

2 蚁群算法

2.1 基本思想

蚁群算法是一种用来寻找优化路径的概率型算法，它来源于蚂蚁搜索食物问题的研究［10］。该算法不仅是一种自适应的分布式算法［11］，而且也是一种随机搜索算法［12］。蚂蚁在觅食的过程中通过遗留在路径上的化学物质完成沟通与合作，这种化学物质称为信息素。信息素越强，对应的路径距离越短。当路径信息素浓度较高时，蚂蚁发现该路径的概率越大，同时，经过该路径的其他蚂蚁也会释放一定量的信息素来增强该路径信息素的浓度，从而构成了一种学习信息的正反馈现象。在这种积极反馈的作用下，蚁群最终将找到从巢穴到食物源的最佳路径。然而，生物学家发现随着时间的推移，路径上信息素的浓度将逐渐衰减。

蚁群算法求解最优化问题的基本步骤是：将蚂蚁行走路径视为最优化问题的可行解，所有路径上的蚁群组成最优化问题的解空间。信息素在短径路中的释放量较多，随着时间的推移，信息素在短径路中的积累量逐渐增加，越来越多的蚂蚁会选择这些短径路。最终，蚂蚁在正反馈的作用下会聚焦在最佳路径上。

2.2 基本原理

在不失一般性的前提下，假设整个蚁群的蚂蚁数量为m，道路网络拓扑的节点数为n，道路节点i和节点j之间的距离为dij（i，j=1，2，…，n），在t时刻，节点i和节点j之间的信息素浓度为τij(t)，每个道路节点中的每个信息素浓度在初始时间内设置为τij(0)=τ0。

第k个蚂蚁根据道路节点上的信息素浓度决定下一个选择节点，假设(t)表示蚂蚁在t时刻从节点i移动到节点j的概率，则其计算公式为

其中，τij(t)表示在t时刻节点i到节点j之间的信息素浓度，它随着时间的推移逐渐衰减；ηij(t)表示道路节点i和节点j的路径期望，并与距离dij的倒数相对应，它代表了一种引导更好路径的局部启发式信息；α表示信息素浓度τij(t)的因子，该值可通过实验进行调整；β表示路径期望ηij(t)的因子，该值也可通过实验进行调整；Ak(t)表示在t时刻蚂蚁移动到下一个节点的集合，由于蚂蚁的移动根据信息素浓度的变化，所以该值呈现动态变化。假设在n时刻，蚂蚁完成从起始点到结束点的路径搜索，则信息素浓度的更新公式为

其中，ρ为常数，τij表示路径中节点i到节点j的信息素浓度变化，其可表示为

其中，表示第k个蚂蚁从节点i到节点j所释放的信息素浓度。

3 改进蚁群算法求解路径规划

本文将通过MAKLINK图论［13］建立物流配送路径规划模型并对路径网络拓扑进行初始化，由MAKLINK图中的几条MAKLINK线生成物流配送路径规划可行区域。其中，MAKLINK线可以表示相邻物流集散地之间的连接线。

3.1 链路节点的划分

在MAKLINK图论中，利用Dijkstra算法［14］规划出次优路径S，P1，P2，…，Pd，T，Li(i=1，2，…，d)是与节点对应的自由链路线。假设和是Li的两个端点，则其他节点可以表示为

其中，hi表示尺度参数，d表示链路划分中的节点数。式（4）表明，Dijkstra算法可通过链路线得到初始路径，只要定义一组参数(h1，h2，…，hd)，就可以从初始点到结束点获得一条新的路径，因此，蚁群算法的目标是求解(h1，h2，…，hd)中的最佳参数。

在使用蚁群算法之前，还需要对道路空间进行离散处理。由于路径初始规划的自由链路线选择，其链路线的长度各不相同，本文采用基于固定距离分类的链路分割方法［15］，假设链路线L的长度为ξ，则其分隔编号为

如果Int(Li/ξ)为奇数，则πi加1后的中点也是路径点，考虑到链路线Li按照πi划分，则链路线Li-1到达链路线Li具有πi+1条路线可供选择。

本文采用蚁群算法得到路径参数集合(h1，h2，…，hd)，目的是在离散道路空间中找到最短路径。假设有m个蚂蚁从起始点S到结束点T构成环形路径：S→n1j→n2j→…→ndj→T。其中，ndj表示位于链路线d中位置j的路径点。随着每个蚂蚁的移动，蚂蚁从链路线Li到链路线Li-1选择节点j的规则为

其中，I表示链路线中的路径点，q表示［0，1］之间的随机参数，q0表示［0，1］中的可调参数，τi，k表示关于信息素的启发值。

对于节点j的计算方法，首先计算从链路线节点i到下一个节点j的选择概率Pi，j，然后使用轮盘赌选择下一个节点j，其中选择概率Pi，j为

3.2 信息素更新的改进

本文所改进的信息素更新包括实时信息素更新和路径信息素更新。其中，实时信息素更新要求每个蚂蚁必须在选择节点之后更新节点信息素，即：

其中，τ0是信息素的初始值，ρ表示信息素的挥发因子，且其值为［0，1］的可调参数。

当所有蚂蚁从初始点移动到结束点时，即可完成迭代搜索过程。为了在所有蚂蚁移动到结束点时所选择的路径长度最短，还应更新每条道路上的路径信息素：

其中，Δτi，j=1/L*，L*表示最短路径的长度。

3.3 节点选择的改进

当蚂蚁搜索节点pi-1到下一个节点pi时，传统的蚁群算法是根据信息素和距离从所有可选节点pi=(pi1，…，pim)中计算蚂蚁移动到下一个节点的概率。每个节点选择都是为了减少从当前节点到结束点的总长度。因此，本文在选择节点pi-1到下一节点pi时，起始点与结束点之间的最短连线穿过所有可选节点(pi1，…，pim)构成的链路线，通过比较最短连线与链路线所构成的最大夹角来选择下一节点pi，如图1所示。在本文中，将使用此方法来查找下一个节点pi。

图1 节点示意图

4 实验分析

本文设计了一种基于MAKLINK图论建立物流配送路径网络拓扑模型，并基于改进蚁群算法构建了配送路径规划方案。

本文的实验内容和目标分为三部分。

1）在Matlab编程环境下构建物流配送运输环境的仿真模拟地图：假设起始点S到结束点T必须经过四个大型山脉，为了降低物流运输成本，运输车辆应尽可能地避免爬行山路，因此，所规划的物流配送路径需绕过这些山脉。所构建的物流配送地图及具体坐标信息如图2所示。

图2 构建物流配送地图

2）在Matlab编程环境下，对比各种参数的不同数值对改进蚁群算法迭代计算路径规划的性能影响，在对比参数不同数值前，先固定其他参数数值保持恒定，从而逐一确定改进蚁群算法计算过程中的参数寻优。

3）在Matlab编程环境下，对改进的蚁群算法和传统蚁群算法的物流配送路径规划结果进行性能分析，并且各自生成路径规划结果，验证本文提出的改进算法的有效性。

4.1 参数分析

1）蚂蚁数量对路径的影响

为了讨论蚂蚁数量对最优路径的影响，本文分析了六组不同的蚂蚁数量，图3给出了当蚂蚁数量m分别选择5、10或15时，随着蚂蚁数量的增加所规划的最短路径将逐渐减少。

图3 蚂蚁数量为5、10和15时的影响

相反，为了更细致地观察m=15、20和30时，随着蚂蚁种数的增加所规划的最短路径的波动变化，本文单独绘制m=15、20和30时的路径总长度变化，如图4所示。随着蚂蚁种数的增加所规划的最短路径将逐渐增大。因此，当m=15时，所提出的改进蚁群算法可以进行最优路径规划。

图4 蚂蚁数量为15、20和30时的影响

2）信息素浓度因子对路径的影响

图5表明，当信息素浓度因子α=1或2时，路径规划总长度的差异并不明显，但当α=1时，路径规划的收敛速度明显快于α=2，因此本文最后选择α=1作为信息素浓度因子参数。

图5 信息素浓度因子对路径的影响

3）路径期望因子对路径的影响

图6表明，当路径期望因子β=1时，路径规划的结果并不稳定。相反，当路径期望因子β=2时，路径规划结果较为稳定。因此，本文选择β=2作为路径期望因子，它在计算过程中可以得到比其他路径期望因子更稳定的路径规划效果。

图6 路径期望因子对路径的影响

4）信息素挥发因子对路径的影响

图7表明，当信息素挥发因子选择ρ=0.1时，随着迭代次数的增加最短路径逐渐收敛，当ρ=0.2或0.3时，路径规划结果随着迭代次数的增加而产生较大波动。因此，本文选择ρ=0.1可以进行更为理想的路径规划。

图7 信息素挥发因子对路径的影响

4.2 结果分析

本文选取了最优计算参数进行物流配送路径规划：蚂蚁数量为m=15，信息素浓度因子为α=1，路径期望因子为β=2，信息素挥发因子为ρ=0.1，迭代次数为500。图8给出了改进蚁群算法和传统蚁群算法的性能比较。

图8 算法比较

图8表明改进的蚁群算法比传统蚁群算法具有收敛效果。且传统蚁群算法计算的物流配送路径规划最优距离为205.5889km，而改进后的蚁群算法路径规划最优距离为194.5734km。图9给出了改进的蚁群算法和原始蚁群算法共同规划的路径。其中，实线代表采用改进的蚁群算法进行最优路径规划，虚线代表采用原始蚁群算法。结果表明，改进后的蚁群算法比传统蚁群算法可以规划出更好的物流配送路径。

图9 路径规划结果

5 结语

本文将改进的蚁群算法应用于物流配送路径规划问题，运用MAKLINK图论建立物流配送路径规划模型，选取Dijkstra算法作为初始规划算法并得到初始路径尺度参数，以此来确定蚁群算法的寻优目标函数。并对蚁群算法的信息素更新和节点选择进行了改进，通过该改进算法可以规划出从起始点到结束点的最优路径。通过与传统蚁群算法的仿真比较，结果表明，改进后的蚁群算法比传统蚁群算法具有更好的路径规划性能。