混合优化算法求解同时送取货车辆路径问题

李 珺，段钰蓉，郝丽艳，张维维

兰州交通大学 电子与信息工程学院，兰州730070

近年来，为了避免环境污染，很多国家制定了相应的法律法规，要求企业对整个产品的生命周期负责，不仅要提供客户满意的配送服务，还要进行废弃物的回收利用。因此，企业有了构建正向物流配送和逆向废旧物品回收相结合的物流系统的迫切需求；而客户往往只在特定的时间窗内接受服务。为了提升服务质量和客户满意度，企业不仅需要完成同时送取货的作业，还要额外考虑客户的服务时间窗。因此，如何设计出合理完善的带时间窗的双向物流系统，成为理论研究和实践中关注的重要问题。在运筹学领域，该类问题被称为带时间窗和同时送取货的车辆路径问题（vehicle routing problem with simultaneous delivery-pickup and time windows，VRPSDPTW）。

VRPSDPTW 问题作为车辆路径问题（vehicle routing problem，VRP）的重要扩展，属于NP-hard 问题。这类问题的解决方法主要分为精确算法和启发式算法。2002年，Angelelli等最早提出VRPSDPTW问题，使用精确算法中的分支-价格法求解算例规模为20 个客户点的小型算例。当客户规模增大时，精确算法不能在合理的时间范围内求得满意解。学者们开始尝试设计不同的启发式算法来解决VRPSDPTW问题。Cao等提出了一种改进的遗传算法，根据用户的优先顺序重新设计了编码方式。当最大客户数目为8时，改进算法能有效找到最优解，然而，在现实生活中，客户数目远远多于8个。Boubahri等设计了一个多智能体群体系统来解决VRPSDPTW问题。尽管这种解决方法很新颖，但是作者没有提供任何数值实验结果。2012年，Wang等采用协同进化遗传算法解决VRPSDPTW问题，并在经典的Solomon数据集的基础上设计了VRPSDPTW基准实例，实验结果表明，所提出的协同进化遗传算法能够在较短的时间内找到满意解。王超等运用回溯搜索优化算法来求解该问题，选取了测试数据集中的6个算例进行了实验。王超等提出了一种离散布谷鸟算法来求解该问题。除此之外，还有改进全局人工鱼群算法、大邻域搜索算法等。

目前关于VRPSDPTW 问题，虽然学者们已经进行了一些研究，但是仍然缺乏有效的求解方法。迄今为止，VRPSDPTW问题的解决，主要采用启发式算法，并且以Wang等设计的测试数据集作为国际通用数据集，各类文献中的已知算法在对算例进行测试时，都无法找到所有算例的最优解，因此，高效、稳定的求解方法成为学者们追求的目标。

为了更好地解决VRPSDPTW 问题，通过大量的实验发现，模拟退火算法（simulated annealing，SA）在依据概率突跳特性进行降温寻优的过程中，对较差的解具有一定的容忍性，使得算法的全局寻优能力优于很多当前流行的智能优化算法，同时能够在一定程度上克服对初始解的依赖性；自适应大规模邻域搜索算法（adaptive large-scale neighborhood search，ALNS）能够较好地避免算法在寻优过程中陷入局部极值，且在邻域搜索的过程中，通过一些启发式信息来指导寻优，能够在一定概率上获得高质量的解。将模拟退火和大规模邻域搜索算法相结合，本文提出一种混合优化算法（SA-ALNS），以标准模拟退火算法作为主体，用插入启发式算法构造问题的初始解，结合自适应大规模邻域搜索算法进行寻优。实验结果表明，本文所提出SA-ALNS 有效缩短了物流配送路径长度，节约配送成本，为各企业解决VRPSDPTW问题提供有效的解决方案。

1 VRPSDPTW问题

1.1 问题描述

