混合蚁群算法求解带时间窗的车辆路径问题

王 建，李红云，杨燕飞

Wang Jian，Li Hongyun，Yang Yanfei

（北京航空航天大学 交通科学与工程学院，北京 100191）

车辆路径问题（Vehicle Routing Problem，VRP）是营运车辆研究领域中一个具有重要理论和现实意义的问题[1]。由于该问题属于 NP-hard（Non-deterministic Polynomial Hard，非确定性多项式难题），所以寻找到一种高效而精确的算法的可能性微乎其微，而自然界中生物群体的合作与竞争等复杂行为产生的群体智能往往对解决某些特定的随机寻优问题提供了高效的解决方法，因此人们开始尝试利用仿生智能算法求解。

蚁群算法模型来源于对自然界真实蚂蚁行为的观测，蚁群在解决优化以及分布控制问题上具有很高的智能性，因此蚁群算法对解决复杂寻优问题的新型算法的开发与应用具有重要的启发价值。蚁群算法随机寻优机制的核心内容是分布性和协作性，而营运车辆具有同蚁群相似的分布性与协作性。目前采用蚁群算法求解车辆路径问题已经取得了很多的研究成果[2-4]。但是蚁群算法也存在着前期收敛速度慢，容易陷入局部最优等缺点。国内外学者针对蚁群算法存在的缺点进行一系列的改进，包括Max-Min蚂蚁系统，精英蚂蚁系统，基于排序的蚂蚁系统，基于混沌理论的蚂蚁系统等[5-6]，这些改进有一个共同的目的，就是在合理时间复杂度的限制条件下，尽可能提高蚁群算法在一定空间复杂度下的寻优能力，从而改善蚁群算法的全局收敛性，并拓宽蚁群算法的应用领域。

文中对蚁群算法的分布和协作机制进行了深入研究，在分析已有蚁群系统的优缺点的基础上提出了基于实时路况的 3层信息素更新策略，提出了考虑时间窗约束的基于多种蚁群系统的混合蚁群算法（Mixed Ant Colony Algorithm，MACO），在算法中充分考虑实时路况更新对道路通行能力的影响，以增强蚁群算法在求解动态车辆路径问题的算法性能。

1 车辆路径问题描述

营运车辆的调度问题属于车辆路径问题，但在普通的车辆路径问题上增加了一些约束，主要体现在以下3个方面：

1）营运车辆的调度不只是单纯地考虑最短路径，同时考虑车辆运行过程中所经路径等级、运行时间等问题，最终达到降低整体成本的目的；

2）营运车辆作为一种商业化的信息沟通形式，要充分考虑以人为本，要注重企业形象、提高顾客满意度；

3）营运车辆数目有限，载货量一定并且客户的订单具有时间要求。

营运车辆领域的车辆路径问题可以简单描述为：每个厂商都有一个仓库和一批客户集合，仓库即是配送中心，拥有K辆可用于调度的运输车辆，车辆的最大载重量、最大行驶距离和车况已知，每个客户的位置信息、需求信息已知，车辆都由仓库出发，经过若干客户点之后返回仓库，形成一个子回路，假如若干车辆构成的子回路集合可以完成对客户点的不重复遍历，那么就构成车辆路径问题的一个可行解。通过一定的算法以及约束条件寻找可行解，并从可行解的集合中发掘满足总行程最短或者总体成本最低的可行解就是营运车辆领域的车辆路径问题。

鉴于营运车辆调度问题与普通的车辆路径问题存在以上不同，同时我国“十二五”提出到2015年构建完善的营运车辆车联网系统，以完成对路况信息的实时更新，因此有必要对蚁群算法做出一定形式的改进，以适应企业对车辆的调度。

2 基本蚁群算法模型

蚁群在觅食过程中可以通过感知和释放一种带有气味的化学物质—信息素来实现相互之间的通讯交流[7]。生物学家已经指出，只要存在一种通过媒介质进行的间接传递信息途径，就可以解释蚁群如何实现有序的组织行为。蚁群算法的提出正是以此为基础，以一种人工媒介质的形式来实现群体之间的协作沟通。

