改进蚁群算法在带时间窗车辆路径规划问题中的应用

雷金羡，孙 宇，朱洪杰

(广西大学 计算机与电子信息学院，广西 南宁 530004)

0 引言

车辆路径规划问题(Vehicle Routing Problems,VRP)自1959年被提出后，引起了国内外研究者们的关注，随着经济和电子商务的快速发展，该问题已成为众多学者研究的热门问题之一[1]。VRP配送中心在满足客户需求和约束的限制下进行路径规划，目的是找到成本最低的路线。经过多年的研究，VRP已经拓展出许多更具实际意义的研究问题[2]，带时间窗的车辆路径问题(VRP with Time Window, VRPTW)是其中之一。VRPTW在基本VPR问题上对客户接收货物的时间段进行了约束，客户只在某一段固定时间接受送达的货物，超过这个时间段则拒绝接受货物，在此约束下找到一条最优路径[3]。解决这一问题的方法一般分为精确式算法和启发式算法两大类。

精确式算法是一类能够求出最优解的算法，一般用于解决复杂度较低的组合优化问题，常用的算法有线性规划法、贪婪算法、动态规划算法等[4]。然而，随着问题研究的不断深入，VRP也变得更加复杂，数据量更大，精确算法对于这类较为复杂的组合优化问题的计算时间将呈指数增长[5]。因此，为了能够在可接受时间内得到可行解，通常采用启发式算法。启发式算法可以在一定的时间和范围内求解得到精度较高的近似解[6]，常用于解决VRP的启发式算法包括：遗传算法[7]、禁忌搜索算法[8]、模拟退火算法[9]、蚁群算法[10]、粒子群算法[11]等。

蚁群算法(Ant Colony Optimization,ACO)是一种通过模拟自然界蚂蚁觅食行为来优化实际问题的智能优化算法，最早由意大利学者DORIGO等[12]在上个世纪九十年代提出。蚁群算法寻优的基本思想是：以巢穴为出发点，食物源为目的地，蚂蚁开始搜索行为时会沿路释放一种蚁群之间能够相互识别的化学物质即信息素(pheromone)。一开始搜索时蚂蚁的行为没有信息素的指导，各个蚂蚁随机选择路径，同时沿路释放信息素。随着时间的推移，蚂蚁们各自找到了食物，并在路径上留下信息素。由此多次往返后，在单位时间内，短路径上留下的信息素浓度更高。而蚂蚁会趋向于选择走高浓度的路径，在后续搜索中越来越多蚂蚁选择短路径，最后得到一个最短路径的解[13]。由算法思路可知，由于蚁群算法不需要初始解，在不同的环境下能够自动地调整寻优路线，体现了其具有正反馈机制、与其他算法结合的适应性强、鲁棒性强、自适应能力强的特点[14]。

但是传统蚁群算法因为过于依赖信息素的引导，所以存在容易陷入局部最优，收敛速度慢、参数难以精确设置等缺点。针对这一缺陷，ZHANG等[15]改进了蚁群算法中的状态转移概率计算方法，降低信息素对蚂蚁选择路径的影响，将局部搜索能力较强的2-optimization(2-opt)算法加入到现有解的优化中，弥补了蚁群算法在局部寻优方面的不足；LU等[16]使用最大最小策略更新信息素，目标是实现最小—最大或劳动平衡的目标，通过面向任务的方法将蚂蚁分配到团队中，最终达到优化算法的目的；YAO等[17]也针对容易陷入局部最优的问题提出改进的蚁群算法(Improved Ant Colony Optimization,IACO)算法，加入了一种扫描策略，并使用交叉操作来扩大算法的搜索空间；方文婷[18]等针对蚁群算法在前期的搜索阶段，因信息素不足而导致收敛速度慢的问题，结合A*算法的全局收敛性对蚁群算法进行改进，提出一种混合算法，并证明了其有效性；何美玲等[19]在传统蚁群算法中加入变邻域搜索算法来加强局部搜索的能力，并设置了进入局部搜索阶段的条件，当连续两次迭代结果相同且信息素挥发系数在设定的范围内时，就进入局部搜索阶段等。因此，本文针对其容易陷入局部最优的缺点，在信息素更新方式上借鉴最大最小蚁群(MAX-MIN Ant System, MMAS)方法[20]进行了改进，同时在迭代过程中动态调整信息素挥发因子的大小，并加入2-opt(2-optimization)算法、顺序交换策略、顺序插入策略优化其每次迭代得到的最优路径。将改进算法应用在VRPTW上，并通过实验证明了改进算法的有效性。