VRPSDPTW 问题可以描述为：一个配送中心拥有若干型号相同且载重能力相同的车辆，为分布在不同位置的已知客户提供送货、取货服务。每一个客户的地理位置信息已知、送货量和取货量已知、服务时间窗以及持续服务时间已知。要求配送中心在满足客户需求的基础上规划出合理的配送路线，最小化总配送成本，并满足以下假设：

（1）每个客户只能由一辆车完成送货和取货服务，且需求不可拆分；

（2）每辆车均从配送中心出发，在送取货任务完成后返回配送中心；

（3）每辆车的载货量不能超过车辆载重；

（4）在客户规定的服务时间窗内，先进行送货服务，再进行取货服务；

（5）每一条道路都畅通，不考虑道路突发状况。

1.2 符号定义

为了方便构造VRPSDPTW 数学模型，需要对所用到的符号进行说明：

（1）参数

表示需要服务的客户集合和配送中心；N表示需要服务的客户集合，∈{1,2,…,} ；表示配送中心；表示车辆集合，={1,2,…,}；D表示每个客户的送货量；P表示每个客户的取货量；D表示客户到客户的欧氏距离(,∈)；[ET,LT]表示客户的服务时间窗，其中ET为客户允许的最早开始服务的时间，LT为客户的最晚开始服务时间；S表示客户所需的持续服务时间；表示车辆的最大载重量。

（2）决策变量

（3）衍生变量

St表示客户的开始服务时间；T表示从客户到客户所花费的时间；表示车辆从配送中心出发时的装载量；p表示车辆在离开客户时的装载量，∈{1,2,…,}。

1.3 VRPSDPTW数学模型

其中，式（1）为目标函数，表示最小化车辆总距离；约束（2）表示每个客户都只能由一辆车服务；约束（3）保证所有车辆从配送中心出发最终返回配送中心；约束（4）表示车辆在离开配送中心时的装载量即某条路径上所有客户的送货量总和；约束（5）表示车辆在离开每个客户时的装载量，即离开上一个客户时的装载量减去本客户的收货量（车辆的送货量），再加上本客户的寄货量（车辆的取货量）；约束（6）保证车辆在任何时刻的装载量都不超过车辆的最大载重量；约束（7）表示满足客户的服务时间窗要求。

2 VRPSDPTW问题的混合优化算法设计

混合优化算法（SA-ALNS）在SA 的基础上结合ALNS 思想进行寻优。SA-ALNS 中设计了多个插入、删除算子，且为每个算子赋予分数和权重，在邻域搜索的过程中根据各个算子的分数和权重动态选取插入算子和删除算子对现有解进行重构，从而得到质量更好的解。由于ALNS 的接受准则和停止准则一般是根据目标值来判断，这种方法存在准确性差、鲁棒性弱的缺点，引入SA 中的退火准则来控制解的更新，提高解的质量。

2.1 编码方式

算法采用整数编码，编号0 表示配送中心，编号1,2,…,表示客户点。令=[[1],[2],…,[]]，为负责服务客户的车辆顺序排列的组合。假设为客户服务的车辆规划路径如图1 所示，则=[[1],[2]]=[0 7 2 3 9 1 0 0 6 5 8 4 0]。从图1 可以看出，共有9 个需要服务的客户，配送中心一共启用了2 辆车，第一辆车从配送中心出发，分别为客户7、客户2、客户3、客户9、客户1 提供送取货服务，最后返回配送中心；第二辆车从配送中心出发，服务客户6、5、8、4 后，返回配送中心。

图1 车辆规划路径Fig. 1 Vehicle planning route

2.2 初始解构造

采用插入启发式算法构造VRPSDPTW 问题的初始解。用插入法构造初始解时，由于客户有服务时间窗约束，故采用Solomon的基于距离与时间加权的插入标准。

式中，为待插入客户点；d表示客户到客户的距离；(,,)表示客户插入、两点间后，路径距离的增量。

式中，St表示将客户插入客户、之间后，客户的新开始服务时间；St为客户的原开始服务时间；(,,)表示客户插入路径后对客户的开始服务时间的影响。

