基于改进禁忌搜索算法的VRPSPDTW 研究

张 思，王 海 （上海大学 管理学院，上海 200444）

ZHANG Si， WANG Hai (School of Management, Shanghai University, Shanghai 200444, China)

0 引 言

近年来，随着经济水平的快速发展，人们的生活条件不断改善，对生鲜产品的需求量逐年上升。据统计2018 年生鲜市场交易额约为1.91 万亿元，然而由于产品腐烂变质造成的损失高达1.23 千亿元[1]。所以为了保证产品新鲜度从而降低货损成本，运输途中会全程低温冷链，但这会大幅增加能耗成本。合理的车辆调度可以缩短产品的在途运输时间，保证生鲜产品的新鲜度，降低货损率，减少燃油消耗量，降低运输成本。因此冷链物流的车辆路径问题成为新的研究热点，引起了众多学者的关注[2]。

为了提高客户满意度，产品需要在规定的时间窗内交付客户，然而由于生鲜产品的易腐性，因此客户对产品新鲜度有一定要求，全程冷链降低了腐烂速度，但是会加大运输油耗，产生更多的二氧化碳，不利于环境保护。现有的研究已经考虑了时间窗[3-5]、碳排放[6-8]、产品新鲜度[9-10]等多种情况下的冷链物流车辆路径问题，但是在上述研究基础上考虑同时取送货情况下的冷链配送研究还相对比较少。生鲜产品要求在整个配送过程中保持恒定的低温，车门的频繁开关和装载货物时频繁搬动会影响温度控制，加速产品的腐烂变质；同时，生鲜产品的逆向物流量主要为包装物的回收和少量缺陷产品的退货，比一般产品少。将正向的配送和逆向的回收单独运作，必然会增加制冷成本和运输成本。因此，采用同时取送货策略，可以节约运输、制冷、回收等成本，有利于节约资源和保护环境。所以本文在前人的基础上，考虑顾客同时有取货和送货的需求，建立带时间窗的同时取送货车辆路径问题（Vehicle Routing Problem with Simultaneous Pickup-Delivery with Time Windows， VRPSPDTW） 运输配送模型。

2003 年 Angelelli 等[11]首次提出 VRPSPDTW 问题，Savelsbergh[12]证明了 VRPTW （Vehicle Routing Problem with Time Windows） 为NP-hard 问题，那么它的拓展VRPSPDTW 也一定为NP-hard 问题。由于精确算法仅适用于求解VRPSPDTW 的小规模问题，而对于中大型规模，学者们更倾向于设计启发式算法获得最优可行解。Lai 等[13]应用改进的差分进化算法求解了一个8个顾客规模的算例。Wang 等[14]在Solomon[15]的VRPTW 测试算例的基础上，提出了VRPSPDTW 的测试算例，并使用共同演化遗传算法进行求解。该算例囊括了9 个中小型算例（顾客规模为10，25，50 各3 个） 和56 个大规模算例（顾客规模为100），成为国际上针对VRPSPDTW 的通用算例。Wang 等[16]采用并行模拟退火算法，王超等[17]应用离散布谷鸟算法，黄务兰等[18]使用改进全局人工鱼群算法都对该算例进行求解。

禁忌搜索算法（Tabu Search，TS） 是一种邻域逐步寻优的局部搜索算法，采用禁忌策略减少循环搜索，提高搜索效率。李相勇[19]在对VRP 问题求解算法详细综述的基础上指出，在各种启发式算法中以禁忌搜索算法的求解质量最高，是一种高效算法。本文选用标准TS 作为算法框架，加入多种性能提升策略，提高算法的寻优能力，对VRPSPDTW 问题进行求解。

1 带时间窗的同时取送货车辆路径问题

1.1 问题描述

冷链VRPSPDTW 可以被描述为：给定一个配送中心、一组位于不同位置的顾客以及一个冷藏车队，每个顾客都有自己的服务时间窗以及取货需求和送货需求，管理者的决策是为车队的每一辆车规划服务顾客的行驶路径，优化总的物流成本。

1.2 假设

一个配送中心为若干个顾客提供服务，配送中心和顾客的位置都是确定的，各顾客的取货需求和送货需求都是已知的，每辆冷藏车的起始点和终止点都是配送中心；配送中心的冷藏车数量充足且为同一型号；冷藏车辆在运输过程中匀速行驶，不考虑交通情况的影响；每个顾客只允许被服务一次。

