基于改进蚁群算法的多时间窗车辆路径问题

朱 杰，张培斯，张询影，余微微

(北京物资学院 信息学院，北京 101149)

0 引 言

多时间窗车辆路径问题是车辆路径问题[1]的扩展，它源于现实生活中人们对服务时间的需求。例如某甲要为周边多个用户提供配送服务，假设用户乙在[8:00，10:00]和[12:00，13:00]时间段有空闲时间接受服务，用户丙在[12:00，12:30]和[16:30，17:20]时间段内有空闲时间接受服务，用户丁等也具有多个互不重叠的时间窗；这就需要甲安排合理的路线，在满足用户要求的情况下实现成本最低、路程最短或用车最少等目标。

从时间窗的数量角度划分，带时间窗的车辆路径问题可分为单时间窗问题和多时间窗问题；目前关于带时间窗的车辆路径问题研究主要集中在单时间窗[2-4]类型，而多时间窗的车辆路径问题研究文献相对较少。Belhaiza等[5]提出了变邻域禁忌搜索算法求解最小等待和延误时间的多时间窗车辆路径问题；Beheshti等[6]设计了协同进化多目标量子遗传算法求解带有优先级顺序的多时间窗车辆路径问题；Favaretto等[7]提出了允许多次访问的多时间窗车辆路径问题；马华伟等[8]设计了一种求解允许分割配送的多时间窗车辆路径问题的改进蚁群算法；黄秋爱等[9]通过引入最优个体保留机制改进传统的遗传算法，并设计数学模型进行求解，验证了算法及其模型的有效性；朱玲玲等[10]提出一种协同禁忌优化算法，通过扫描算法求得初始解，再设计自适应修改禁忌长度的算法和多个子禁忌算法进行协同优化进行求解；李珍萍等[11]运用智能水滴算法对多时间窗车辆路径问题进行了有效探索；闫芳等[12]应用粒子群算法，以总成本最小和满意度最大为目标，求解了多模糊时间窗车辆路径问题。

蚁群算法[13]是意大利学者Dorigo在20世纪90年代提出的一种仿生算法，具有正反馈、分布式计算以及贪婪的启发式搜索等特点，同时具有较好的耦合性，易于和其他算法结合，这些特点为更好地解决组合优化问题提供了可能[14]。文中以总成本最小为目标，建立多时间窗车辆路径问题的数学模型，改进蚁群算法对问题进行求解，并通过算例验证模型和算法有效性。

1 数学模型

1.1 问题描述

1.2 模型假设

假设一：每个用户的需求量不超过车辆最大载重量；假设二：用户的时间窗为硬时间窗要求；假设三：用户的各个时间窗互不重叠；假设四：单车场多需求点的配送模式；假设五：各个配送车装载量相同；假设六：用户的需求不可分割。

1.3 数学模型

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

Rik+Tij·xijk+Si·xijk-M(1-xijk)≤Rjk

(11)

目标函数1表示总成本最小，其中第一项表示动用车辆的固定成本，第二项表示车辆运行成本；式2、3表示一个用户能且仅能被访问一次；式4表示所有车辆必须从配送中心出发，最终返回配送中心；式5表示完成所有任务共动用的车辆数；式6表示任何一辆车所服务的用户的总需求量不超过车辆最大装载量；式7表示如果车辆k到达j点，则必为j用户提供服务；式8表示如果车辆k为i用户提供服务，则服务完必从i点离开；式9表示任何车辆在其配送路线上前后两个相继节点的时刻之间的关系；式10、11为时间窗约束。

2 算法设计

2.1 基本蚁群算法

蚂蚁在协同觅食的过程中，会在经过的路径上留下信息素，每一只蚂蚁经过的路径都可以看作是一个可行解，各个蚂蚁之间通过信息素进行联系，蚂蚁觅食时会选择信息素较高的路径，信息素越高，被选的概率就越大，随着时间的推移，较优路径上的信息素会越来越多，而其他路径上的信息素随着蒸发逐渐降低，算法最终收敛到最优解或近似最优解[3]。但是该算法也有搜索时间长和收敛速度慢、容易陷入局部最优解等缺点，对此，文中改进转移概率和信息素更新公式以跳出局部最优陷阱，结合邻域搜索策略提高算法的寻优能力，加快算法收敛速度。

2.2 改进算法描述

2.2.1 伪随机转移概率公式

(12)

其中，τij为从i到j的信息素浓度；α为信息素浓度重要因子；ηij为启发函数，ηij=1/Dij，表示蚂蚁从用户点i到j的期望程度；β为启发函数重要因子；ωij为节约值，ωij=Di0+D0j-Dij；ε为节约值重要因子；allowk表示车辆在满足约束条件下可访问点的集合。

2.2.2 邻域搜索策略

蚁群算法具有贪婪的启发式搜索特性，这就造成算法在构造可行解的时候，只关心解的成分，而不关心解是怎么组成的，它只会随机组合这些成分，而最优解的组合方式一般是唯一的，随机组合得到最优解的可能性很低。因此借助邻域搜索策略增加算法搜索广度，提高解的质量。邻域搜索是指对产生的可行路径进行位置扰动并重新组合，假设当前路径中的节点个数为N，则其邻域变换的规模大小为N(N-1)/2，通过对路径进行节点位置调换，如果调换两点后的路径满足约束条件，并且解的质量变优，则接受优化后的路径，否则保持原路径不变。

