论文拾萃 |贪心算法与变邻域禁忌搜索算法解决同时取货送货的带时间窗两级车辆路线规划问题（附Java代码）

Part1关于论文

论文第一作者：周航，华中科技大学管理学院本科三年级学生（2019级），具有近2年的启发式算法设计、编程经验。

2020年暑假，工作开始。 2020年9月，确定研究课题。 2020年12月，算法和模型的设计和编程工作基本完成。 2021年寒假期间，实验部分和论文初稿的撰写完成。 2021年6月初，经过几个月的修改，最终向SCI期刊《Soft Computing》投稿。 2021年底，论文被成功接收。

论文的算法设计与秦虎教授（第二作者）、李纪柳博士（第四作者）进行了多次探讨，文章撰写得到了秦虎教授（第二作者）和张子臻教授（第三、通讯作者）的仔细修改。

Part2引言

近年来，物流业的快速发展导致运输过程中的花费越来越大。旨在决定车辆服务的最佳路线的车辆路线规划问题[Vehicle routing problem(VRP)]被广泛研究以适应这种趋势。

两级车辆路线规划问题[Two-echelon vehicle routing problem(2E-VRP)]是这个经典问题的著名变体，如图：

在这个问题中，车辆被分为两级：一级车辆连接唯一的中心仓库与中转站，其容量往往较大；二级车辆连接中转站和顾客，其容量往往较小。货物先通过一级车辆运送到各个中转站，再从中转站由二级车辆运到顾客。

然而，真实情况往往更为复杂：想要外卖或生鲜食物尽量新鲜的顾客需要在特定时段内收到货物；顾客在收取货物的同时，也可能有像退货这样需要快递员取货的需求；对于一些医疗用品，在顾客用后也需要立即回收，防止污染或被非法销售。

因此，我们提出同时取货送货的带时间窗两级车辆路线规划问题[Two-echelon vehicle routing problem with time windows and simultaneous pickup and delivery(2E-VRPTWSPD)]。其中所说的时间窗，就是每个顾客特定的接受服务时间段。

除了以上两个条件，我们假设：对每一个顾客而言，取货量小于送货量；在一级车辆送货到中转站时，卸货需要时间且与货物量成正比。这两个假设都有较强的合理性，且后者是尤为重要的改进，很少在其它文章中出现。

下面给出问题的数学模型：

给定有向图\ce{G = (V, A)} ，其中顶点集\ce{V = V_0\cup V_S\cup V_C} 包含了中心仓库(Central Depot)（只有一个）、中转站(Satellite)和顾客(Customer)。

顶点间弧的集合为\ce{A} 包含两个集合\ce{A_1} 和\ce{A_2} ，其中\ce{A_1} 和\ce{A_2} 分别为一级和二级路线，即\ce{A_1 = \{(i , j) | i , j\in V_0\cup V_S\}} ，.对于每一条弧\ce{(i , j)} 都有对应的花费\ce{c_{ij}} .对于每个顾客\ce{i\in V_C} 均有送货需求\ce{d_i} 和取货需求\ce{p_i} ，根据之前的假设，恒有\ce{d_i\gt p_i}.相应地，在每个中转站的服务顾客确定后，其总送货需求量为和取货需求量也能相应地计算出。对每个中转站\ce{s\in V_S} ，其分配的顾客集合为\ce{S} ，则总送货需求量为\ce{\sum_{i\in V_C}d_i} ，总取货需求量为\ce{\sum_{i\in V_C}p_i} .

同时，对于每个顾客\ce{i\in V_C}均有时间窗\ce{[e_i , l_i]} ，顾客仅在这个时间段内可以接受服务，服务时间记为\ce{s_i} 。车辆允许在各个地点等待且没有花费。时间窗仅在顾客处存在。根据前面的另一个假设，在一级车辆送货到中转站时，卸货时间与货物量成正比，系数为\ce{\tau} 。对于一级和二级车辆，其容量分别为\ce{Q_1} 和\ce{Q_2}，其集合分别为\ce{K_1} 和\ce{K_2} .

整个过程可以分为三步：

1. 一级车辆从中心仓库出发将货物运送到各个中转站；
2. 二级车辆从各中转站出发将货物送到各个顾客，同时立即从顾客处取货，再将取到的货物送到各个中转站；
3. 一级车辆将各个中转站的货物送回中心仓库；

