基于自适应动态搜索蚁群算法的车辆路径规划

贺智明，郑 丽，梁 文

(江西理工大学 信息工程学院，江西 赣州 341000)

0 引 言

车辆路径问题(vehicle routing problem，VRP)是指一组车辆从指定点出发，且遍历到一系列特定点的路线[1]。由于该问题的传统求解方法效果不佳，如精确算法[2]和启发式算法[3,4]。因此，学者们将AI技术与启发式算法结合，如：模拟退火算法[5]、禁忌搜索算法[6]、遗传算法[7]和蚁群算法[8]等。相对而言，蚁群算法(ant colony，ACO)在寻径方面占据独特优势。然而，当问题规模较大时，算法易陷入局部困境，无法对搜索空间进行深层次挖掘。为此，学者们做出不同的改进，例如：文献[9]将人工免疫和ACO算法相结合，有效解决紧急粮食分配问题；徐坤等[10]将信息素挥发因子采用莱维飞行模式更新，提高了算法的全局寻优能力；王飞鹏等[11]在求解TSP问题的最优解集中按比例选取部分解集构造近似骨架，并基于近似骨架对问题分段求解，有效解决算法精度不高等问题。

上述改进方法主要通过改变部分更新规则或同其它算法互补。然而ACO算法中关键参数的设置以及群体的合作行为都直接影响着算法性能。为此，本文提出自适应动态搜索蚁群算法(ADACO)，通过实验性配置关键组合参数和自适应伪随机策略协助群体选择合理的转移方向。此外，信息素强度的分段化设定有效预防了群体长时间滞留于困境中而无法跳脱的现象，减少了时间开销。

1 模型建立

本小节针对车辆路径问题建立数学模型，其中包括模型假设、符号说明和目标优化函数的设定。

1.1 模型假设

依据实际问题对该模型做出如下假设：

(1)指定配送中心负责完成一系列需求点的配送服务；

(2)配送中心以及各个需求点的相对地理位置和对应需求量是明确给定的；

(3)车辆配送完毕，返回指定配送中心；

(4)配送车辆是同种规格，不存在些许误差；

(5)不考虑城市交通堵塞问题；

(6)配送车辆始终以匀速行驶，单位距离内的配送成本是等同的，因此行驶距离可代表配送成本；

(7)每个需求点当且仅当由一台配送车辆服务，且该车辆服务的所有需求点的需求量之和小于或等于车辆的额定限载量。

1.2 符号说明

该模型包含的相关符号说明见表1。

表1 相关符号说明

1.3 设定目标优化函数

首先，决策变量如下

目标优化函数如式(1)所示

(1)

其中，cij计算如式(2)所示

(2)

cok表示配送中心调度成本；cs表示单位距离内车辆行驶成本；当i=0时，需要配送车辆越多，总的成本也随之增加。由式(2)可知，减少配送车辆的派遣数量以及缩短车辆的行驶距离是降低配送成本的关键所在。

相关约束条件如式(3)至式(11)所示

(3)

(4)

(5)

(6)

(7)

(8)

xijk(xijk-1)=0，i=1,2,…,n
j=1,2,…,nk=1,2,…,m

(9)

yik(yik-1)=0，i=1,2,…,nk=1,2,…,m

(10)

(11)

其中，式(1)表示配送总成本达到最小；式(2)表示成本费用计算；式(3)表示车辆k单次累计配送量不高于车辆额定限载量；式(4)表示车辆k单次累计配送距离不超过车辆最大限定行驶距离；式(5)表示单个需求点i仅由一台车辆负责配送；式(6)表示共有m台车辆参与配送；式(7)和式(8)表示两个变量之间的关系；式(9)和式(10)表示两变量均满足0-1约束；式(11)表示配送过程中不存在回路现象。

2 ADACO算法

2.1 基本蚁群算法