1 VRPTW数学模型

VRPTW是VRP的一个拓展，在VRP的基础上增加了一个最主要的时间窗约束，使问题的研究更具现实意义。

1.1 问题描述

配送中心通过配送车辆完成向客户配送货物的任务，已知客户点的位置、客户接受服务的时间区间、服务时长、车辆容量、客户的货物重量等信息，车辆在进行货物配送时，有以下约束[21]：

(1)车辆只能在客户接受的时间区间内对客户进行配送服务，否则客户会拒绝接受服务；

(2)每个客户只能被走访一次；

(3)车辆的载重不能超过车辆容量；

(4)车辆只能从配送中心出发，最后返回配送中心。

本问题的目标是在满足上述约束的情况下，找到一条成本最低的路线[22]。

1.2 建立模型

根据以上问题描述建立的相应的VRPTW模型中[23]，可将配送中心和客户点视为一个无向图G(V,A)，其中顶点集V={v0，v1，v2,…,vN}表示1个配送中心和N个客户点的集合，其中v0表示配送中心，{v1，v2,…,vN}表示N个客户点，配送中心要为N个客户点进行配送服务；边集A={(vi，vj)|vi，vj∈V,i≠j}表示每个点之间都存在可行路径；K表示车辆集合；dij表示车辆从i点到j点花费的距离；tij表示车辆从i点到j点已花费的时间；ci表示客户点i的货物重量，即服务量。

目标函数：

(1)

约束条件：

xijk∈{0,1}，

(2)

ai+si+tij>bi，

(3)

(4)

(5)

式(2)中的xijk表示车辆k是否经过点i和点j之间的路径，若经过，则xijk=1，否则xijk=0。由此，式(1)中用xijk的取值来判断车辆是否经过i和点j之间的路径，将车辆k经过的所有客户点进行累加，然后从K辆车的路线中取距离最短的路线作为目标函数值z。客户i接受服务的时间区间为[ai,bi]，si表示在客户点i的服务时间，则式(3)保证车辆服务客户点的时间必须在客户指定的时间内进行；式(4)表示每个客户点只能进行一次服务；式(5)表示每辆车的载重不能超过车本身的容量。

2 蚁群算法

自蚁群算法提出后，许多学者将蚁群算法改进后应用于更多的组合优化问题中，且都在不同程度上展现出了较为良好的成果[24]。

(6)

其中ηij(t)为根据自身自适应定义的启发函数，

(7)

城市i与j之间的距离用dij来表示，dij和ηij(t)成反比关系，dij越小，ηij(t)越大，则状态转移概率p也越大，由此ηij(t)代表蚂蚁由城市i转移到下一个城市j的期望量值。

所有蚂蚁在一次迭代中完成走访全部城市的任务后，为避免信息素积累过多导致覆盖了还未探索的路径启发信息，需对信息素进行及时的更新处理。

τij(t+1)=(1-ρ)·τij(t)+Δτij。

(8)

其中ρ表示信息素挥发系数，会直接影响到整个蚁群算法的全局搜索能力和收敛速度，(1-ρ)则是信息素的残留因子，体现了蚂蚁个体之间相互影响的强弱程度，ρ的取值范围：{ρ|0<ρ<1}，初始τij(0)=0。Δτij为本次迭代中的信息素增量，可表示为：

(9)

式中：Q是一个常量，表示蚂蚁本身携带的信息素的固定值；Lk代表本次迭代蚂蚁k走过的路径。

3 改进蚁群算法

本文对蚁群算法的改进主要在3个方面：①改进更新信息素的方式;②对信息素挥发因子ρ进行阶梯式调整;③加入了2-opt算法、顺序插入策略、顺序交换策略进行改进。