值得注意的是，不允许货物直接从中心仓库运送到顾客。

我们的目的是将顾客分配到各个中转站后，选择花费最少的路线。

由于“在一级车辆送货到中转站时，卸货需要时间且与货物量成正比”这一假设，不同于两级车辆路线规划问题(2E-VRP)中的规定，一级车辆可以多次到达同一个中转站以减少可能的花费或避免与时间窗形成冲突。

以下面的两个情况为例： 图中\ce{a_i} 表示到达中转站或顾客的时间，例子中所有顾客均无取货需求

如图，注意到\ce{C_3} 和\ce{C_4} 的时间窗较为靠后，一级车辆若先将这两个顾客的货物于\ce{S_1}卸下，会导致\ce{C_2} 的时间窗无法满足。而先将\ce{C_2} 货物于\ce{S_2} 卸下再回到\ce{S_1} 卸下\ce{C_3} 和\ce{C_4} 的货物就可以解决这个问题。

Part3问题解决办法

1整体流程

1. 贪心算法生成初始解 1.1 给各个中转站分配顾客 1.2 根据各个中转站分配的顾客构建二层路径，同时判断是否存在可行解 1.3 根据二层路径构建伪中转站 1.4 根据中转站构建一层送货路径和一层取货路径
2. 变邻域禁忌搜索算法优化

2贪心算法生成初始解

伪代码：

2.1 分配顾客

若顾客\ce{i} 到中转站\ce{s} 的距离加上中转站\ce{s} 到中心仓库的距离最小，则将顾客\ce{i} 分配到中转站\ce{s} .

2.2 构建二层路线

对每一个分配有顾客的中转站:

1. 创建一条新路径；
2. 选取时间窗末尾最早的顾客，进行检查。若可行，则作为该路径的第一个顾客；若不可行，则无可行解；
3. 选取花费（或距离）增加量最小的顾客，进行检查；若可行，插入到路径中；若不可行，则跳过该顾客。直至遍历完成；
4. 若有剩下的顾客，则再创建一条新路径，回到第二步；若没有，则构建完成。

这里的检查指的是：检查二级车辆的容量是否能够满足顾客的发货需求，以及是否会与时间窗冲突。

2.3 构建伪中转站

伪中转站(Dummy Satellite)是该算法的一个重要创新。

如图，在左图中，中转站\ce{s} 下有两条路径，假设一级车辆先卸货给含3个顾客的路径，再卸货给含2个顾客的路径，由于卸货时间的存在，可以将中转站\ce{S_1} 看作两个距离为0的伪中转站\ce{DS_{1-1}} 和\ce{DS_{1-2}}.为了表示方便，相似的，我们将中转站\ce{S_2} 和中转站\ce{S_3} 表示为\ce{DS_{2-1}}和\ce{DS_{3-1}} .这样一来，以第一部分提到的第二个情况为例，一级车辆的路径为

伪中转站随着二级路线的确定而确定，伪中转站的最迟到达时间 （伪时间窗） 也可以随之确定。

对于属于伪中转站\ce{j} 的第\ce{i} 个顾客，我们引入一个变量\ce{TS{_i^j}} 来表示该顾客可允许一级车辆延迟到达中转站的时间量。其公式为： 其中\ce{a_k} 表示到达顾客\ce{k} 的时间，\ce{e_k} 和\ce{l_k} 分别表示顾客\ce{k} 的时间窗始末。 这个公式可以理解为：二级车辆等待所有第\ce{i} 个顾客前面的顾客时间窗开始的时间之和（若需要等待），加上二级车辆到达第\ce{i} 个顾客的时间提前于第\ce{i} 个顾客时间窗末的时间。如下图，

接着我们引入变量\ce{TS{^j}} 来表示伪中转站\ce{j} 中\ce{TS{_i^j}} 的最小值，其意义为该伪中转站\ce{j} 可允许一级车辆延迟到达该伪中转站的时间量 。其公式为：

由此我们可以算出可到达伪中转站\ce{j} 的最晚时间\ce{l_j} 。其公式为：\ce{l_j = a{_1^j} + TS{^j} - c_{j{j^*}} - s^j} 其中\ce{a{_1^j}} 表示到达第一个顾客的时间 ，\ce{c_{j{j^*}}} 表示从伪中转站到其第一个顾客的时间花费，\ce{s^j} 表示在伪中转站\ce{j} 的卸货时间。 这个公式可以理解为：一级车辆从中心仓库直接出发，到达该伪中转站的时间(即\ce{a{_1^j} - c_{j{j^*}} - s^j} )加上可以推迟的时间量(即\ce{TS{^j}} )。 下图是一个供参考的例子（假设二级路径中仅有一个顾客）：