蚂蚁在蚁巢与食物源之间往返，在前进和返回时都会释放信息素，并且自然界中蚁群的实际行为也证明这是寻找较短分支所必需的行为方式。

蚁群在蚁巢与食物源之间的随机寻优简化模型如图1所示。

参考图1，假设在t时刻分别有m只蚂蚁同时从蚁巢和食物源之间出发，路径AB的长度等于路径BC的长度，并且均为路径AD以及DC的2倍。此时路径ABC与路径ADC上的信息素浓度均为τ(t)，蚂蚁选择路径的概率严格与信息素浓度成线性比例关系，因此分别有p/2只蚂蚁选择ABC与ADC。当到达t+n时刻时，ADC路径上的蚂蚁已经从出发地到达目的地，然而由于路径较长，AB路径和BC路径上的蚂蚁在B点相遇，此时路径ADC的信息素浓度为

而此时路径ABC上的信息素浓度为

式中，τ(ρ)表示挥发掉的信息素数量，τ(*)表示每只蚂蚁在路上经过时对路径信息素浓度的贡献量。

由于蚂蚁选择路径的概率与信息素浓度成线性比例关系，因此

因此当以后的m-p只蚂蚁继续往返于蚁巢与食物源之间时，由于两条路径信息素浓度的不同而有越来越多的蚂蚁选择较短的路径而达到群体寻优的效果。

3 蚁群算法改进策略

将蚁群算法的思想用于求解营运车辆路径问题，要充分考虑客户订单的时间要求、位置要求等方面，因此对普通蚁群算法主要改进转移概率，信息素浓度更新以及最终可行解的选择3个方面。

3.1 相邻城市转移概率

在基本的蚁群算法中，蚂蚁转移概率只考虑道路长度和信息素浓度的影响，而在带有时间窗的车辆路径问题中，应综合考虑，做到紧急订单优先处理。因此其转移概率为

式中，τij(t)为在t时刻路径ij上的信息素浓度；ηij(t)为由节点i选择j点的期望值，一般情况下取ηij(t)=1/dij，dij为客户 ij之间的花费；ωij(t)是在 t时刻由城市i转到城市j的满意度影响因子；α，β，λ分别为信息素启发因子、路径选择期望值影响启发因子和满意度影响启发因子。顾客满意程度与送货时间有关，假定[aj，bj]为顾客点j的时间要求，在此范围内送到顾客的满意度为1，顾客能容忍的提前送到时间为，能容忍的最晚送到时间为。在提前和推迟送货时间内将货物送到的顾客满意度变化符合一定的三角函数规律，如图 2所示。

因此ωij(t)随送货时间的变化取值如式（6）所示。

式中，tj表示到达城市j的时间，其值等于到达顾客点i的时间加上在顾客点i的服务时间和由顾客点i到达顾客点j的路程时间。

在该转移概率算法中，充分考虑了时间窗对顾客满意度的影响，同时在不需要考虑时间窗的VRP问题中，通过将λ设置为0可以很方便地将顾客满意度的影响忽略。

3.2 信息素更新策略

3.2.1 信息素挥发自适应策略

线路非直线系数是路网布局规划中的一项重要指标。网络两节点（小区）间的非直线系数定义为该两节点（小区）间的路上实际距离与两点间空间直线距离之比。

首先统计车辆行经路径信息，并按照所经路径的质量，路径质量定义为实际距离与非直线系数的函数，即

式中，Rij为m×2维矩阵，1到m分别代表顾客点i到顾客点j的路段在路网中的功能等级，ψij代表顾客点i到顾客点j的路段的非直线系数。

定义信息素挥发因子

式中，ρ(t)为自适应信息素调整因子，R(i1)表示某段路径的功能等级数，s为道路集合。

采用自适应信息素调整后的全局信息素更新策略为