式中，为车辆当前行驶速度，(,,)表示客户插入路径后，对路径产生的影响。在配送过程中，为了同时考虑路径增加部分和服务时间增加部分对整体配送过程的影响，引入了车辆行驶当前速度值，通过当前速度与增加服务时间的乘积，将时间量转化为路程量，使得衡量的标准统一为距离，方便计算；考虑到车辆在配送过程中可能会出现交通拥堵的情况，车辆的行驶速度会发生变化，式（10）在速度动态变化的情况下能更精确地反映待插入客户对整个路径的影响程度，为求解多通路车辆路径问题提供一种思路。

式中，(,,)表示插入标准值。通过(,,)筛选出距客户和客户越近且距离配送中心越远的客户点，优先插入路径中，从而提高后期优化阶段中SAALNS算法的收敛速度。计算中，引入常数≥1，对进行放大，提高插入标准值的敏感性。

基于距离与时间加权的插入法，过程如下：

（1）生成一条只包含车辆起点和终点的初始路径[0 0]；

（2）在所有的客户点中随机选择一个客户点作为种子节点插入初始路径中；

（3）计算剩余客户点在所有可能插入位置的插入标准值；

（4）将插入标准值降序排列，把插入标准值最大的客户点插入到最佳可行的位置，若路径中客户总送货量超过车辆的最大载重量，则重新生成一条路径；

（5）重复步骤（3）、（4），直到所有的客户都插入路径。

2.3 路径优化

在寻优阶段，引入删除算子、插入算子和自适应选择策略进行路径优化。删除算子按照一定的规则从路径中删除部分客户点，插入算子将删除的客户点重新添加到路径中的合理位置，得到新解。根据各个删除、插入算子在程序运行中的表现，自适应调整权重，不断地更新算子的选中概率，以不同的方式完成删除和插入操作，提高解的多样性，从而更好地进行全局寻优。

选用四种删除算子，通过不同的方式随机在路径中选择客户点，将其在路径中删除，为局部寻优做准备。

（1）Random removal算子

该算子从客户集合中随机选取个客户，将个客户从相应的路径中移除，以增加搜索的多样性。

（2）Random schedule removal算子

该算子会随机选择一条路径，将这条路径上的所有客户删除，为这些客户重新寻找配送位置。这种方式在一定概率上能够减少车辆的使用数量，从而降低物流成本。

（3）Worst removal算子

算子的主要目的是最小化总行驶距离。从客户集合中选取一个客户点，计算并保存该点被删除前后路径距离的节约值，剩余的客户点重复此过程，从而得到全部客户点被删除前后路径距离的节约值，将所有客户点距离的节约值降序排序，选取前个节约值较大的客户点从相应的路径中删除。

（4）Node distance removal算子

该删除算子首先计算每条路径的平均距离占用值，然后将平均距离占用值最大的路径中的客户点全部删除。平均距离占用值的计算公式为：

式中，()表示第条路径的总距离，N表示第条路径中的客户数量。根据平均距离占用公式，选择一条最不经济的路径删除其中所有客户点。

文中选用两种插入算子，使用不同的插入规则将删除的客户点重新插入到路径中。

（1）Greedy insertion算子

该方法随机选取一个待插入客户点，遍历每条路径，找到所有既满足时间窗约束又不超过车辆最大载重量的可插入位置，计算该客户点插入到每个可插入位置前后的距离增量，选择距离增量最小的位置将客户点插入。若遍历所有路径都没有找到符合时间窗和车辆载重约束的可插入位置，就重新生成一条初始路径，将客户点添加到其中。重复上述过程，直到将所有的待插入客户点添加到路径中。

（2）Regret insertion算子

混合算法以模拟退火算法的基本结构进行寻优，寻优过程中，以自适应方式选择删除和插入算子。