M.Dorigo，V.Maniezzo和A.Colorni等意大利学者长期研究自然界中蚁群觅食寻径行为，发现不管地理环境多复杂，蚁群经常能克服重重困难和阻碍，在洞穴和食物之间找到一条最佳路径。究其根本，蚂蚁在走过的路上均会放置一种称之为“信息素”的分泌物质。某条路径上经过的蚂蚁越多，分泌物则堆积越多，分泌物的浓度也会不断增强。此外，蚂蚁对该分泌物具有一定的感知能力，它们会根据路径上分泌物浓度的高低去选择路径。然而，随着时间的逐步增加，分泌物质会出现渐进式蒸发现象。因此，路径上剩余分泌物质浓度的高低与吸引后来蚂蚁数量的多少成正比，从而形成一种正反馈机制。这种机制能够帮助蚁群在“深度挖掘”和“合理利用”之间寻求一个最佳临界点，即时找到最佳路径。为此，学者们多次模拟该生物相互合作的社会性和组织性群体行为，最终在20世纪90年代初期提出启发式ACO算法[8]。图1从整体视角规划出该算法的逻辑结构，为解决实际问题提供了清晰而有力的帮助和支持。

图1 ACO算法的基本逻辑结构

2.2 基本算法模型

ACO算法一经提出，学者们纷纷将蚁群寻径思想运用到经典TSP问题上。近些年来，学者们又在单回路TSP问题上逐步衍生出多回路TSP问题，即VRP问题。换言之，TSP是VRP的基础问题。因此,本小节以求解TSP的ACO算法为基础建立求解VRP的ACO算法模型。

(12)

其中，Jk(i)={1,2,…,n}-τk表示蚂蚁k下一步允许选择的城市；列表τk记录着此次迭代中蚂蚁k的已访问城市，在接下来的遍历中不能再次访问列表τk中的城市；τij(t)表示t时刻路径(i,j)上信息素的数量；ηij表示启发因子，一般取路径(i,j)距离的倒数：ηij=1/dij；α和β分别表示路径上信息素累积量和启发信息的权重比例。

当所有蚂蚁均实现遍历任务后，各条路径上的信息素数量根据式(13)和式(14)更新

τij(t+n)=(1-ρ)τij(t)+Δτij(t)

(13)

(14)

(15)

其中，Q为正常数，Lk表示蚂蚁k在此次迭代中所走过的路径长度。

2.3 ADACO算法设计

针对ACO算法的不足，本文基于原有算法的框架做出一些改进，以提高算法的性能和效率。

本文采用随机性选择和确定性选择相结合的策略，并自适应性调整转移概率，引导算法探索最优路径和提高算法的收敛性能。详细地讲，算法在搜索之前，根据式(16)中的伪随机分布转移规则(pseudo-random distribution transition rule，PRDTR)先执行状态转换的选择操作，使得搜索个体更加倾向于选择信息素累积量多且距离较近的城市j

(16)

(17)

(2)信息素强度的动态调整

由式(12)可知，当α=0时，只有路径启发信息β发挥着作用，此时算法等同于最短路径寻优，如式(18)所示

(18)

当β=0时，路径启发信息β为0，只有路径信息因子α引导搜索个体进行单纯性地随机搜索，如式(19)所示

(19)

为使算法能够在α和β的相互作用下始终维持在“深度探索”和“合理利用”的临界点。本文采用式(20)中的分段函数Qi替代式(15)中的常数Q，使得路径上信息素数量变化时，群体均能够有根据地选择路径，改善了群体寻径时的盲目性选择

(20)

其中，式(20)对应着不同区间内的不同取值。当函数最优值在某一时间段内持续没有变化，说明整个搜索过程可能陷入局部误区，此时分段函数的设定强制增加或减少路径上信息素数量的导向，赋予算法跳出局部误区的能力。

2.4 ADACO算法描述

通过2.1至2.3小节对基本ACO算法、算法模型及其改进方面的详细介绍，本文提出ADACO算法，且该算法求解车辆路径问题的伪代码描述如下：

算法1：求解车辆路径问题的ADACO算法

输入：目标优化函数minZ，关键参数α、β、ρ，最大迭代次数iterations，起始点蚂蚁只数o等各项相关实验参数，起始点和一系列需求点的位置坐标、相应需求量。

输出：全局配送方案及配送成本

(1) nc=1

(2) while nc≤iterations// 停滞条件

(3) for k=1：o// 对o只蚂蚁循环

(4) whileτk=0 // 禁忌表为0

(5) for j=1:n// 对n个需求点循环

(6) if 禁忌表τk中不包含需求点j

(7) 将需求点j添加到待访问需求点列表Jk(i)中

(8) end if

(9) end forj

(10) forj= 1:Jk(i)

(11) if 剩余车载量≥待访问需求点的需求量