该调整因子的功能在于对道路进行排序处理，路程短且非直线系数小的道路属于精英道路，信息素挥发较慢，有助于加快算法收敛速度，当R(i1)过大的时候，则代表此段路径长度长且非直线系数大，此时ρ(t)有可能为负值，主要是为了避免算法陷入局部最优，使所有道路都有可能被选中。

3.2.2 考虑空间扩散特性的局部信息素更新

信息素在空气中的浓度与距离成反比，在以往的蚁群系统中，往往对信息素的扩散更新只是局限于一条道路，文中认为信息素在空间的扩散过程是三维立体扩散，信息素的扩散对周围道路亦产生影响，该信息素扩散策略更加忠实于自然界真实的蚂蚁系统，扩散过程如图3所示。

在简化的信息素扩散模型中，圆心的信息素浓度为τmax时，信息素在空气中的最大传播距离为2rmax，根据信息素浓度与传播距离成正比的原则可知，信源信息素浓度为τ时，信息素的最大传播距离为。

由此可得，距离信源为ri处的信息素为

从式（10）可以看出：距离信源越远，蚂蚁所接收到的信息素就越少。

该扩散策略充分考虑了与信源的距离和中央信息素浓度的影响，同时在算法中，考虑信息素的空间扩散，更加真实地模拟自然界中信息素的扩散机制，能够更加全面地反映路况，提高算法的收敛速度。

3.2.3 采用阈值判断的全局信息素更新策略

蚁群算法中容易出现的停滞和扩散问题不容忽视，将各条路径上可能的残留信息素量限制在[τmin，τmax]之间，以避免算法陷入停滞状态。这个信息素限制规则的作用是把位于城市 i的蚂蚁选择城市 j作为下一个访问城市的概率 pij限制在[pmin，pmax]内，其中0

基于阈值判断的信息素更新策略如下

假定在任何一次迭代结束之后，任意一条边（i，j）上的信息素的最大增量为qf(s*)，因此可得在第 1次迭代中的信息素的最大值为(1-ρ)τ0+qf(s*)，在第 2次迭代之后最大值为(1-ρ)2τ0+(1-ρ)qf(s*)+qf(s*)，以此类推，考虑信息素挥发之后，第NC次迭代结束之后的信息素的值应该小于等于下式

因为0<ρ≤1，因此式（12）渐进和收敛于

每当发现一条新的最优路径，就按照式（13）更新τmax的值，相应地，信息素的下界被设定为τmin=τmax/a，其中a是一个参数。

3.3 可行解的构造方法

由于在VRP中，每辆营运车辆所经过的只是客户集合中的一个子回路，所有蚂蚁子回路的集合构成的解有可能为可行解也有可能得不到可行解。若在有限的迭代次数内经常得不到可行解，则会造成算法的时间复杂度大幅度增加，影响车辆调度系统对车辆的有效调度，无法完成企业降低成本等方面的要求，因此文中提出当算法到达一定的迭代次数并未找到可行解时，放弃寻找可行解并转向将所得近似解进行可行化的算法以降低计算量，防止算法陷入搜索停滞状态。

按照文献[8]中给出的定义，近似解有2种，分别为最大未满非可行解和最小溢出非可行解[8]。对于未满非可行解按照节约算法将未出现在路径中的点插入到现有路径中，同理对于最小溢出非可行解可以将多次出现的客户点通过插入可行解任意一个子回路的方式抹去。

若到达一定迭代次数时没有找到可行解，并且还存在没有被调用过的车辆，则需要比较单独使用未调用车辆去服务未出现的客户点与直接将该客户点插入至未达到最大载货量与最大行驶距离的子回路的成本，成本较低的方案即为寻找的可行解。

若近似解已经完成对全部车辆的调用，则算法需要遍历将未出现客户点插入至子回路产生的成本总和，最低成本者同样为寻找的可行解。

4 MACO算法步骤

根据上述蚁群算法改进策略，提出的 MACO算法求解步骤如下。

1）算法开始进行时，初始化MACO的参数：τmin, τmax, h, allowedk，[aj，bj]，s，R，α，β，设置迭代次数NC，初始化各条路径上的信息素，将m只蚂蚁均匀地放在 N个节点上，更新 allowedk，tabuk；