3.1 改进信息素更新方式

在信息素更新方式上作了3个方面的调整：

(1)在每次迭代结束更新信息素时只更新最优路径的信息素；

(2)在更新信息素时增加一个奖励值；

(3)对信息素的值设置动态的限制区间。

下面对以上3个方面的调整进行详细说明。

3.1.1 更新最优路径的信息素

由信息素增量式(8)可知，基本蚁群算法更新信息素时在每只蚂蚁走过的路径上都增加了信息素，这样的更新方式使得信息素的累积较快，迭代一段时间后会导致最优路径和其他路径的信息素形成一个较大的差值，蚂蚁们在后续迭代中更倾向于选择这条最优路径，从而丧失了寻找其他更优路径的能力，最终使整个算法陷入局部最优。针对该问题，本次改进将在每次迭代结束之后只更新最优路径bestroute上的信息素值，并加上一个奖励值award，信息素更新方式为:

(10)

式中，bestroute已经更新为本次迭代中的最优路线，只更新最优路径上的信息素值能够相应地降低路径上积累信息素的速度，使信息素在早期的时候的引导作用较小，从而提高全局搜索能力。

3.1.2 增加奖励值

在更新信息素增加一个奖励值award，目的是加强信息素的引导，保证算法早期的搜索质量，award具体计算方法为：

(11)

式中bestroute是还未更新的最优路线长度，而nowbestroute是当前迭代得到的更好的最优路线长度，则nowbestroute的值越小，award值也越大，通过award值达到了奖励最优解目的。award值奖励了找最优路径的蚂蚁，在削弱信息素早期引导能力的同时，也通过奖励机制保证了蚂蚁在前期搜索的质量，对后期的搜索起到一个指导作用。

3.1.3 设置信息素的限制区间

(12)

(13)

3.2 改进信息素挥发因子

信息素挥发因子ρ决定着信息素存留在路径上的持久程度，若ρ过小，信息素存留在路径上的时间长，虽然具有较强的引导能力，但是随着时间的累积，很有可能限制整体的全局搜索能力，陷入到局部最优的情况中；若ρ过大，路径上存留的信息素较少，虽然可能在早期能够提高全局搜索能力，但是在一定程度上会减弱信息素的引导能力，整体进入盲目的搜索状态，从而得到不稳定的结果。因此，ρ的取值会影响整体算法的搜索能力和效率，根据这一特点，本文对ρ值的设置进行了改进。随着迭代次数的增加，信息素挥发因子ρ也逐步增大，以适应蚁群搜索过程中信息素浓度的变化。

(14)

其中：n表示当前迭代次数，N表示总迭代次数。一开始ρ设置为一个较小的值，目的是保持蚁群算法搜索的特点，在前期通过信息素的引导，找到一些较好的路径；进入迭代的第二阶段，也就是0.25N之后，路径上的信息素积累到较大的值，开始加大挥发力度，以防止一些路径信息素浓度累积过高，存在陷入局部最优的风险；三阶段的调整在迭代次数为0.75N时进行，路径上的信息素浓度都已达到一个较大的值，相应地增大ρ值。

3.3 多策略改进

(1)2-opt算法 2-opt是一种局部搜索算法，原理是随机获取路线上的两个点，将这两个点之间的点都进行逆序翻转，两点外的其他点顺序不变[26]。图1a可以表示为一个VRP的路线图，0为配送中心，其他点为客户点。路线3的原路径为：(0，10，6，8，7，3，0)，假设随机获得了点7和点6，经过翻转后，得到的路径为：(0，10，7，8，6，3，0)。

(2)顺序交换策略 顺序遍历每一客户点，将当前客户点与同一路线内和不同路线之间的客户点位置进行交换，如图2所示。图2举例说明了路线间的客户点交换，假设图2a遍历到了路线2中的点3和路线3中的点2，这两个点进行交换，即得到图2b中的结果。

(3)顺序插入策略 顺序遍历每一客户点，将当前客户点插入到同一路线或不同路线中的客户点位置，如图3所示。图3举例说明了在路线间插入客户点的情况，假设图3a遍历到了路线2中的点3，将点3插入到路线3中，即得到图3b中的结果。