每一个温度下（以下简称为阶段），算法进行次寻优迭代；每次迭代时，SA-ALNS采用轮盘赌机制选择一个删除和一个插入算子完成路径的更新；之后根据新得到的路径的优劣，对所选用的删除、插入算子评分。所得分数将影响下一阶段中该算子的权重，得分越高的算子在下一阶段轮盘赌选择策略中的权重值将越大，被选中的概率越高。算子第阶段的得分，计算公式如式（14）。

其中，π表示算子在第个阶段所得分数；ε表示算子在第阶段被选择的次数；常数∈[0,1]，本文取的值为0.1。每个算子的权重与该算子所得分数、选择次数有关，分数越高，权重越大，选择概率就越大。算子的权重作为一种启发式信息，使算法偏向于选择效果好的算子，从而在很大概率上能够获得更满意的解。

2.4 可行解的接受条件和迭代结束标准

2.5 混合优化算法流程

初始化基本参数：初始温度，每个温度下的最大迭代次数，结束温度。采用插入启发式算法构造初始解。

用轮盘赌机制分别选择一种删除算子和插入算子，生成一个新解。

计算的目标函数值，根据Metropolis准则更新当前解，并更新各个算子的分数。

若达到每个温度下的最大迭代次数，则更新删除、插入算子的权重并执行降温=操作，其中，为降温速率。

若达到足够低的温度(＜)，输出最优解，整个算法结束；否则回到步骤2。

混合优化算法的流程图如图2所示。

图2 混合算法流程Fig. 2 Hybrid algorithm flow

3 实验与分析

程序使用Matlab（R2016a）编写，并在IntelCorei5-7300HQ CPU@2.50 GHz处理器，8 GB内存和16位操作系统的Windows10计算机上进行。

为了验证SA-ALNS 算法的性能，选取Wang 等设计的求解VRPSDPTW 的测试算例（数据集网址http://oz.nthu.edu.tw/～d933810/test.htm）。共56 个大规模算例，可分为Rdp1、Rdp2、Cdp1、Cdp2、RCdp1、RCdp2，共6 类。Rdp1 类和Rdp2 类中的客户地理位置满足随机分布，较为分散；算例Cdp1、Cdp2中的客户位置满足聚类分布，相对较聚集；RCdp1 类和RCdp2 类客户地理位置通过聚类分布和随机分布混合生成，部分聚集，部分分散。此外，Rdp1、Cdp1、RCdp1 算例集具有较紧的时间窗，较小的车辆装载量；而Rdp2、Cdp2、RCdp2算例集的时间窗较宽，车辆装载量较大。

SA-ALNS算法在每个算例上运行10次，并记录最优值。本文提出的SA-ALNS 算法与文献[6]中的DCS 算法、文献[11]中的p-SA 算法、文献[12]中的ETSP算法、文献[13]中的ALNS-PR算法、文献[14]中的VNS-BSTS 算法以及文献[15]中的Par-SAA 算法进行对比。SA-ALNS 算法在Cdp1 类、Cdp2 类算例上与其他算法最优值的对比结果如表1 所示，在Rdp1 类、Rdp2 类算例上的对比结果如表2 所示，在RCdp1类、RCdp2类算例上的对比结果如表3所示。

表1 SA-ALNS在Cdp类算例与其他算法的最优值对比Table 1 Best value comparison between SA-ALNS and other algorithms in Cdp examples

表2 SA-ALNS在Rdp类算例与其他算法的最优值对比Table 2 Best value comparison between SA-ALNS and other algorithms in Rdp examples

表3 SA-ALNS在RCdp类算例与其他算法的最优值对比Table 3 Best value comparison between SA-ALNS and other algorithms in RCdp examples

混合优化算法的参数设置：初始温度设为500，截止温度为0.001，降温速率为0.95，最大迭代次数设为100。