2）将 m只蚂蚁放在初始节点，迭代次数NC=NC++；

3）蚂蚁从allowedk中选择下一步允许到达的城市，根据转移概率公式进行移动；

4）判断载重量是否已经达到极限，若是，则转到第5步，若否，则转到第3步；

5）蚂蚁k返回原点，构成一个子回路；转到第2步，若tabu[k]未满，则从初始节点继续出发；

6）根据动态挥发原则，更新局部路径信息素；记录本次最优路径，更新全局信息素；

7）若Nc

8）判断可行解是否找到，若找到，转到第9步，若没有找到，找到近似解，通过节约算法将近似解可行化，转到第9步；

9）输出结果。

5 仿真验证

为了便于检验算法的性能，用改进的MACO算法在C#中进行了仿真计算。文中采用Marius M等在文献[9]中所述的基准VRPTW实例，这些实例共有56个，这56个实例中都含有100个客户和1个中心仓库，并规定了车辆负载、客户的时间窗和车辆运行时间[9]。

实验开始，在每个城市都放置一只蚂蚁，蚂蚁的个数与客户的数目相同，设置α=1.0，β=5.0，信息素挥发因子ρ=0.12，ω1=0.68，ω2=0.32，NC=40，τmax=1，τmin=0.024。

文中选取56个实例中的10个进行仿真计算，实验结果见表1。

表1 实验结果

仿真结果表明，算法具有快速寻优的能力，能够在很短的时间内找到可行解或者找到近似解进行快速可行化，并且通过对实验结果求平均值可以知道算法的寻优结果稳定，有效地改进了蚁群算法求解时间长，容易陷入局部最优的缺点。

6 结 论

文中提出的混合蚁群算法（MACO）在处理带有时间窗的车辆路径问题中具有计算结果稳定，跳出局部最优，计算时间短的优点。除此之外，算法还有以下优点。

1）提出的信息素挥发自适应策略能够根据实时道路状况调整信息素的挥发快慢，可以扩展算法完成动态调度问题；

2）将蚂蚁转移概率中的ωij设置为1可以很方便地求解不带时间窗的车辆路径问题或者经典旅行商问题；

3）修改迭代次数可以在保证计算量的前提下保持较好的寻优稳定性。

[1]Jose Brandao.A Tabu Search Algorithm for the Heterogeneous Fixed Fleet Vehicle Routing Problem.[J]Computers&Operations Research.2011，38（1）：140-151.

[2]Ren yingtao，Maged Dessouky，Fernando Ordonez.The Multi-shift Vehicle Routing Problem with Overtime[J].Computer&Operations Research.2010，37（11）：1987-1998.

[3]R.Tavakkoli Moghaddam，M.Gazanfari，M.Alinaghian.A New Mathematical Model for A Competitive Vehicle Routing Problem with Time Windows Solved by Simulated Annealing[J].Journal of Manufacturing Systems.2011，30（2）：83-92.

[4]Habibeh Nazif，Lai Soon lee.Optimised Crossover Genetic Algorithm for Capacitated Vehicle Routing Problem[J].Applied Methematical Modeling.2012，36（5）：2110-2117.

[5]W.Y.Szeto，Yongzhong Wu，Sin c.Ho.Anartificial Bee Colony Algorithm for the Capacitated Vehicle Routing Problem[J].European Journal of Operational Research.2011，215（1）：126-135.

[6]Zhang xiaoxia，Tang lixin.A New Hybrid Ant Colony Optimization Algorithm for the Vehicle Routing Problem[J].Pattern Recognition Letters.2009，30（9）：848-855.

[7]桑国珍，王峰，杨瑞臣.改进的蚁群算法求解VRP问题[J].现代电子技术， 2010（12）：75-77.

[8]段海滨.蚁群算法原理及其应用[M].北京：科学出版社， 2005，238-249.

[9]Marius M，Solomon M.Algorithms for Vehicle Routing and Scheduling Problems with Time Window Constrains[J].Operation Research.1987，35（2）：763-781.