1.3 参数

（1） 集合。V 为顾客点集合，V=｛i ｝，i=1，2，…，n；i=0 表示配送中心，其中节点集合 U=V∪ ｛0 ｝；K 为冷藏配送车辆集合，K=｛k ｝，k=1，2，…，m。

（2） 参数。c1：每辆冷藏车的固定使用成本；c2：冷藏车行驶单位距离的运输成本；c3：冷藏车提前到达客户点处的单位时间等待成本；c4：冷藏车延迟到达客户点处的单位时间惩罚成本；c5：冷藏车排放单位重量二氧化碳的成本；c6：单位重量制冷剂的使用成本；c7：单位重量货物的损耗成本；Q：冷藏车的最大载重量；dij：客户点i 与客户点j 之间的距离；tij：从客户点i 到客户点j 所需的时间；pi：客户点i 处的取货需求量；qi：客户点i 处的送货需求量；ti：冷藏车在客户点i 处装卸货所需的时间；f：燃料的消耗函数；σ1：运输过程中消耗单位体积的燃料产生的二氧化碳重量；σ2：运输过程中制冷设备单位时间内产生的二氧化碳重量；g1：运输过程中产生的热负荷函数；g2：装卸货过程中产生的热负荷函数；α1：运输过程中单位时间内单位货物的损耗比例；α2：装卸过程中单位时间内单位货物的损耗比例； ［ETi，LTi］：客户点i 的时间窗。

1.4 数学模型

1.4.1 碳排放成本

碳排放成本主要包括两个方面：一是发动设备产生的CO2成本，二是制冷设备产生的CO2成本。

（1） 发动设备产生的碳排放成本。发动设备产生的CO2主要通过燃油消耗量来计算，依据参考文献[20]，冷藏车单位距离燃料消耗量为；

其中：ρ0、ρ*分别为空载、满载下运输单位距离时燃料的消耗量，X 为冷藏车的载重量，Q 为最大载重量。

由于发动设备只在运输过程中启动，所以发动设备产生的碳排放成本为：

（2） 制冷设备产生的碳排放成本。由于冷藏车的制冷设备与发动设备是相互独立的，所以等待过程中发动机熄火，而制冷设备仍继续工作。冷藏车服务完最后一个顾客返回配送中心时，车上已没有生鲜产品，因此会关闭制冷设备。所以制冷设备产生的碳排放成本为：

综上，整个配送过程中的碳排放成本为：

1.4.2 制冷成本

制冷成本主要包括运输途中和等待过程中由于冷藏车内外温差不同所引起的传热，以及装卸过程中的热空气对流，可以通过制冷剂的消耗进行计算制冷成本。

（1） 运输过程。运输途中因为内外温差单位时间产生的热负荷为：

其中：β 表示车辆的折旧程度，R 为车辆的导热率，S 为车辆平均受热面积，可表示为分别表示车厢的内外表面积，Tn、Tw分别表示车厢的内外温度。

所以，运输途中的制冷成本为：

（2） 等待过程。由于等待过程中并未打开车门且制冷设备仍在工作，热负荷产生函数不变，因此等待过程中的制冷成本为：

（3） 装卸过程。冷藏车到达顾客进行装卸服务时需打开车门，此时热空气对流，单位时间产生的热负荷为：

其中：Vk表示车厢的体积，γ 表示开门频率系数。

所以，冷藏车在装卸过程中的制冷成本为：

综上，整个配送过程中的制冷成本为：

构建冷链VRPSPDTW 的数学模型如下：

式（2） 保证每个客户只能被一辆冷藏车服务，式（3） 和（4） 是两个变量之间的关系，保证每辆冷藏车运输时的载重量不能超过它的最大载重量，式（5） 保证每辆冷藏车从配送中心出发服务完所有客户后必须回到配送中心，式（6） 保证冷藏车从配送中心出发时的载货量等于线路上顾客的送货总需求，式（7） 表示冷藏车经过顾客前后载重量变化，式（8） 保证冷藏车的载重量始终不超过最大容量，式（9） 和（10） 确保每辆冷藏车服务时间的连续性，式（11） 和（12） 表示两个变量的取值范围。