2.2.3 信息素更新策略

当全部蚂蚁完成对所有节点的访问后，对当前最优路径进行信息素更新，更新公式为：

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

(13)

为了防止算法容易停滞和陷入局部最优解，结合模拟退火法[15]的特点，以一定概率接受恶化解，帮助算法跳出局部最优的陷阱。fk+1为当前蚂蚁完成本次循环后得到的局部最优解，Δf=fk+1-fk，如果Δf<0，则接受新解，否则进行判断，p=exp(-Δf/T)，如果p大于(0,1)间的随机数，则接受新的恶化解作为最优解，否则不接受，最优解仍为fk。T是当前温度，完成一次循环后进行降温处理，降温速率为r，T(t+1)=T(t)·r。

2.3 算法步骤

(1)输入参数，初始化信息素矩阵，设置最大迭代次数N和蚂蚁个数K；

(2)将蚂蚁放置起点，设当前出发点为i，建立禁忌表，即蚂蚁已访问节点和未访问节点集合，同时建立allowk表，即可去点的集合；

(3)从当前出发点i开始，根据约束条件从未访问节点集合中搜索出下个可去点并将其放入allowk，直至所有节点搜索完毕，如果allowk为空集，则车辆返回配送中心，更新车辆信息，再令i=0，继续执行本步骤；

(4)根据转移概率公式，按照轮盘赌的方法从allowk表中选择下个访问节点j，同时更新禁忌表以及车辆载重信息；如果全部节点访问完毕，转至步骤5，否则令i=j，转步骤4；

(5)如果所有节点均已访问完毕，则k=k+1，转至步骤2；如果所有蚂蚁遍历完毕，找出当前最优解，按照邻域搜索策略进行可行解的优化，然后根据更新公式更新信息素；n=n+1，如果n

(6)输出结果，退出程序。

3 仿真实验

多时间窗车辆路径问题尚无标准的测试数据，该算例数据取自文献[11]，不在此一一列举。改进蚁群算法的参数设置为：种群规模100，迭代次数200，初始信息素为1，α=1，β=2，ε=1，ρ=0.1，T=1 000，r=0.9。改进蚁群算法求得的最优解为2 156.8，共需要4辆车完成配送任务,路线如图1、2和表1所示。

图1 路线图1

图2 路线图2

车辆路线装载率/%10→1→4→3→6→2→5→06020→7→9→10→8→11→072.53a0→20→19→15→18→0953b0→18→15→19→20→09540→17→16→13→14→12→095

车辆一从配送中心出发，按路线4-3-6-2-5给用户提供配送服务，完成后返回配送中心；

车辆二从配送中心出发，按路线7-9-10-8-11给用户提供配送服务，完成后返回配送中心；

车辆三有两种方案选择，车辆从配送中心出发，可以按路线20-19-15-18给用户提供配送服务，或按路线18-15-19-20给用户提供配送服务，完成后返回配送中心；其成本和距离一样，决策者可根据实际情况自行选择行车路线安排配送；

车辆四从配送中心出发，按路线17-16-13-14-12给用户提供配送服务，完成后返回配送中心。

与文献[11]的结果相比较，智能水滴算法求得的结果为2 168.9，改进后的蚁群算法求得的结果为2 156.8，最快一次仅七代就搜索到最优解，而且结果变优，同时线路选择增加；相比智能水滴算法，改进蚁群算法可以更好地求得最优解。

同时，为进一步验证改进蚁群算法在求解多时间窗车辆路径问题上的有效性，又分别用标准蚁群算法、模拟退火算法和禁忌搜索算法进行20次测试对比，结果如表2所示。

表2 算法对比

从表2中可以看出，在20次实验中，改进蚁群算法求得的最优解为2 156.8，平均每次求得的最优解为2 161，标准差为6.69，三项指标均优于其他三种算法。标准蚁群算、模拟退火算法和禁忌搜索算法均停留在某个局部最优解上，说明改进蚁群算法在跳出局部最优解方面具有良好的性能，而且算法求解的标准差较小，结果相对稳定，而未改进的标准蚁群算法、模拟退火算法和禁忌搜索算法在求解过程中的稳定性较差。

从图3可以看出，模拟退火算法和禁忌搜索算法在迭代过程中变化幅度大，稳定性差，而且求解质量不高，而改进蚁群算法在求解问题时速度较快，稳定性好，求解质量高于其他三种算法。

图3 算法迭代对比图

4 结束语

车辆路径问题属于NP难题，构造高质量的启发式算法是很多学者的研究方向。针对多时间窗车辆路径问题建立了一般数学模型，改进蚁群算法进行求解，和其他算法求得的结果进行比对分析。改进后的蚁群算法在求解多时间窗车辆路径问题上有着较好的性能，是求解多时间窗车辆路径问题的较好途径。