如下图，特别地，当时间窗冲突无法解决时，\ce{l_j = -1}

这一概念的提出使得路线结构变得更加清楚，优化操作对象更为明确；同时在一定程度上加快了计算过程（详见3.2）。

2.4 构建一层送货、取货路径

在构建伪中转站和对应的时间窗后，一层送货路径问题就变为了带结束时间限制的“车辆路径规划问题”(VRP),一层取货路径问题就变为了典型的“带容量限制的车辆路径规划问题”[Capacitated Vehicle Routing Problem(CVRP)]。用与2.2相类似的办法即可解决。

3变邻域禁忌搜索算法

伪代码：

3.1 适应度函数

按照问题的条件，如果一个解中存在时间窗或容量冲突，则表示这个解是不可行的。然而，我们在一小步一小步迈向最优解的过程中大概率会经过不可行的解。所以，当我们遇到不可行解时，需要判断这个解是不是通向较优解的一块垫脚石。因此，我们引入一个可以将搜索控制在一定的范围内，避免我们误入歧途的适应度函数。它可以同时计算路径花费及其超出限制（包括时间窗和容量）的程度，通过这样的方式综合地表示解的优化程度。其公式为：

\ce{f(s) = c(s) + \alpha t(s) + \beta d(s)}，其中，,简单来说，\ce{t(s)} 是对所有超出顾客时间窗的时间之和，\ce{d(s)} 是所有车辆超载重量之和。\ce{\alpha} 和\ce{\beta} 是在预先经过实验得出的区间\ce{[LB,RB]} 动态调整的权重参数。开始时\ce{\alpha} 和\ce{\beta} 在区间内随机确定，当一个解中出现时间窗或容量冲突时，对应的参数就会乘上一个大于1的数\ce{\delta} ；反之，若一个解是可行的，对应的参数就会除以\ce{\delta} 。需要注意的是，调整后的参数仍需要处于区间\ce{[LB,RB]} 内。

3.2 搜索方式

算法运用的是经典的两种算子：单一移动、交换。对应到二级路径的顾客、一层送货路径和一层取货路径的伪中转站三种节点，可以得到6个算子，如图：

由于一层送货路径和一层取货路径主要部分均由中心仓库和伪中转站构成，故都可以用图二表示

选择这六种算子的方式类似掷两个骰子：随机从6个算子中选取两个不同的算子，分别搜索各自的最佳操作方式（位置），评价时采用刚才引入的适应度函数。选取操作后函数值较小的操作（若函数值相同则随机选择）更新当前解。若更新后的解仍可行且函数值比当前最优解更小，则将其作为当前最优解。

操作后，若干对顶点（伪中转站或顾客）写入禁忌表，即在接下来的若干次（通过预试验决定）迭代中，若进行某一操作，写入禁忌表的顶点对不能包含这些顶点对。写入禁忌表的顶点对参见上文图中的所有红线连接的顶点对。

需要注意的是，一个操作往往会造成很大的变化，如果全部重新计算，会产生很大的计算量，非常耗时。因此，我们需要用到2.3引入的伪时间窗。比较操作后一级车辆到达某个二级路径没有改变的伪中转站的时间与该伪中转站的伪时间窗，若不超过，则说明该伪中转站下所有顾客的时间窗都不会有冲突，可以省略该伪中转站下路线的时间计算。这一方法平均可以节约19%的计算时间，并且最高可达45.72%。

当超过若干次迭代没有优化，或迭代超过若干次后，优化结束。

以上即为全部内容，你看明白了吗？

参考文献：

原论文：Zhou, H., Qin, H., Zhang, Z.Z.*, Li, J.L., 2021. Two-echelon vehicle routing problem with time windows and simultaneous pickup and delivery. Accepted by Soft Computing. https://doi.org/10.21203/rs.3.rs-604710/v1

欲下载相关代码，请移步留言区

-The End-

文案&排版：吕其乐（华中科技大学管理学院本科一年级）

指导老师：秦虎老师 （华中科技大学管理学院）

如对文中内容有疑问，欢迎交流。PS：部分资料来自网络。