2 算法设计

TS 算法是一种逐步寻优的邻域搜索算法，从初始解出发，记忆搜索过程中局部最优解，避免在下一次搜索过程中进行重复搜索，尽可能多地扩大搜索范围，利用局部最优的信息逐步达到全局寻优。然而，标准TS 算法对初始解的依赖性很强，且很难对某一特定问题确定有效的禁忌长度，难以避免搜索过早收敛，从而陷入局部最优，错失全局最优解。

本文设计改进的TS 算法采用RCRS 算法生成较优的初始解，保证解的质量，邻域变换时应用了多邻域随机变换策略，实现对多个邻域的快速搜索，有利于丰富邻域解的多样性，避免算法过早收敛，WTS 编码方式缩短了邻域运算时间，减少了迭代次数，响应性策略可以依据搜索进程动态地调整禁忌长度，加强了TS 算法的搜索机制，使得求解更加全局性。

下面介绍改进策略的具体流程。

2.1 路径的编码与解码

VRP 问题的常见编码方式是以配送中心节点（一般用0 表示） 作为子路径的分隔符，如0-1-2-3-0-4-5-6-0 表示0-1-2-3-0 和0-4-5-6-0 两条子路径。一方面，这种方法需预先估计最小车辆数（需求总重量/车辆最大载重量），然而在有时间窗约束的前提下，车辆在进行服务时并不一定能满载出发，易导致车辆的预估不足；另一方面，算法经过邻域交换产生的新解不一定是可行解，需要进行检验，增大算法运行开销。

基于此，本文选用的编码方法为首先生成一条主路径，然后将主路径划分为几条子路径，所以划分算法的优劣对TS 算法的性能举足轻重。Beasley[21]以车辆的载重量为划分节点，若加上当前顾客的需求，子路径的总需求大于车辆的容量，则以当前顾客为起点产生一条新的子路径继续进行划分，直到主路径划分完毕。这种方法虽然效率很高，但对主路径的顾客顺序依赖性很强。李进等[22]继承了Beasley 的划分思想，提出了一种WSS（Weight and Speedbased Split） 划分算法，但是对于VRPSPDTW 问题来说，这种方法没有考虑时间窗以及顾客的取货需求对路径划分的影响。因此本文对WSS 进行改进，提出适合VRPSPDTW 模型的WTS（Weight and Timebased Split） 算法，WTS 算法的具体步骤如下：

步骤1：初始化

假设节点i 的最小总费用（指车辆从配送中心出发，依次完成该节点及其前面所有节点的任务后返回配送中心这一过程中所发生的费用之和，包括固定成本和运输成本） 为V［i ］，节点i 的最小总费用路径的直接前继节点（指上一辆车服务的最后一个客户） 为P［i ］。

令V［i ］=∞，V［0 ］=0，P［i ］=i-1，∀i∈V；

步骤2：最优路径划分

计算每个客户节点i （i=1，2，…，n ）的最小总费用以及直接前继节点，置i=1；

步骤2.1 令当前车辆的载重量load=0，总费用cost=0，令j=i；

步骤2.2 load=load+第j 个节点的需求量；

步骤2.3 若load＞Q 或不满足时间窗，则i=i+1，转步骤2.1；否则转步骤2.4；

步骤2.4 若V ［j- 1 ］+cost＜V［j ］，则V［j ］=V ［j- 1 ］+cost，P［j ］=i-1；

步骤3 算法终止

所有顾客都被插入路径中，若j＞n，则算法结束，否则令j=j+1，转步骤2.2。

2.2 初始解的构造

标准TS 算法随机生成初始解进行迭代搜索，这种生成方法虽然简单有效，但是Tan 等[23]研究发现TS 算法对初始解有一定的依赖性，初始解的优劣将最终影响最优解的质量。为了保证初始解的质量，本文对Dethloff[24]解决VRPSPD 问题时提出的RCRS（Residual Capacity Radial Surcharge） 算法进行改进，加入时间窗约束，生成初始解。

RCRS 算法的具体步骤如下：

步骤1：选择种子客户