本文使用这3种策略对蚁群算法每次迭代后得到的最优路径进行优化。根据VRPTW约束，最优解中会出现多条回路，因此多策略将会对每一条回路进行调整优化，调整次数设置为每条路径的节点数，以此来适应数据的变化。每一次调整后都会判断是否能够得到比初始解更好的路径，若调整后出现更短的路径则替代原路径。

4 改进蚁群算法在VRPTW问题上的应用

本章采用Java语言编写了改进算法，主要进行了两个实验：第一个实验将本文的改进算法应用在Solomon Benchmark problem的算例 C101上，并调整迭代次数，与官网结果进行对比；第二个实验将本文改进算法与基本蚁群算法同样应用在算例C101上进行对比。两个实验均得到了较好的结果，本章将对实验及结果进行分析比对。实验环境为：Windows 10系统，Intel(R)Core(TM)i5-7300HQ CPU @ 2.50 GHz。

4.1 参数设置

蚁群算法没有设置参数的规范，需要通过大量反复的实验得到一个较好的参数设置范围。本文通过反复实验之后，得到了让实验结果呈现最好效果的参数，参数设置如下：种群规模(蚂蚁数量)为100；蚂蚁载重上限(容量)为200；迭代次数为1 000；α=1；β=2；pbest=0.05。

4.2 算法设计

算法的具体流程如下：

(1)对信息素、客户以及车辆信息等相关参数进行初始化，设车辆数量为m，且共有n个城市，候选客户数组为allowk[n]。将蚁群算法应用在VRPTW时，算法中的蚁群相当于车辆集合。

在互联网时代条件下，物联网技术的应用为农业产生带来了极大的便利，同时也促进着农业生产技术的发展。智慧农业作为一种新型农业形态，其融合了多项现代信息技术，有效解决了农业生产中遇到的问题，是未来农业发展的必然趋势。要想促进农业的高效、可持续发展，就必须加大物联网技术在农业生产中的应用，不断创新农业生产模式，以提高生产效率。

(3)判断车辆载重是否超过车辆最大容量C或服务时间超过客户点接受服务时间范围[ai,bi]，若判断为真，则让其返回配送中心，记录下本次途经的路径，再重新创建一条从配送中心出发的新路径，更新当前位置信息；反之，车辆k将准备移动到客户点j并更新局部信息素。

(4)接着根据allowk[k]中所剩的个数判断是否遍历完所有城市，若车辆k已完成全部走访任务，则车辆k回到配送中心，k=k+1；反之，车辆k继续计算状态转移寻找下一客户点，即重复步骤(2)。

(5)判断当前k是否等于车辆数量上限m，若k=m，则结束本次迭代，得到本次迭代最优解，使用改进的信息素全局更新公式进行更新；反之，开始第k辆车的走访任务。

(6)本次判断迭代次数是否大于最大迭代次数，若成立，则结束本次迭代，输出最优解X；反之，则迭代次数增加一次，开始新一轮迭代。

改进算法流程图如图4。

4.3 实验过程

4.3.1 实例1

数据集选用Solomon Benchmark，该数据集包括6类算例：C1、C2、R1、R2、RC1、RC2，其中C1、R1、RC1的算例的时间窗口比较小，设定的车辆负载较小；C2、R2、RC2则相反，其中的算例时间窗口较大，车辆负载也较大。本次实验将改进的算法应用在Solomon Benchmark的算例C101中不同数量的客户点中，分别为：25，50，100。

输入实例如表1所示(选取前10个客户点作为展示)，序号0为配送中心。

表1中算例C101给出的信息有：使用横纵坐标来表示客户点的位置信息、货物量ci、时间窗起始时间ai、时间窗结束时间bi，以及服务时间si。

表1 Solomon Benchmark problems中算例C101前10个客户点信息

Solomon Benchmark 的网站给出了各个算例历来使用启发式算法求解得到的最优路径，将其与本次改进后得到的最优解对比，如表2。

从表2中可以看到，改进后的算法结果虽然与精确解有一定的差值，但是官网同时给出了C101.100启发式求解方法的最优解为828.94，即与表2中改进后的最优解是相同的，由此可知本次改进后的结果有着较为良好的效果。

