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

吴延峰，韩鹏飞，田 凯

（河南科技大学 车辆与交通工程学院，河南 洛阳 471003）

0 引言

带有时间窗的车辆路径问题(Vehicle Routing Problem with Time Windows,VRPTW）作为传统车辆路径问题（Vehicle Routing Problem,VRP）的一个扩展，除了考虑车辆容量约束以外，还要考虑车辆发车时间以及客户服务顺序，并要在客户指定的时间窗内将货物送达。并行时间窗下的车辆路径问题（Vehicle Routing Problem under Parallel Time Windows，VRPPTW）是VRPTW问题的一种情况，该问题要求在相同的时间窗内，同时满足多个客户的需求，这类VRPTW 问题在实际物流配送中是广泛存在的。例如，对于生鲜品类的配送，就存在着多个客户要求将货物在同一时间送达的情况。

目前，求解VRPTW的方法可分为启发式算法和精确算法。VRPTW 已被证明是一个强NP 难题，在合理时间内只能求出近似解。因此，国内外学者对其求解主要集中在启发式算法上，并取得了较好的效果。蚁群算法是由意大利学者Dorigo 基于蚂蚁的行为特性所提出的启发式全局优化算法。近年来，蚁群算法凭借着其极强的鲁棒性及隐含的并行性，已然成为众多启发式算法中的佼佼者。2006 年，陈幼林，等通过改进蚁群算法，将VRPTW转化为TSP进行求解，用实验计算验证了方案的有效性。刘志硕，等提出了一种基于可行解两阶段构造策略的自适应混合蚁群算法；随后，Ding，等通过在信息素的计算中引入灾难因子，提出了一种求解VRPTW 的混合蚁群优化算法，避免了传统蚁群算法在运行时陷入局部最优解；韩越通过对信息素更新方法与局部搜索策略进行改进，提出了一种改进混合蚁群算法的新型启发式算法求解VRPTW问题，避免了蚁群算法易陷入局部最优解的不足及易于出现早熟和停滞的现象。孙小军，等通过引入交通拥堵因子改进传统蚁群算法，求解了带时间窗的动态车辆路径问题，并用数值实例验证了改进蚁群算法的可行性和优越性。

综上，既有文献对VRPTW问题已经进行了大量深入的研究，但对于贴合实际下的VRPPTW 研究较少，而该类VRPTW问题在实际生活中是普遍存在的，求解也是复杂的。因此，本文针对VRPPTW的求解提出一种改进蚁群算法，通过采用多个蚂蚁子群并行共享访问列表的方式，克服了传统蚁群算法在求解并行时间窗约束下的集货路径问题的局限性，并以零担货物的集货路径规划为实例，验证了改进蚁群算法具有较好的优化性能和应用效果。

1 VRPPTW问题描述和数学模型

1.1 问题描述

带有并行时间窗约束的车辆路径问题（Vehicle Routing Problem under Parallel Time Windows，VRPPTW）是VRPTW问题的一种情况。在该问题中，每个客户都有一个与之对应的预约时间，并按从早到晚对预约时间进行排列，且排列结果中最早的预约时间相同个数大于1个。VRPPTW的描述为：（1）K辆型号相同的作业车辆从一个物流配送中心出发，完成配送任务后必须返回配送中心，且每辆车容量限制应满足其载重量约束；（2）N 个客户都有相应的时间窗约束，且有若干个客户初始时间窗相同；（3）目标为以最小车辆行驶的总距离满足所有的客户需求。

1.2 数学模型

G=(V,A)表示无向连通图，V 表示图中所有节点集合，包括接驳点（配送中心）和客户点，A 表示图中所有弧的集合，由于此问题中起点和终点相同，因此接驳点用0表示。N=V，表示客户点集合，K 表示所有车辆的集合，c表示车辆从i 点到j 点的路程。x为0-1变量，当运输车辆k 经过弧(i,j)时，x取值为1，反之为0。δ(i)表示车辆从i 点离开后前往下一点j 的集合，j ∈δ(i)；δ(j)表示所有到达点j 的集合，出发点i ∈δ(j)。d表示i 点的货物重量，V表示车辆k 的最大载重量。w表示车辆k 到达顾客点i 的时间；s表示在i 点的服务时间；t表示车辆从i 点到j 点的行驶时间；w表示车辆从i 点出发到达j 点的时间。M 是一个足够大的数。VRPPTW问题的数学模型如下：

上述模型中，式（1）为目标函数，表示总运输车辆在规定的约束下服务完全部客户所用的距离和最小；式（2）表示每个顾客只能被一辆车服务一次；式（3）表示全部车辆必须从起始点出发；式（4）表示第k 辆车服务完点j后必须离开；式（5）表示每辆车最终都必须要回到起点；式（6）表示每辆车的载重量要小于其最大载重量；式（7）表示到达顾客点的时间表达式；式（8）表示服务车辆到达每个顾客的时间窗约束，E,L分别表示最早和最迟开始服务时间，本文中最早和最迟开始服务时间一致，车辆必须按时到达，且有不少于2个客户的初始时间窗相等。

2 改进蚁群算法介绍

2.1 基本思想

传统的蚁群算法是由一只蚂蚁遍历完所有节点再对方案进行分割，若订单数据中最早的时间窗出现并行时，传统蚁群算法便显现出局限性。如某公司三个客户订单的预约提货时间相同，当蚂蚁选择第一站时，只会从这三个客户中选择一个客户进行服务，从而导致另外两个客户服务超时，算法失效。为此，当多个初始时间窗相同时，就产生了并行需求，需要利用多只蚂蚁同时并行从起始点出发进行遍历。针对VRPPTW的特点和传统蚁群算法的不足，改进蚁群算法首先对硬时间窗进行排序，接着通过并行时间窗的个数来确定起始蚂蚁（车辆）数。然后依照订单的时间顺序，计算每只蚂蚁前往下一站的概率。依据轮盘赌法选择下一站，当蚂蚁的容量超过规定容量时，则必须返回出发点。若所有蚂蚁在执行当前最紧迫的订单时都发生超时，则初始化一只蚂蚁，由该蚂蚁执行此订单。改进后蚁群算法程序框图如图1所示。

2.2 改进蚁群算法模型的优点

改进后的蚁群模型通过增加每次迭代的蚁群数量，解决了当订单数据的初始时间出现并行时的情况，如图2所示。由于只对每次迭代蚁群中的最优蚁群所经过的路径进行信息素更新，有利于缩短收敛时间，增加结果的准确性。并且在选择下一站的过程中，采取轮盘赌法依概率选择下一站，避免了陷入局部最优解。

3 案例分析

3.1 案例说明

3.1.1 案例描述。某配送企业现有若干提货车辆在某市内承担装载零担货物，目前已开设多个接驳网点（配送中心），综合考虑车辆的行驶线路、行驶里程、车辆的装载能力等，要求在完成全部提货任务的前提下，给出最优的汇合接驳网点的推荐顺序并给出每辆车的最优线路。

采用改进的蚁群算法求解时，依旧采用多次迭代的方法。当最优距离不再变化时，求得在该接驳点下的车辆最优运输方案。其余接驳点同理，经过多次求解，最终给出各接驳点的总距离排序，选取距离最小的接驳点作为此次集货路径的接驳点。

在该案例中，做出如下假设：

（1）假设货车上午7:00开始工作；

图1 改进后蚁群算法程序框图

图2 传统蚁群算法与改进蚁群算法对比图

（2）假设货车提前20min到达；

（3）假设每个订单的服务时间为20min；

（4）假设货车在行驶过程中平均速度为60km/h；

（5）仅考虑使用同一车型。

已知该企业各个订单的经纬度坐标、需求量以及对应的服务时间等信息，具体见表1。已知该企业接驳网点位置，见表2。

表1 按时间顺序排列的订单信息（部分）

表2 接驳网点位置

表3 订单距离矩阵（部分）

表4 接驳点到订单的距离信息（部分）

3.1.2 数据处理。由于表1、表2 中给的是经纬度信息，考虑到两点的直线距离并不等于两地的路程，所以直接利用欧氏距离对两点进行求解误差较大。因此，基于Python编写数据处理程序，借助百度地图API批量获取两地的实地距离，见表3、表4。

3.1.3 初始蚁群（车辆）数目的确定。将表1按照预约提货时间进行排序，结果见表5。从表5可以看出，前3 个订单（ID1、ID9、ID31）的预约时间均为9:00，订单ID20与ID26的预约提货时间为9:20，而每个订单的服务时间为20min，因此至少需要5 只蚂蚁（车辆）同时从起点出发，五只蚂蚁选择的第一站分别对应ID：1、9、31、20、26。

表5 按时间顺序排列的订单列表

3.2 改进前运行结果分析

从图3可以看出，传统的蚁群算法在对该问题进行求解时，发生多处超时，其原因在于最早3个订单的提货时间相同，导致蚂蚁在选择第一站时，只能从重复的三个站点中选择最近的进行访问，没有其他蚂蚁服务剩余订单，从而导致超时。

图3 传统蚁群代码运行结果

3.3 改进后运行结果分析

本文以接驳点A为例，运用改进的蚁群算法，经过100次迭代，最终得到在该接驳点下的车辆最短行驶距离，如图4所示。图4记录了每次迭代过程中总行驶距离的变化情况，可以看出，迭代进行到75次左右时达到最优解。经程序验算，车辆在执行任务的过程中，未违反重量、时间约束。共发出7辆车，其各自行驶路径如图5所示，所有车辆行驶总距离为845 109.00m。

3.4 最优接驳点的选取

本文采用Matlab2016a 作为编程工具，按照文中程序框图编程可得5个接驳点对应的最优距离，见表6。

图4 车辆行驶总距离（m）次迭代过程

图5 改进的蚁群算法程序运行结果

表6 5个接驳点最优距离

由表6可以看出，接驳点D对应所有车辆的总距离之和最小，距离为619.862km，因此选择接驳点D为最优的接驳点。从图6中也可以直观地看出接驳点D更接近需求点分布中心，说明计算结果合理。因此，本案例中，依据车辆行驶总距离最小原则，得到5个接驳点优先顺序为：D＞E＞B＞C＞A。

3.5 车辆的最优运输方案

通过对接驳点D对应的运输方案进行分解，从而得到每辆运输车辆的运输方案，见表7。

表7中，0表示接驳点，数字表示订单序号，可以看出平均每辆车的工作单数为6 单左右，平均行程88.55km。其中，车辆4 行驶距离最长，为114.51km；车辆2行驶距离最短，为52.13km。车辆2和车辆4的

图6 接驳点分布图

表7 接驳点D对应车辆的运输方案

行驶线路分别如图7中实线和虚线所示。

图7 车辆2和车辆4的行驶线路

4 结语

本文针对并行时间窗约束下的车辆路径问题，建立了以路径最短为优化目标的VRPPTW数学模型，并设计了一种改进蚁群算法。该算法在传统蚁群算法的基础上进行了优化改进，通过采用多只蚂蚁并行共享访问列表的方式，避免了目前蚁群算法在求解初始时间窗相同的车辆路径问题的失效。最后，以某公司零担货物的集货路径规划为例，验证了改进蚁群算法的可行性。本文仅考虑了静态的、单目标的车辆路径问题，求解算法也是针对传统蚁群算法的不足进行了优化改进，如何解决动态条件下并行时间窗的多目标车辆路径问题有待进一步研究。