(12) 根据式(16)选择待访问需求点j， 计算装载距离，并更新禁忌表τk和待访问需求点列表Jk(i)

(13) else

(14) 起始点重新发出一台车且车辆编号加1， 按照式(16)和式(17)继续遍历剩余的待访问需求点j

(15) end if

(16) end forj

(17) end whileτk

(18) 计算构造解的路径长度， 即配送成本

(19) end fork

(20) 依据式(13)-式(15)和式(20)更新各路径信息素增量Δτij， 进而更新全局路径信息素τk

(21) nc = nc +1

(22) 清空禁忌表τk

(23) end while nc

(24) 输出最佳配送方案以及对应的配送成本

针对上述伪代码的描述，分析其时间复杂度：第(5)-第(9)步设置待访问需求点列表的时间复杂度为O(n)，第(10)-第(16)步单只蚂蚁通过自适应伪随机选择并遍历需求点的时间复杂度均为O(n)，第(4)-第(17)步单只蚂蚁构造解的时间复杂度为O(n2)，第(3)-第(19)步o只蚂蚁构造解的时间复杂度为O(o·n2)，第(2)-第(23)步o只蚂蚁经过iterations次循环的时间复杂度为O(o·n2·iterations)。由此可以看出ADACO算法较原有算法没有增加多余的时间开销，由此验证该算法的可行性。

3 实验计算与分析

为了验证算法改进前后的高效性，本文采用郑州市“家辉生鲜”连锁店货物配送问题作为实验案例，其测试环境：Windows操作系统；i5处理器；双核2.5G CPU；4.0 G内存；1 T硬盘；MATLAB R2016a仿真平台。

3.1 案例描述

该连锁店的仓库每天都会向各个连锁分店进行生鲜补给，最大化满足广大顾客的生活需求。以下是通过高德地图获取到仓库以及20个分店的相对位置，如图2所示。编号1-20是各个连锁店的分布位置，“★”代表仓库的位置。

图2 仓库及连锁分店的分布位置

为了方便测试，将仓库及各个连锁分店的位置坐标映射至XOY平面上，其中仓库编号为0，对应的位置坐标为(100,400)。各连锁分店的位置坐标及对应的每日需求补给量见表2，表2中的位置坐标信息转化到直角坐标系上，如图3所示。

表2 连锁分店位置坐标及补给量

3.2 参数设置

ACO算法中，庞大的参数系彼此关联，密切影响着算法的性能，其中起主要作用的参数分别为：路径信息素因子α、路径启发因子β和信息素蒸发比例ρ。因此，α、β以及ρ的组合配置是衡量算法性能指标和求解效率的关键因素。

图3 直角坐标系下仓库及连锁分店的位置分布

为了得到组合参数的最佳配置，本小节在上述测试案例的TSP问题上进行实验，按照修改一个参数的值，另外两个参数值保持不变的规则斟酌最佳参数的设定。初始默认参数为α=1，β=1，ρ=0.7，iterations为100次，每组实验分别运行10次，实验结果如图4所示。

图4 α、β、ρ的不同配置对算法性能的影响

其中，最差、平均、最优路径长度以及差值分别表示10次运行结果中的最大值、平均值、最小值、最大值与最小值之差。差值越小，说明系统越稳定，解的质量也越好。上述实验结果可以看出3个关键参数的最佳配置为：α=1，β=4，ρ=0.7。

结合案例，其它相关实验参数设置见表3。

3.3 案例验证及结果分析

本小节在“家辉生鲜”实际案例中，对4种算法进行测试和对比分析。其中，对改进的两个方面分别测试，得到自适应转移蚁群算法(AACO)和动态导向蚁群算法(DACO)，另外两组则为ACO算法和ADACO算法。

表3 相关实验参数设置

表4列出了4种算法各自运行10次所对应的配送成本、收敛代数以及CPU运行时间。在配送成本和收敛代数两方面，ACO算法的配送成本大多集中于4750附近，最大值为4758，最小值为4744，始终没有一个较大的突破，收敛代数也呈现跌宕起伏的状态，不具稳定性；AACO算法的配送成本则相对稳定，主要趋于4729附近，其中配送成本为4725的概率占据30%，收敛代数同样没有明显的规律性；DACO算法得到的配送成本较于前两者更具稳定性，始终维持在4710-4715之间，且4710出现的概率为40%，迭代次数也相应收敛于30代。对比前三者可知，ADACO算法不仅在配送成本方面则有了一个实质性的进展和突破，不再局限于4700的约束，且以50%的概率归拢于4674，而且最佳的收敛代数曾达到26.26。此外，10次运行结果中，4种算法的CPU运行时间都是参差不齐的，但是观察其最佳值、平均值和最差值，ACO算法均高于其它3种算法，而ADACO算法则略胜一筹。