对Cdp1 类、Cdp2 类算例进行测试，SA-ALNS 算法在每个算例上的最好结果见表1。从表中可以看出，在Cdp104、Cdp108、Cdp109 算例中，SA-ALNS 算法的实验结果比VNS-BSTS、ALNS-PR的结果差；在Cdp105 算例中，SA-ALNS 的寻优效果弱于DCS 算法；在Cdp204算例上，DCS、ALNS-PR算法的实验结果优于SA-ALNS；在除Cdp204 的其他Cdp2 类算例中，SA-ALNS算法均获得了最优解；本文算法在Cdp1类和Cdp2 类算例上都优于p-SA 算法。总的来说，SA-ALNS算法的计算精度较高。

由表2 可看出，与p-SA 算法相比，在Rdp103、Rdp104、Rdp107、Rdp108算例上，SA-ALNS的求解性能弱于p-SA，在其余算例上的求解性能均优于p-SA；

同DCS 算法相比较，SA-ALNS 在Rdp104、Rdp105、Rdp107、Rdp108、Rdp204算例上的效果弱于DCS，其余算例的效果优于DCS；与VNS-BSTS 算法相比较，在Rdp104、Rdp112、Rdp206 算例上，SA-ALNS 的实验结果较差，但在其他算例上都领先于VNS-BSTS；同ETSP 相比，SA-ALNS 在除Rdp204、Rdp207 之外的其他算例上都获得最优解；同ALNS-PR相比，SAALNS 在Rdp104、Rdp106、Rdp108、Rdp205、Rdp206、Rdp208、Rdp209、Rdp210 算例上的求解性能弱于ALNS-PR，但在其余算例上求解性能强于ALNS-PR；与Par-SAA算法相比，SA-ALNS在除Rdp104的其他算例上均优于Par-SAA。在Rdp1、Rdp2 类算例中，SA-ALNS 在82.6%算例上优于p-SA，在78.2%算例上优于DCS，在87.0%算例上优于VNS-BSTS，在81.8%算例上优于ETSP，在65.2%算例上优于ALNSPR，在91.7%算例上优于Par-SAA。

实验结果分析：由表3 可以看出，在RCdp1 类算例中，SA-ALNS在求解RCdp101、RCdp103、RCdp106算例时，寻优结果弱于p-SA和DCS，但在其余算例的寻优结果都强于p-SA、DCS；SA-ALNS在求解RCdp103、RCdp104、RCdp105、RCdp106、RCdp107时，求解能力比VNS-BSTS、ALNS-PR 弱。在RCdp2 类算例，SAALNS算法的运行结果均优于对比算法。

从Cdp1、Cdp2、Rdp1、Rdp2、RCdp1、RCdp2 算例的实验结果可以看出，本文所提出的SA-ALNS 在求解VRPSDPTW问题中有不错的效果，说明该方法是行之有效的。

图3是SA-ALNS与其他的算法分别在Cdp1类、Cdp2 类、Rdp1 类、Rdp2 类、RCdp1 类、RCdp2 类算例上的实验结果对比，能够更加清晰地看出不同算法求得的最短距离值之间的差距。

图3 不同算法在不同算例上的对比Fig. 3 Comparison of different algorithms on different examples

部分算例的路径优化图，如图4。

图4 部分算例的路径优化图Fig. 4 Path optimization graph of some examples

4 结束语

本文针对VRPSDPTW问题提出了一种SA-ALNS算法，该算法运用插入启发式算法构造初始解，以模拟退火为框架，采用自适应大规模邻域搜索算法进行邻域搜索，并设计了四种删除算子和两种插入算子，增大邻域搜索的范围，从而加速解的收敛。通过Cdp1类、Cdp2类、Rdp1类、Rdp2类、RCdp1类、RCdp2类算例测试，并与其他已知算法对比，最后证明了SA-ALNS 算法的优越性和有效性。现如今，人们越来越关注环境保护问题，绿色物流将是未来物流行业的发展趋势，在车辆路径问题中考虑碳排放等约束条件，从而衍生出更多复杂的VRP问题，本文所提出的SA-ALNS 为解决这些复杂VRP 问题提供一种新思路。