计算所有未路由的客户的最早开始服务时间 （=max ｛车辆从配送中心到达顾客的时间，顾客允许的最早时间窗｝），选择开始服务时间最小的客户作为种子客户。

步骤2：判断是否有可插入位置

步骤2.1 种子客户选好后，生成初始路径（如0-1-0，该路径有2 个插入位置）。判断是否存在未路由客户，若存在，继续下述步骤，否则转步骤4。

步骤2.2 依次判断未路由客户是否满足插入位置的要求（载重量约束，时间窗约束），若存在可插入位置，转步骤3，否则转步骤1。

步骤3：计算可插入位置RCRS 标准值

计算可插入位置的RCRS 标准值，计算方法与文献[24]相同，最后选择RCRS 标准值最小的客户插入，然后转步骤2.2。

步骤4：算法终止

所有客户都被插入路径，算法终止。

2.3 邻域结构设计

禁忌搜索基于邻域变换进行搜索，确定邻域操作至关重要。WTS 编码方法使得邻域操作时简单方便，只需进行内部操作即可。本文选用3 种广泛应用于车辆路径问题的邻域结构，操作时随机选择其中一种。例如解为123456，下划线处为随机选择的两个顾客i 和j，结果如下：

（1） 点交换。将顾客i 和j 的位置互换，得到：153426；

（2） 点插入。将顾客i 插入到j 后，得到：134526；

（3） 点逆序。将顾客i 和j 之间的顾客逆序，得到：124356。

2.4 禁忌对象及禁忌长度

将移动元素作为禁忌对象，对三种邻域操作，建立三个禁忌表来存储相应的禁忌对象。禁忌长度的确定是TS 算法的关键，决定了禁忌时间的长短，从而影响解的搜索范围和质量，禁忌长度过短则易陷入循环，算法难以跳出局部最优点；过长则会加大数据存储量，甚至导致算法无法继续进行。标准TS 选用固定的禁忌长度，然而对于不同的问题很难确定统一的禁忌长度。响应性禁忌搜索算法（Reactive Tabu Search，RTS） 对标准禁忌搜索算法进行改进，基于解的重复次数和解的重复时间差在搜索过程中动态调整禁忌长度。调整规则有两种方式，一是解重复出现的间隔在设定的最大间隔之内，表明禁忌长度过短，增大禁忌长度；二是当前时间距离上次禁忌长度发生改变的时间超过预设值，表明搜索区域过大，减小禁忌长度。若解的重复次数超过预设值，表明解陷入混沌，即陷入局部最优，此时算法采用逃离机制，跳出当前区域，重新进行搜索。为了避免禁忌过度，每当历史最优解被更新，清空禁忌表，使搜索更自由。RTS 算法具体步骤如下：

步骤1：初始化RTS 相关参数

步骤2：RTS 算法框架

步骤2.1：生成候选解，找出当前最优解；

步骤2.2：把当前最优解存入Hash 表，判断是否重复，若重复，转步骤2.3，反之转步骤2.5；

步骤2.3：解重复次数chaotic=chaotic+1，若chaotic＞混沌标志数chaos，转步骤3，反之转2.4；

步骤2.4：判断重复间隔R 是否超过预设值Rave，若R＜Rave，禁忌长度，L=1.1*L，Rave=0.1*R+0.9*Rave，反之转步骤4；

步骤2.5：判断当前时间距离上次禁忌长度发生改变的时间tT 是否超过预设值GapMax，若tT＞GapMax，L=0.9*L，转步骤4，反之转步骤4。

步骤3：逃离机制

跳出当前搜索区域，重新生成初始解进行搜索。

步骤4：算法终止

达到预先设定最大迭代步数，算法终止。

2.5 ITS 算法流程

下面给出ITS 算法的具体流程。

步骤1 初始化

输入各改进策略的算法参数；设置算法终止条件：迭代代数达到最大迭代数Nmax或者达到允许最优解未改进的最大次数Emax；设迭代计数器t=0，最好解未改进次数t1=0；采用改进RCRS 算法生成初始解S，并把该解置为Sbest和Snow，计算初始解的适应度值F（S ）；当前候选解数目n=0，最大候选解数目为nmax，候选集为C。

步骤2 生成候选解

从三种邻域变换中随机选取一种作用于当前解Snow生成候选解S'，将S'置入候选集C 中，n=n+1；若n＞nmax，转步骤3，反之转步骤2。