表2 历来启发式最优路径和本次改进最优解对比

通过实验，当客户点数量为25时，改进蚁群算法算法得到的最短路径X=191.81对应的路线如表3所示。

表3 客户点数量为25的最优路径

当客户点数量为50时，改进蚁群算法算法得到的最短路径X=363.24对应的路线如表4所示。

表4 客户点数量为50的最优路径

当客户点数量为100时，改进蚁群算法得到的最短路径X=828.94对应的最优径路如表5所示。

表5 客户点数量为100的最优路径

4.3.2 实例2

本次实验将基本蚁群算法和改进蚁群算法进行对比，选取了C1型、R1型和RC1型的实例，每种类型选取4个算例，分别为：C101、C102、C103、C104、R101、R102、R103、R104、RC101、RC102、RC103、RC104，共12个实例。每个算例测试10次，将得到的最优路径长度取平均值进行对比，得到结果如表6所示。

表6 最优路径长度均值对比

由表6的最长路径长度均值对比可知，基本蚁群算法通过改进后解的质量得到了显著提升。接下来对两个算法得到的最短路径长度平均值进行比较，如图5所示。

从图5更直观地看到了改进蚁群算法得到的最优路径明显比基本蚁群算法得到的最优路径更好。本次研究选取了改进蚁群算法和基本蚁群算法在c101算例上得到的最优路径解，根据算例中的横纵坐标画出其最优解的路径图，如图6和图7所示。

从图6和图7中能够看到路径的选择方式，基本蚁群算法得到的路径中存在一些交叉路径，使得到的结果路径更长，路径质量降低，相较之下，改进蚁群算法的路径更为简洁。

本次实验将两个算法的收敛情况进行了对比，如图8所示。

本次实验最大迭代次数设置为 1 000，图8显示了在这1 000次迭代中两个算法收敛的情况。蚁群算法存在着容易过早收敛，陷入局部最优的问题，这个现象可以从图8中看到。在改进蚁群算法还在搜索最优路径解时，基本蚁群算法已经早早地停滞在当前搜索结果上，没有再继续进行搜索；而改进蚁群算法能够不断地进行搜索，直到找到最优路径解，这说明改进算法扩大了蚁群算法的搜索范围，增强了路径的搜索能力，达到了改进目的。

5 结束语

VRPTW是经典NP难问题，随着问题规模的不断增大，启发式算法更适用于解决这类问题。蚁群算法则是经典的群智能启发式算法，其最初就是为了解决TSP而提出的，因此蚁群算法对解决路径问题有着天然的适应性。算法本身具有正反馈、适应性强、鲁棒性强等优点，在解决VRP上也具有较为良好的表现，但同时也存在许多缺点。本次改进针对蚁群算法容易陷入局部最优的缺点，从3个方面对算法进行改进，目的是增强算法的路径搜索能力，扩大搜索范围。本文改进内容如下:

(1)改进信息素更新方式，每次迭代只更新最优路径上的信息素值，同时增加一个奖励值奖励，且对信息素值设置了动态区间，为找到最优路径的蚂蚁保证后续搜索的解质量。

(2)改进信息素挥发因子，随着迭代次数的增加动态地调整信息素挥发因子的大小以适应蚁群搜寻路径的情况。

(3)加入2-opt算法、顺序交换策略、顺序插入策略对每次迭代得到的最优解进行优化，调整最优解中每一条回路中任意两条边，重新计算路径长度，若得到更短的路径长度则替代原路径，循环迭代最终得到最优解。

在实验部分，利用Java编程实现了改进方案的全部代码，然后在Solomon Benchmark中的算例上进行测试，最后通过两个部分的实验，证明了改进蚁群算法具有较为优良的效果的结论，并达到了增强路径搜索能力，防止蚁群算法陷入局部最优的目的。蚁群算法本身还存在参数较多且难以设定的问题，在未来的研究方向中可以更多的考虑对参数的优化，同时，可以尝试在路径优化方向上找到更高效的策略，从而提高最优解的质量。