【析】考虑同时取送和时间窗的车辆路径及求解算法

期刊：***puter engineering and applications 计算机工程与应用![c

引言

1. 问题分析

1.1 问题描述

问题描述为：

1. 若干运输车辆从配送中心出发为客户取送货并最终返回配送中心，每位客户仅由一辆车服务一次，车辆在配送过程中任何时刻都不能超载。
2. 车辆到达客户处为客户送货的同时从客户处取走回收的货物，每位顾客具有取货和送货的需求。
3. 配送中心和客户的位置、时间窗、客户取送货需求量、服务时间需求，以及配送各中心和各个客户之间的距离、车辆行驶速度均已知。
4. 允许车辆在客户最早开始服务时间之前到达，不允许车辆在客户最晚开始服务时间之后到达；车辆要在配送中心最早开始时间之后为客户服务，在配送中心最晚截止时间之间返回配送中心。

物流网络可抽象为一连通图：假设各节点之间相互连通；两点之间的距离对称，即$d_{ij}=d_{ji}$;任意3个节点之间的间距满足$d_{ik}+d_{kj}\ge d_{ij}$;忽略道路、天气及交通拥塞等其他因素。

1.2 模型建立

模型如下：

2. 算法设计

2.1 编码解码与种群初始化

假设所研究的配送网络中共有 N 个客户，配送中心最多可使用 m 辆车，则个体的解可以表示为1~ (N + m - 1) 随机排列。

该个体表示服务6个客户，最多使用3辆车的一个解。配送中心表示0；客户集 {1,2,3,4,5,6} ；车辆集 {7,8} 。
具体解码为：

1. 首先找到车辆节点 7、8 的位置；
2. 提取节点 2、5、7；
3. 在个体中删除提取节点，在所提取节点中删除车辆节点并在首尾加上配送中心，生成子路径 0→2→5→0；
4. 重复操作生成子路径 0→3→1→0；
5. 最后提取剩余节点生成子路径0→4→6→0。

编码：(可看做基因代码) 2,5,7,3,1,8,4,6的顺序.其中 7和8是车辆节点，其他6个为客户节点。
解码：根据这个顺序，根据车辆节点的分隔去完成配送任务。
如上所说个体解是1~8(6+3-1=8)的随机排列。那么会有三种情况：

• 仅仅使用一辆车的特殊解:
  • 7,8,1,2,4,5,3,6
  • 1,2,4,5,3,67,8
  • …
• 使用两辆车的解：
  • 1,2,4,5,7,8,3,6
  • 1,2,7,8,4,5,3,6
  • …
• 使用三两车的解如图2所示

还有一个问题：VRPSPDTW是在原来的VRP上扩展了同时取送和时间窗两个约束。那么就会有一个实际的编码解能否成立的问题？

• 客户1:8:00-8:30 客户2:9:00-9:50 客户3:11:00-11:40
• 如果存在一个编码顺序 $3\to 2\to 1$，则实际解码不会成立的。

初始解的质量对算法的求解速度和求解质量影响较大。

初始解的已有的设计

1. ，周蓉等[23]通过大部分初始种群个体随机生成和部分优良个体采用改进节约算法的方式生成初始种群。《装卸一体化车辆路径问题的自适应并行遗传算法》

   以 Ｃ－Ｗ 节 约 法 为 基 础，设 计 ３种基于双重需求 的 启 发 式 种 群 初 始 化 方 法，并 采用大部分个体随 机 生 成、部 分 优 良 个 体 采 用 种 群初始化方法生成的方式得到初始种群。随机产生方法 遵 循 两 条 原 则：第 一，不 允 许 产 生 相 同 个 体；第二，随机产生个 体 与 已 产 生 个 体 的 目 标 值 之 差应不小于某一数值Δ

2. Xia 等[24]采用随机方式生成初始解，并通过设计邻域搜索机制来降低算法对初始解的依赖性。《Improved tabu search algorithm for the open vehicle routing problem with soft time windows andsatisfaction rate》(具有软时间窗和满意率的开放式车辆路径问题的改进禁忌搜索算法)
3. 本文选择随机方式生成初始解，并通过对违反载重量、时间窗的惩罚机制接受不可行解，增大搜索范围以及提高算法跳出局部最优的能力，使算法在迭代寻优中找到更优质的解。这个的意思对 因为载重量、时间窗的不可行解 接受，只是进行惩罚机制，以增大搜索范围？？？

C-W节约法

C-W节约法（Clarke and Wright Saving Method）是一种经典的启发式算法，主要用于解决车辆路径问题（Vehicle Routing Problem, VRP）。这种方法由Clarke和Wright于1964年首次提出，目的是在车辆数不固定的情况下，为需要配送的客户安排最经济的路线。C-W节约法通过合并运输路线来减少总行驶距离，从而节约成本。

C-W节约法的基本步骤如下：

1. 初始化：从配送中心开始，为每个客户创建一条独立的配送路线。此时，每条路线只包含一个客户。
2. 计算节约量：对于每对客户（i, j），计算如果将它们合并到同一条路线中，可以节约的行驶距离。节约量的计算公式通常为：节约量 = d(0,i) + d(0,j)
   -d(i,j)，其中d(0,i)表示从配送中心到客户i的距离，d(0,j)表示从配送中心到客户j的距离，d(i,j)表示从客户i到客户j的距离。
3. 排序：根据计算出的节约量，对所有客户对进行降序排序。
4. 合并路线：从节约量最大的客户对开始，尝试将它们合并到同一条路线中。如果合并后的路线满足所有约束条件（如车辆载重限制、客户时间窗等），则进行合并，并更新相关路线信息。然后，继续考虑下一个节约量最大的客户对。
5. 迭代优化：重复步骤3和4，直到无法再合并任何客户对或达到预设的迭代次数。

C-W节约法的优点在于简单易实现，且能够在较短的时间内得到一个较好的解。然而，它也存在一些局限性，如容易陷入局部最优解，无法保证找到全局最优解。因此，在实际应用中，通常会将C-W节约法与其他优化方法（如遗传算法、模拟退火算法等）相结合，以提高求解质量和效率。
案例说明见：《【路径分割】序列分隔和路径提取的案例》

2.2 计算适应度值

解码出的配送方案并不一定都是可行的， 首先通过式（21）、（22）分别计算当前配送方案违反载重量约束及违反时间窗约束之和，然后通过式（20）对违反载重量和时间窗约束的配送方案进行惩罚，保证算法能找到更优质的解。

$G(x)$ 为当前配送方案的总成本，即目标函数；
$K(x)$ 为车辆使用数目；
$C(x)$ 为车辆总行驶距离；
$L(x)$为各条配送路径违反的载重量约束之和；
$T(x)$为所有客户违反的时间窗约束之和；
$\beta$ 为违反载重量约束的惩罚因子；
$\gamma$ 为违反时间窗约束的惩罚因子；
$l_i$ 为货车到达客户 i 的时间。

2.3 聚类及替换

（1）计算每个个体的适应度函数值，采用 k -means聚类方法把 n 个 个体分成 m 个类，并将各类个体进行排序，其中最佳个体作为聚类中心。
（2）随机产生一个 [0,1] 之间的数 r1 ，若 r1 小于给定的参数 p0（替换概率），则进入（3），否则进入生成新个体操作。
（3）在 m 个聚类中随机选择一个聚类的聚类中心，生成一新个体，然后用新个体替换选中的聚类中心。

猜想：在原有的遗传算法上添加一个聚类的目的是什么呢？
根据生活经验来看，车辆对于聚在一堆的站点跑的路程可能是短的。为了缩短优化的过程而设立的。这样的操作对于 团状聚类会有好处的， 而对于环状聚类图是不利的。 当然，聚类的结果主要是取决于当地的地理环境的。

2.4 更新种群

更新种群的主要方法是生成新的个体，而生成新个体的方式有两种：
（1）选出某一个聚类中的个体进行 2-insert 和 2-opt 操作；

（2）选出某两个聚类中心的个体进行顺序交叉操作。
顺序交叉如图3（c）所示，首先找到个体 xi 第一部分（选中的两个客户节点之间的部分），然后将 xj 放到 xi 第一部分之后，最后依次删除重复个体，xj 同理。

这个交叉操作有点像 遗传中的交叉操作。但不同的是，遗传中的交叉操作 是相同长度的片段 交换。而这个是不同长度的。比如第一个体选中的交叉片段为7-3-1-8,长度为4；第二个个体选中的交叉片段为8-6-4,长度为3. 遗传中的交叉操作，见博文《[基因遗传算法]进阶之四:实践CVRP》

生成新个体的部分参数为：
$r2、r3、r4，[0,1]$ 之间的随机数；
$p_1$ ，选择一个聚类的概率；
$p_2$ ，选择一个聚类中聚类中心的概率；
$p_3$ ，选择两个聚类中聚类中心的概率；
$C_i(i=1,2,\cdots ,m)$，第 i 个聚类的聚类中心；
$x_1$ ，从聚类中选出的第一个个体；
$x_2$ ，从聚类中选出的第二个个体；
$obj(x_i)(i=1,2,\cdots ,n)$ ，个体 xi 的目标函数值。

假设种群（population）数目为 n ，聚类数目为 m(m > 2) ，
更新种群的伪代码如下所示。

2.5 局部搜索策略

本文的目标函数成本主要与行驶距离、时间窗、车辆指派数相关，而车辆指派数又与取送货需求量相关，因此本文设计的大邻域搜索算子主要与上述四点相关，破坏操作结束后输出被移除的节点集合 R ，以及被破坏的个体 $S_{destory}$ ；修复操作结束后输出修复后的个体$S_{repair}$ 。本文共设计了6种“破坏”与“修复”算子。

2.5.1 破坏算子

（1）路径随机破坏：随机选择种群中一个个体 $x_i$ ，然后再随机选择一个节点放入被移除的节点集合 $R$ ，同时更新 $x_i$ ，重复操作，直到 $r$ 个节点被移除。

python举例 ：讲解一个简单的破坏算子

import numpy as np
Populations=[[1,2,3,4,5,6,7,8,9],[1,2,3,5,6,9,4,7,8],[1,2,3,4,6,7,5,8,9],[1,2,3,4,6,8,7,9,5],[1,2,3,5,7,9,4,6,8],[1,2,3,7,5,4,8,6,9] ]
#是某个种群,个数为6
## 一、路径随机破坏
xi=Populations[np.random.randint(low=0, high=6)] #随机选择一个个体
R=[] #被移除的节点集合
r = 4 #假设重复4次移除操作
for i in range(r):
    index=np.random.randint(10-r) #移除前的序列长度，随机选择一个下标
    R.append(xi.pop(index)) #将删除的元素放入结合R中
    print("更新个体xi为：",xi)
print("删除的元素为：",R)

运行结果展示：

（2）相似度破坏：该算子分别从行驶距离、时间窗、送取货需求量，以及是否同一路径四方面考虑两个节点的相似度。两节点间的相似度由 R(i,j) 表示，其表达式如下：

（3） 目标最差破坏：该算子主要目标是移除对目标成本影响最大的节点，包括考虑距离、时间窗两方面，从而直观地改善总的运输成本。

猜测的情况如下：

2.5.2 修复算子

（1）贪婪修复算子：在满足所有约束的基础上从被移除的节点集合 R 中随机选择一个节点，找到该节点可插入的位置，计算该点插入某一位置后的插入成本（将 R 中的某个节点插入 $S_{destory}$ 的某个位置后，此时修复后的总成本减去修复前的总成本即为 “插入成本” ），选择 插入成本增加最少的位置进行插入，重复操作直到R 为空集。

（2）遗憾值修复：在满足约束的基础上，R 中节点 i在 $S_{destory}$若有 $l$ 个可插入位置，则对应产生 $l$ 个插入成本。将 $l$ 个插入成本从小到大排序，排在第二位的插入成本减去排在第一位的插入成本即为 节点 i 插回 $S_{destory}$的遗憾值 。

xi=[1,2,3,6,5] ,原成本$10$, R=[8,4,9,7]
对于节点8满足约束的基础上有$l=6$个插入位置(所有的位置都可以插入),则产生$l=6$个结果。

• [8,1,2,3,6,5], 修复后成本11,插入成本$c1=1$
• [1,8,2,3,6,5], 修复后成本16,插入成本$c2=6$
• [1,2,8,3,6,5], 修复后成本14,插入成本$c3=4$
• [1,2,3,8,6,5], 修复后成本18,插入成本$c4=8$
• [1,2,3,6,8,5], 修复后成本15,插入成本$c5=5$
• [1,2,3,6,5,8], 修复后成本13,插入成本$c6=3$

对于贪婪修复算子会选择插入成本最小的第一种插法。
计算遗憾值：
排序：$c1(1)\to c6(3)\to c3(4)\to c4(5)\to c2(6)\to c4(8)$
遗憾值为 3-1=2

（3）最短距离修复：在满足约束的基础上从 R 中随机选择一个节点 k ，计算 k 各个插入位置的 节约值，如将节点 k 插入节点 i、j 之间，则 节约值 Δd(i,k,j) = dik +dkj - dij 。选择节约值最小的位置进行插入并更新 R ，重复操作直到 R 为空集。

2.6 自适应机制

为增强算法的自适应调整能力，本文 为每种破坏和修复算子分配了权重 λ 。基于赌轮盘的思想，在迭代过程中，根据每种算子被分配的权重在所有算子权重中所占的比例 ωi ，首先自适应选择其中一种破坏算子对当前个体 x 进行破坏，然后同样以自适应的方式选择修复算子进行修复操作。每种算子权重占比 ωi 计算公式为：

破坏、修复、记录的过程

1. 在解搜索前，选择破坏和修复算子,并记录
   destory_id,repair_id=selectDestoryRepair(model)
model.d_select[destory_id]+=1 model.r_select[repair_id]+=1
2. 执行破坏算子，获得移除的节点集合
   reomve_list=doDestory(destory_id,model,sol)这里的sol是邻域搜索的出发解。
3. 执行修复算子，获得新的解
   new_sol=doRepair(repair_id,reomve_list,model,sol)
4. 比较新解、最优解、出发解，根据得分规则得分。
   
5. 将最优解放入历史最优解中
   history_best_obj.append(model.best_sol.obj)

在上面的过程中，值得解说的有以下几点：

1. 破坏和修复算子的选择是没有关联的。所有共有3*3=9中选择(本文中设置了3种破坏3中修复)。但可成对选择的。
2. 每一轮 破坏和修复 都会有一个 得分，然后对应到破算算子和修复算子的位置 记录。然后这个得分又会影响算子的选择。
   得分和权重的影响如下：

2.7 迭代终止条件

ABSO有两种迭代的终止条件，只要满足条件之一便使算法终止迭代：
（1）当种群中的最优解连续不变的迭代次数达到预设的阈值 $ma{x}_{remain}$ ；
（2）当实际总迭代次数达到预设的最大迭代次数 $ma{x}_{gen}$
终止迭代后，选取全局最优解作为最终解输出。

2.8 ABSO算法流程

ABSO 算法1️⃣引入 ALNS 算法局部搜索机制，进行有效的邻域搜索，并2️⃣通过惩罚机制在一定情况下接受不可行解，加深种群搜索，3️⃣通过聚类及替换操作增加种群的多样性，避免算法陷入局部最优，以更大几率找到优质解，算法具体流程如下所示。

输入：算法参数、客户信息、车辆信息、迭代次数等。
输出：VRPSPDTW问题车辆配送方案。

1. 提取数据信息，初始化算法参数
2. 种群初始化：生成初始种群
3. 初始化全局最优，保留每次迭代全局最优
4. 开始迭代循环
   

在4.循环中，蓝框部分是优化种群的过程。
有点类似于遗传算法，只是把交叉、变异改成了蓝框部分。

3 算例实验与分析

为验证模型和算法的有效性，本文进行 3 组实验。实验1验证本文算法在小规模标准算例方面的有效性，分别对 10、25、50个客户数量的小规模标准算例进行实验。实验2验证本文算法对大规模标准算例的性能，针对6组不同类型大规模标准算例，每组随机抽选3个，共选取18个算例进行实验，每个算例包含100个客户。实验3引入具体问题案例对算法性能进行测试，验证算法实际应用价值。

本 文 算 法 由 Matlab- 2018a 编 程 实 现 ，在 CPU 为
AMD Ryzen 5 2500U，2.00 GHz，内 存 为 8.00 GB 的
Windows10 操作系统的计算机上运行。算法参数设置
如下：

• 最大迭代次数 Maxgen = 400 ；
• 种群规模 Popsize =50~100 ，种群的规模与客户点规模 n 有关，n 越小种群规模越小。
• 考虑测试算例车辆数目，选取聚类数目为 8个；
• p_replace 调整算法局部与全局的关系，将该参数设置为0.3；
• 参数 p_one 与算法搜索邻域大小成反比，将该参数设置为 0.4；
• p_one_center 、p_two_center 主要考虑局部最优与随机个体的关系，为防止陷入局部最优并且加大算法搜索效率，将上述参数分别设置为0.3、0.2。

算法参数根据控制变量法实验得出，每次调整只变动某一个参数进行反复实验，确定了合适的参数值，具体参数设置如表1所示。

3.1 小规模标准算例分析

实验 1 采用文献[8]的 9 个小规模标准算例进行实验，9个小规模标准算例包括3个10个客户规模，3个25个客户规模，3个50个客户规模。将实验结果与文献[8]（GA）算法、文献[9]（p-SA）算法和文献[10]（DCS）算法对比，所对比文献的☀️主要目标函数均为最小化车辆使用数（number vehicle，NV），☀️次要目标函数为最小化行驶距离（travel distance，TD），本文也采用相同的目标函数。

实验对比结果如表2所示，表3给出了算例Rcdp2504的车辆配送路线。不难看出，本文设计的算法可以全部求得小规模标准算例已知的最优解，验证了本文算法对VRPSPDTW小规模标准算例求解的有效性。

3.2 大规模标准算例分析

实验2 为验证本文算法对大规模算例的有效性，选用文献[8]设计的大规模标准算例进行实验。为保证实验的准确性，针对6组实验数据，随机选择每组的3个算例进行实验，每个算例包含 100个客户。在同时满足载重量和时间窗约束的条件下进行实验，将实验结果与文献[8]（GA）算法、文献[9]（p-SA）算法和文献[10]（DCS）算法算法进行对比。同样的本文主要目标函数为最小化车辆使用数（NV），次要目标函数为最小化行驶距离（TD）。

实验对比结果如表 4所示。可以看出，在🐸求解质量方面，本文提出的算法在随机选择的 18 个标准算例中有13个算例更新了最优解，4个算例取得与当前最优解相同的结果。其中算例Rcdp202与GA算法相比提升了7.52%，与 p- SA、DCS 算法相比分别提升了 12.03%、9.89%。🐸在求解速度方面，如图4所示，本文算法可以在较少的迭代次数内快速收敛，当算法陷入局部最优解时，可快速跳出局部最优，具有较好的寻优性能。 为更直观地展示本文实验结果，图 5给出了算例 Rcdp106的配送路线图。综合随机选取的 18 个标准算例实验数据，本文算法更新或达到最优的算例占测试算例的94.45%，其中 72.22%的算例更新了最优解，充分说明了本文提出的模型和算法在解决大规模标准算例方面的有效性。

3.3 应用案例分析

实验 3 为验证本文算法在实际物流案例中的有效性，本文获取了某物流快递公司在一定区域内的数据信息，包括1个中转物流中心，20个门店的送货量、取货量以及服务时间要求。为进一步提高算法的可靠性及实际案例的应用价值，本文在考虑道路通畅信息的情况下导出配送中心与各个门店之间距离矩阵。此外，通过实地调研的方式获取各个门店的取送货量需求以及服务时间需求，保证数据的准确性。为计算方便，对中转配送中心和各个门店进行编号，其中0表示中转配送中心节点，1~20表示20个门店节点，具体数据如表5所示。

仿真实验开始前首先计算中转中心及各个门店考虑道路通畅的距离矩阵，然后将客户的时间窗约束转换为具体数值，继而程序开始读取各个门店的数据信息，进行迭代运算。同样的，本实验的主要目标函数为最小化车辆使用数（NV），次要目标函数为最小化行驶距离（TD），算法最短路径变化趋势曲线如图 6 所示，图 7 给出了车辆配送路线。与模拟退火算法（SA）、鲸鱼优化算法（WOA）进行对比，结果表明，在寻优能力方面，本文求解最优解为 237.85，与 SA 算法（282.64）、WOA 算法（261.42）相比分别有 18.83%和 9.91%的优化；在收敛速度方面，本文算法能够在较短的迭代次数寻得优质解，且不易陷入局部最优。充分表明了本文算法在解决实际VRPSPRTW物流运输问题时的可行性和实际应用价值。

4 结束语

VRPSPDTW 是一类应用广泛的复杂车辆路径问题，因其问题的特殊性、复杂性和诸多限制条件等特征，需要高性能的求解算法。本文针对该问题，构建了基于车辆使用成本和车辆行驶距离成本总成本最少的路径优化模型，提出自适应头脑风暴算法（ABSO）求解。ABSO 具有如下优点：
采用新的编解码方式，并对不满足约束条件的个体进行多项惩罚，扩大全局搜索区域；
使用聚类操作和三种不同的路径搜索策略来推动算法较快地到达优质解空间；
以六种破坏-修复算子备选集合为依据，通过自适应动态选择邻域搜索机制对优质解空间进行局部搜索，有效平衡了搜索广度与搜索深度之间的关系，从而提升算法性能。

对不同规模测试算例和算法进行比较，ABSO在小规模客户标准算例和大规模客户标准算例以及实际物流案例中，均能以较快的收敛速度找到近似最优解，且寻优性能好于所对比算法，充分验证了本文算法的有效性。
本文研究的VRPSPDTW 问题是需求不可拆分的问题，即每个客户只能由一辆车服务一次，后续研究方向是松弛每个客户只能由一辆车服务一次的约束，考虑需求拆分对VRPSPDTW产生的影响以及相对应的算法设计。