步骤3 候选解排序

采用WTS 算法对C 集合中的候选解进行解码计算，选出当前最优解S*，记录其适应度值F （S*）。

步骤4 调整禁忌长度

将F （S*）代入RTS 算法，动态调整禁忌长度L。

步骤5 更新统计信息

若F （S*）＞=F （Sbest），则t1=t1+1；否则Sbest=S*，t1=0，Snow=S*。

步骤6 更新禁忌表

将当前解S*的禁忌对象放入禁忌表中。

步骤7 算法终止

若t＞Nmax或t1＞Emax，算法终止输出最优解Sbest，否则转步骤2。

3 算例实验与分析

3.1 测试环境与测试数据

实验环境如下：Intel（R） Core（TM） i7-8550U CPU，8GB RAM，操作系统为Window 10，编程环境为C#。

Wang 等[14]提出的测试算例已成为求解VRPSPDTW 问题的国际通用算例，本文亦选取该算例进行实验。为避免偶然性，每个算例独立运行20 次，取其中的最优值作为实验结果。

3.2 实验一

为验证改进策略对TS 算法性能的提升，选取9 个小规模算例进行实验，将结果与标准TS 算法进行比较。实验对比结果如表1 所示，其中，NV（Number of Vehicle） 表示所需要的车辆数；TD（Travel Distance） 表示总运输距离；Gap 表示2 个算法的差距，其中TD%= （改进TS-标准TS ）/改进TS。观察发现，9 组测试算例中，改进TS 在NV 目标值上有2 组优于标准TS，而对于TD 目标值，改进效果明显，共有6 组有较大改进，最大改进率为3.06%。

表1 小规模客户改进TS 与标准TS 实验结果对比

为了进一步研究ITS 和TS 的算法的收敛性能，选取RCdp5001 算例，其最优结果的迭代过程如图1 所示，x 轴表示算法迭代次数，y 轴表示目标函数TD 值。由图1 中可以看出，RCRS 算法保证ITS 算法比TS 算法随机生成的初始解更优，更有利于接下来的搜索，RTS 算法动态调整禁忌长度，提高跳出局部最优的可能性，ITS 算法可以更快的跳出局部最优。

3.3 实验二

为进一步测试ITS 算法的有效性，选取9 个小规模算例和10 个大规模算例进行实验，将实验结果与Wang 等[14]设计的遗传算法（Genetic Algorithm，GA）、Wang 等[16]设计的并行模拟退火算法（parallel-Simulated Annealing，p-SA）、王超等[17]设计的离散布谷鸟算法（Discrete Cuckoo Search，DCS） 取得的最优实验结果进行比较，对比结果如表2 所示。

观察结果得出，9 组小规模算例中，1 组算例更新了最优解，7 组算例达到最优解，1 组算例略差于最优解。对于10 组大规模算例，4 组算例更新了最优解，最大改进率为8.40%，2 组算例达到最优解，1 组算例NV 多1 辆，但TD 改进0.51%，剩余3 组算例结果略差于最优解。通过实验可以看出，改进禁忌搜索算法加入RCRS 算法和RTS 算法后，能更有效地跳出局部最优进行搜索，加快寻优速度，验证了改进策略的有效性。

4 结束语

本文研究了带时间窗的同时取送货车辆路径问题，以车辆的固定成本、运输成本、车辆超时的时间窗成本、货物的货损成本、保鲜的制冷成本以及考虑环保的碳排放成本之和为目标构建了配送模型。基于标准TS 的框架，采用RCRS 插入算法生成初始解，进行邻域搜索时，应用WTS 算法进行路径划分，减少了可行解的验证时间，RTS 算法动态调整禁忌长度，提高搜索的效率，通过与标准算例的对比，结果表明ITS 算法在求解该问题上能得到可接受的可行解。

本文没有考虑车辆行驶速度带来的影响，后续研究中将考虑速度随时间而变化，即解决时间依赖性带时间窗的同时取送货问题（TDVRPSPDTW），对速度可变情况下车辆调度进行规划，来寻得最优调度。

图1 改进TS 与标准TS 进化过程比较

表2 比较GA、p-SA、DCS 和ITS 算法的结果