表4 各算法的运行结果比较

通过对4种算法运行10次结果的纵横对比以及多方面分析，得到AACO算法、DACO算法和ADACO算法较于ACO算法的提升力度和改进空间，见表5，ADACO算法提升力度尤为明显。

表5 各类算法较于ACO算法的提升力度/%

对照表4中的相关数据，图5给出了ACO算法中最差配送方案及其对应且出现次数最多的配送成本和收敛代数。图6-图8则给出了其它3种算法的最佳配送方案、配送成本以及收敛代数。

观察图5-图8可得，4种配送方案中2号和4号车辆的行驶路线一致，1号和3号车辆的行驶路线稍有差别，配送成本也是各不相同。其中，各方案中单位车辆的行驶路线及配送成本见表6，图9也直观地展示了4种方案的细微差别。对照图表，并结合相关实验数据综合性地研究和分析，ACO算法在第32代绘制出最佳配送方案，如图5(a)所示。表6显示了该算法中1号车辆的行驶路线为：0-20-16-14-13-12-0，该车辆在遍历完20号、16号分店后转向14号分店，直接违背了公理“两点之间线段最短”，由此可以判定该路线不是最优的。此外，从图5(b)可以看出，该算法在第5代的配送成本几乎接近4710，有突破瓶颈的迹象，然而却没能稳定于这一点，而且算法长期处于动荡搜索状态，最终归拢于4758，说明该算法具有一定的提升空间；AACO算法和DACO算法分别在第29代和第31代绘制出最佳配送方案，如图6(a)和图7(a)所示。对比这两种配送方案，清晰地看到两者之间仅3号车辆的行驶路线略有不同，但总的配送成本却相差15，这项差值充分说明DACO算法中3号车辆的行驶路线是可取的。从图6(b)可得知，AACO算法同比ACO算法在收敛代数上缩短了9.68%，并降低了0.69%的配送成本。图7(b)清楚显示DACO算法在第20代有陷入局部困境的迹象，但信息素强度区间性设置引导群体在第30代及时逃离困境构造新的解，并且配送成本最终降低并稳定于4710；图8显示ADACO算法的最佳配送方案于第27代绘制完毕，同图7(a)相比，两者仅1号车辆的行驶路线不同，然而对应的配送成本却迅速降低到4674，而且也不存在交叉或ACO算法中1号车辆的绕路现象，由此可判断ADACO算法1号车辆的配送路线为最佳路线。此外，ADACO算法中3号车辆的行驶路线与DACO算法相同，均为可取路线。

图5 ACO算法规划的配送路线及配送成本

图6 AACO算法规划的配送路线及配送成本

图7 DACO算法规划的配送路线及配送成本

图8 ADACO算法规划的配送路线及配送成本

表6 单位车辆具体配送方案及配送成本

图9 4种算法单位车辆的配送成本

综上所述，AACO算法和DACO算法较于原有算法在时间效率和配送成本方面均有小幅度提升，然而却远远不够。通过将两种改进方法进行有效结合，吸收两者优点得到ADACO算法，而且ADACO算法也展示了具有突破性进展的优化效果以及全面的提升能力。由此可见，ADACO算法在求解车辆路径问题上更具高效性。

4 结束语

针对原有算法求解车辆路径问题时的不足，本文在初始时刻对关键参数采用试凑法设定，保证群体充分利用有效信息。迭代初期引入时变参数，并在择径之前产生一个随机数与之比较，使得群体按照既定的伪随机自适应规则选择转移方向。当算法状态持久不变时，信息素强度的分段化有效诱导群体跳脱困境继续探索。最后基于测试案例对优化前后的算法进行多次仿真，结果表明所提算法规划的配送方案最优，大幅度缩减了配送成本和时间开销。本文算法适用于以菜鸟驿站为代表的物流业务，为了满足多元化需求，派送和拾取同步进行且增加时间窗的服务将作为下一步的研究方向。