硬时间窗VRP的混合变邻域禁忌搜索算法_贺琪.pdf

Computer Engineering and Applications计算机工程与应用2023，59（13）车辆路径问题（vehicle routing problem，VRP）是一个基本的离散组合优化问题，也是交通运输和运筹学领域研究最广泛的问题之一1。随着物流业的快速发展，依据现实具体要求，经典VRP已经衍生出多种变体2。带时间窗约束的VRP（VRP with time windows，VRPTW）3是经典VRP的重要变体之一，除了要满足经典VRP的限制之外，还必须要满足客户点的时间窗约束，大致可分为带硬时间窗的 VRP（VRP with hard timewindows，VRPHTW）和带软时间窗的 VRP 两种2-3：硬时间窗要求车辆必须在时间窗内开始为客户服务，车辆硬时间窗VRP的混合变邻域禁忌搜索算法贺琪，官礼和，崔焕焕重庆交通大学 数学与统计学院，重庆 400074摘要：为了寻求带硬时间窗的车辆路径优化问题的高质量近似解，针对现有数学模型对时间窗约束考虑不充分，建立了最小化车辆数和总行驶距离的双目标非线性优化模型，提出了一种混合变邻域禁忌搜索求解算法。一方面，采用改进的节约算法生成初始解，设计了3种删除算子和一种插入算子对初始解进行扰动优化，为后续禁忌搜索提供优良的初始解；另一方面，基于4种邻域构造算子进行禁忌迭代搜索，利用禁忌搜索的灵活存储结构、避免迂回搜索的禁忌准则和增强多样性搜索的特赦准则有效摆脱局部最优解，最终实现全局优化。在56个Solomon和18个Homberger基准算例上的实验结果表明，该算法的求解质量优于文献中两种同类型搜索算法，具有良好的收敛性和稳定性，且在42个基准实例上获得了比当前已知最好解更低的车辆总行驶距离。关键词：车辆路径优化；时间窗；禁忌搜索；变邻域搜索文献标志码：A中图分类号：TP301.6doi：10.3778/j.issn.1002-8331.2208-0431Hybrid Variable Neighborhood Tabu Search Algorithm for Vehicle Routing Problem with HardTime WindowHE Qi,GUAN Lihe,CUI HuanhuanSchool of Mathematics and Statistics,Chongqing Jiaotong University,Chongqing 400074,ChinaAbstract：To find a high-quality approximate solution to the vehicle routing optimization problem with hard timewindow,a dual objective nonlinear optimization model is established to minimize the number of vehicles and the totaldriving distance,because the insufficient consideration of time window constraints in the existing mathematical models,and a hybrid variable neighborhood tabu search algorithm is proposed to solve it.On the one hand,an improved savingalgorithm is used to generate the initial solution.And three deletion operations and one insertion operation are designed tooptimize the number of vehicles in the initial solution,so as to provide an excellent initial solution for the subsequent tabusearch.On the other hand,four neighborhood construction operators are designed in the tabu search process.The flexiblestorage structure,tabu criterion for avoiding repeated searches and amnesty criterion for enhancing diversity search caneffectively get rid of local optimal solution,and finally achieve global optimization.Finally,the experimental analysis iscarried out on 56 benchmark examples of Solomon and 18 benchmark examples of Homberger.This algorithm has goodconvergence and stability,and its solutions are better than the two similar search algorithms in the literature.Moreover,the total driving distance is lower than the currently known best solution on 42 examples.Key words：vehicle routing optimization;time window;tabu search;variable domain search基金项目：国家自然科学基金（12271067）；重庆市高校创新研究群体项目（CXQT21021）；重庆市研究生联合培养基地建设项目（JDLHPYJD2021016）。作者简介：贺琪（1997），女，硕士研究生，主要研究方向为智能优化计算，E-mail：；官礼和（1975），男，博士，副教授，主要研究方向为智能信息处理、机器学习；崔焕焕（1998），女，硕士研究生，主要研究方向为智能优化计算。收稿日期：2022-08-29修回日期：2022-11-25文章编号：1002-8331（2023）13-0082-10822023，59（13）早到须等待，而晚到则将被拒绝；软时间窗不必在时间窗内开始为客户服务，但在时间窗外开始服务须受到惩罚。显然，软时间窗与硬时间窗的最大区别是用惩罚代替等待和拒绝。因此，VRPHTW的求解方法很容易被转换用于求解带软时间窗的VRP。VRP及其复杂的变体已被证明是 NP-hard问题4，因此求解VRPHTW是一项极具挑战性的工作。文献中已有VRPHTW数学模型，其优化目标通常是最小化总行驶距离5-8、最小化车辆数5，8和最小总成本9。在模型约束方面存在对时间窗约束的考虑不充分和缺乏消除子回路的约束的问题，尚需进一步改进，如表1所示5-9。另一方面，从求解VRP数学模型的方法来看，大致可分为：精确算法、启发式算法和机器学习方法。精确算法的计算时间随问题规模的扩大呈指数增长，仅适合求解小规模问题，对较大规模的问题启发式算法是一种不错的选择。目前，启发式算法主要有变邻域搜索10-11、大邻域搜索8、模拟退火12、禁忌搜索13等，组合多种智能优化算法14求解复杂的VRPHTW及其变体是当前的一个研究热点。此外，利用机器学习方法来求解 VRP及其变体是近年来的另一个研究热点，它克服了精确算法和启发式算法参数调整繁琐的缺点，利用离线训练的优势快速解决在线实例问题15-16。然而，机器学习方法还存在一些技术瓶颈有待解决，如训练数据的限制、通用性的限制等。因此，针对较大规模的VRPHTW及其变体，结合多种智能搜索算法设计高效的混合启发式搜索算法仍是一个值得研究的问题。禁忌搜索17和变邻域搜索18是两种不同的局部搜索算法，均已成功运用于求解VRP及其变体19-20。禁忌搜索以其灵活的存储结构、避免迂回搜索的禁忌准则和增强多样性搜索的特赦准则能有效摆脱局部最优解，搜索空间和有效邻域结构的选择是其关键，同时存在对初始解的依赖性较强和多样性搜索不足的缺陷20。变邻域搜索利用不同的邻域结构进行交替搜索，在集中性和疏散性之间达到很好的平衡，且这种系统地改变当前解的邻域结构能有效拓展解的搜索范围，但存在搜索效率低下、收敛速度慢的问题21。为此，最近已经有学者将禁忌搜索和变邻域搜索进行结合设计混合元启发式算法。如，Paul等22针对多车场多时段的 VRPHTW 变体提出了一种结合禁忌搜索和变邻域搜索的混合元启发式算法，并通过数值实验验证了其有效性。Sadati等23人针对多车场的 VRP 变体提出一种可变禁忌邻域搜索算法，通过改进的节约算法生成初始解，定义了7种邻域算子进行禁忌扰动，并对不可行解放大解空间，取得了较好的结果。Zhou 等24针对同时收发货的两级VRPHTW变体，实现了一种具有定制解表示的可变邻域禁忌搜索算法来求解大规模实例。为了寻求VRPHTW的高质量近似解，建立了最小化车辆数和总行驶距离的双目标非线性优化模型，改进了文献5-9中所建数学模型对时间窗约束考虑不充分的问题，并提出了一种混合变邻域禁忌搜索的元启发式求解算法。首先，采用改进的节约算法25生成初始解；然后，设计了3种删除算子和1种插入算子对初始解的车辆数进行扰动优化，为后续禁忌搜索提供优良的初始解；最后，基于4种邻域构造算子进行禁忌迭代搜索，进一步优化车辆数和总行驶距离。在56个Solomon26和18个Homberger27基准算例上验证了该算法的有效性。1问题描述与数学模型VRPHTW可描述为由m辆车从一个仓库出发为n位客户配送货物，每辆车完成配送任务后返回仓库，通过合理规划车辆的配送任务，使得配送车辆数或总行驶成本最小。其中，车辆有容量限制，在配送过程中不得超载；客户的地理位置信息已知，且各自有不同的需求量及接受配送服务的时间窗，要求车辆必须在客户的时间窗内对进行服务，早到则须等待，晚到则被拒绝。记V=0,1,n，其中0表示仓库，Vc=1,2,n表示客户集。K为车辆集，且车载容量均为Q。车辆从客户i行驶到客户j的距离成本和时间分别为dij表1VRPHTW相关数学模型Table 1Relevant mathematical models of VRPHTW模型文献5文献6文献7文献8文献9本文模型优化目标最小化车辆数和总行驶距离最小化总行驶距离最小化总行驶距离最小化车辆数和总行驶距离最小化总成本最小化车辆数和总行驶距离时间窗约束考虑了车辆k到在达客户i时的等待服务时间和相继访问两个客户i和j的到达时间关系，但未对车辆k是否服务客户i进行刻画，缺乏消除子回路的约束没有考虑车辆k到达客户i时的等待服务时间，缺乏车辆相继访问两个客户i和j的到达时间关系和消除子回路的约束考虑了消除子回路约束，但没有考虑车辆k到达客户i时的等待服务时间，缺乏车辆相继访问两个客户i和j的到达时间关系的约束没有考虑车辆k到达客户i时的等待服务时间，缺乏消除子回路的约束考虑了车辆k到在达客户i时的等待服务时间和车辆相继访问两个客户i和j的到达时间关系，但未对车辆k是否服务客户i进行刻画，缺乏消除子回路的约束考虑了车辆k到在达客户i时的等待服务时间，对车辆k是否服务客户i进行了刻画，加强了车辆相继访问两个客户i和j的到达时间关系和消除子回路的约束贺琪，等：硬时间窗VRP的混合变邻域禁忌搜索算法83Computer Engineering and Applications计算机工程与应用2023，59（13）和tij。客户i的需求量为qi，所需服务时间si，服务时间窗ei,li。车辆k到达客户i的时间为AT(k)i，等待时间为WT(k)i。若车辆k由客户i行驶到客户j，且相继对两个客户进行服务，则x(k)ij=1，否则x(k)ij=0。由此，构建VRPHTW的数学模型如下所示。目标函数：min Z1=jVckKx(k)0jmin Z2=iVjV/ikKdijx(k)ij约束条件：kKiV/jx(k)ij=1,jVc（1）kKjV/ix(k)ij=1,iVc（2）iVcx(k)i0=jVcx(k)0j=1,kK（3）iVqi(jV/ix(k)ij)Q,kK（4）iSjS/ix(k)ij|S|-1,SV,|S|2,kK（5）eijV/ix(k)ij(AT(k)i+WT(k)i)jV/ix(k)ijlijV/ix(k)ij,iV,kK（6）WT(k)i=max0,(ei-AT(k)i)jV/ix(k)ij,iVc,kK（7）kKjV/i(AT(k)i+WT(k)i+si+tij-AT(k)j)x(k)ij=0,iVc（8）x(k)ij0,1,AT(k)i0,i,jV,ij,kK（9）上述模型中，Z1表示从仓库出发对客户进行服务的车辆总数，Z2表示所有车辆的总行驶距离。约束条件中，式（1）和式（2）分别表示到达每个客户的车辆只有一辆和从每个客户出发的车辆只有一辆，即表示对每个客户有且仅有一辆车对其服务；式（3）表示每一辆车进出仓库均为1次；式（4）表示每辆车所访问客户的需求量总和不超过车载容量；式（5）表示不存在两个客户重复访问，用于消除子回路；式（6）表示若存在车辆对客户进行服务，则开始服务时间要在其时间窗内，即时间窗约束；式（7）表示车辆到达待服务客户的等待时间；式（8）表示车辆对相继服务两个客户的到达时间关系约束；式（9）对决策变量到达时间和等待时间进行了非负约束。2混合变邻域禁忌搜索求解算法变邻域搜索通过在当前解的多个邻域中进行局部搜索，能增强算法的搜索空间，但在使用搜索算子时盲目地将每种算子形成的邻域结构都搜索一遍，缺少启发式信息的指导。而禁忌搜索通过设置禁忌表避免迂回搜索，通过特赦准则增强多样性搜索，从而能有效摆脱局部最优解，具有简单、快速、准确的优点。为此，针对上述双目标的VRPHTW数学模型，结合变邻域搜索和禁忌搜索提出一种混合变邻域禁忌搜索求解算法。该算法分为三个阶段：第一阶段，采用节约算法构造初始解；第二阶段，设计了三种删除算子和一种插入算子对初始解的车辆数进行扰动优化，为后续禁忌搜索提供优良的初始解；第三阶段，基于设计的四种邻域构造算子进行禁忌迭代搜索，进一步优化车辆数和总行驶距离。2.1初始解的构造变邻域搜索和禁忌搜索本质上都是邻域搜索，对初始解有较强的依赖性21。因此，对本文提出的混合变邻域禁忌搜索求解算法，好的初始解有助其加快收敛速度和提高解的质量。节约算法具有原理简单且易实现的优点，已广泛用于VRP及其变体的启发式算法中产生初始解。经典节约算法在计算线路节约值时，仅考虑了将带插入客户插入到仓库前或者后两种与仓库相邻的位置，既没有考虑插入的可行性也没有考虑其他插入位置，即并非是可行的最优插入，这必将影响产生初始解的质量。为此，本文将其修改为最优可行插入，即考虑了所有可行插入位置，以此计算并比较不同插入位置的节约值。首先，构造n条仅包含仓库和单个客户的初始路径集R*；然后，通过计算R*中每条单个客户路径并入其余路径的最优插入位置及其插入节约值，选出合并后为可行路径且具有最大节约值的两条路径进行合并，同时更新R*，直到R*中没有仅包含单个客户的路径为止。下面给出最优插入位置、节约值计算和可行路径的定义。定义1 考虑将仅包含单个客户的路径rj=0,j,0合并到路径ri=0,i1,ip,0中，此时rj中的客户j在ri中共有p+1个插入候选位置，最优插入位置为l?ij=argmax1lijp+1save(ri,rj,lij)，其中节约值计算公式为：save(ri,rj,lij)=|d0,i1+d0,j-di1,j,lij=1d0,ip+d0,j-dip,j,lij=p+1dil-1,il+2d0,j-dil-1,j-dil,j,1lijmaxei,ej0,esle。事实上，在执行可行最优贪婪插入操作时，可利用Solomon26提出的前推值插入检测法对可行插入位置进行快速检测，从而提高运算效率。对当前解R采用上述任何一种删除算子后，特别是前两种车辆路径删除算子，R中的车辆路径数只可能减少，从而不断优化车辆总数。对初始解进行扰动优化的具体描述如算法2所示。算法2 初始解的扰动优化输入：初始解R0，扰动次数p，相关性删除客户数。输出：扰动优化后的新解R1。1.记扰动次数t=1；2.随机选择一种删除操作k1,2,3，对当前解R0进行扰动，更新R0和扰动次数t=t+1；3.若扰动次数t未达到上限p，则返回步骤2，否则返回新解R1=R0。2.3禁忌搜索经过对初始解R0的扰动搜索后得到新解R1，新解R1相对于初始解R0的车辆总数得到较大的改善。接下来，采用禁忌搜索方法进一步优化车辆的总行驶距离。禁忌搜索中邻域结构的设计是关键，它决定了当前解的邻域解产生形式和数目，而禁忌表和禁忌对象的设计能避免迂回搜索，有利于跳出局部最优解，实现全局优化。为了增强算法搜索的多样性，禁忌搜索采用的四邻域构造算子及其禁忌表设置如下所示。Relocation 算子NS1：从解R1中选择路径ri=0,i1,ip,0，再从ri上选择客户ik，令ilri，将客户ik插入到客户il之前，得到新路径r*i=,ik-1,ik+1,il-1,ik,il,，距离增量1=dik,il+dil-1,ik+dik-1,ik+1-dik-1,ik-dik,ik+1-dil-1,il。该算子的候选解集CS1=(ri,ri,ik,il,1)|ilri且r*i为可行路径，其禁忌表TL1的禁忌对象为随机选择的路径ri和客户ik，即(ri,ik)。Move算子NS2：从解R1中选择路径ri=0,i1,ip,0和rj=0,j1,jq,0，从ri上选择客户ik，令jlrj，将ik插入到jl之前，得到两条新路径r*i=,ik-1,ik+1,和r*i=,jl-1,jk,jl,，距离增量2=dik-1,ik+1+djl-1,ik+dik,jl-dik-1,ik-dik,ik+1-djl-1,jl。该算子的候选解集CS2=(ri,rj,ik,jl,2)|jlrj且r*i和r*j均为可行路径，其禁忌表TL2的禁忌对象为随机选择的路径ri、rj和客户ik，即(ri,rj,ik)。Cross Exchange算子NS3：从解R1中选择路径ri=0,i1,ip,0和rj=0,j1,jq,0，从ri上选择不包含仓库中心的子路径ik1,ik2，令jl1,jl2为rj上不包含仓库中心的子路径，将ik1,ik2与jl1,jl2互换，得到两条新路径r*i=,ik1-1,jl1,jl2,ik2+1,和r*j=,jl1-1,ik1,ik2,jl2+1,，距离增量3=dik1-1,jl1+djl2,ik2+1+djl1-1,ik1+dik2,jl2+1-dik1-1,ik1-dik2,ik2+1-djl1-1,jl1-djl2,jl2+1。该算贺琪，等：硬时间窗VRP的混合变邻域禁忌搜索算法85Computer Engineering and Applications计算机工程与应用2023，59（13）子的候选解集CS3=(ri,rj,ik1,ik2,jl1,jl2,3)|jl1,jl2rj且r*i和r*j均为可行路径，其禁忌表TL3的禁忌对象为随机选择的路径ri、rj，以及客户ik1、ik2，即(ri,rj,ik1,ik2)。2-opt*算子NS4：从解R1中选择路径ri=0,i1,ip,0和rj=0,j1,jq,0，从ri上选择客户ik，令jlrj，将ri和rj的前、后半段交叉相连，得到两条新路径r*i=0,i1,ik,jl+1,jq,0和r*j=0,j1,jl,ik+1,ip,0，距离增量4=dik,jl+1+djl,ik+1-dik,ik+1-djl,jl+1。该算子的候选解集CS4=ri,rj,ik,jl,4)|jlrj且r*i和r*j均为可行路径，其禁忌表TL4的禁忌对象为随机选择的路径ri，rj和及客户ik，即(ri,rj,ik)。上述4种邻域构造算子中，路径和客户的选择均采用随机选择策略。每种邻域构造算子对应禁忌表中禁忌长度设为常数L，禁忌特赦准则是禁忌对象对应解优于当前最优解，禁忌条件在禁忌长度变为零或满足特赦准则时撤销。禁忌搜索的具体描述如算法3所示。算法3 禁忌搜索输入：最优解R*，当前解R1，邻域构造算子NSi，禁忌表TLi，禁忌长度L。输出：新的最优解R*和当前解R1。1.利用邻域搜索算子NSi，构造当前解R1的候选解集CSi。2.从候选解集CSi中找出距离增量最小的解R*1。3.判断候选最优解R*1是否满足特赦准则：若R*1对应的对象在禁忌表TLi中且R*1的车辆总行驶距离比最优解R*小，即满足特赦准则，则更新最优解R*=R*1和当前解R*=R*1，并将R*1相应的对象重新加入禁忌表TLi，同时将TLi中其他对象禁忌次数减一；否则从候选解集CSi中选择非禁忌对象对应的最优解R*1作为当前解，即R1=R*1，同时将R*1相应的对象加入禁忌表TLi，将其他对象禁忌次数减一。4.返回新的最优解R*和当前解R1。2.4混合变邻域禁忌搜索算法描述首先，根据改进的节约算法构造初始解，接着对初始解进行扰动优化，然后对扰动优化后的解进行禁忌搜索迭代计算。在每次迭代计算中，先进行相关性删除和可行最优贪婪插入扰动，再随机选择一种邻域构造算子进行禁忌搜索，直到达到最大迭代次数为止。具体描述如算法4所示。算法4 混合变邻域禁忌搜索算法（HVNS-TS）输入：数据集，扰动次数p，相关性删除算子参数，最大迭代次数itmax，禁忌次数L。输出：最优解R*。1.调用算法1构造初始解R0；2.依据扰动次数p，调用算法2对初始解R0进行扰动，得到进一步优化的解R1；3.令it=1，禁忌表TLi为空(i=1,2,3,4)，且最优解R*=R1；4.依据相关性删除操作参数，对当前解R1进行相关性删除操作3和可行最优贪婪插入扰动得新的当前解R1。若R1的车辆总行驶距离比最优解R*小，则更新最优解R*=R1；5.随机选择邻域构造算子NSiNS1,NS2,NS3,NS4，调用算法3对当前解R1进行禁忌邻域搜，返回更新后的最优解R*和当前解R1；6.令it=it+1，且若ititmax，则转步骤4，否则输出解最优解R*，算法结束。3实验结果与分析为了验证本文方法的有效性，将HVNS-TS算法与文献中两种同类邻域搜索算法：禁忌搜索启发式算法（TS）19和大邻域搜索算法（LNS）10进行对比实验。算法采用MATLAB R2016a编程，在IntelCore i5-10210UCPU1.6 GHz RAM8G Win10环境下运行。实验数据采用 VRPTW 的 56 个 Solomon 和 18 个 Homberger标准算例（https：/www.sintef.no/projectweb/top/vrptw/），Solo-mon算例包含C1、R1、RC1、C2、R2和RC2共6类算例，每个算例均只有1个仓库，C类、R类和RC类客户地理位置分别为聚类分布、随机分布以及随机与聚类的混合分布；C1、R1、RC1类的车辆容量均为200，且其算例的时间窗比C2、R2、RC2的紧，C2类的车辆容量为700，R2、RC2类的车容量为1 000，从而在R1、C1、RC1类算例中每条路径上能服务的客户数相对R2、C2和RC2要少。每个 Solomon 算例均包含 100 个客户，而采用的 Hom-berger算例是将Solomon算例客户数扩展到200个。3.1实验结果对比分析经过多次测试，得到算法参数的大致范围为：最大迭代次数itmax=100500，扰动次数p=30100，相关性删除算子参数=n m（n为算例中客户点数，m为车辆数），禁忌次数L=518。一般地，客户点规模n越大，参数itmax、p、L的设置也相应大一些，而参数则根据算例规模与车辆数的比值进行调整，约为每条路径客户平均数。在 Solomon 算例实验中，itmax=300，p=100，L=10，在Homberger算例实验中，itmax=500，p=100，L=15。实验时，每个算法对每个算例均进行 10 次求解。实验结果如表24所示，其中：M*和D*分别表示当前已知算例最好解中的车辆数和总行驶距离，BM和BD分别表示算法10次求解的最优车辆数和总行驶距离，AD表示算法10次求解的平均总行驶距离，算法最优总行驶距离的相对误差为Ber=(BD-D*)/D*100%，平均总行驶距离的相对误差Aer=(AD-D*)/D*100%。862023，59（13）从表24可以看出如下几点：（1）从解的车辆数看，在 56 个 Solomon 算例中，HVNS-TS在除R103和RC207之外的54个算例上获得相对TS和LNS较少的车辆数，而LNS在49个算例上获得了同样较少的车辆数，TS仅在算例C106上获得较少的车辆数。此外，相对于56个算例的当前已知最好解，HVNS-TS在17个C类算例上均获得与当前已知最好解相同的车辆数。在 18个 Homberger算例中，HVNS-TS在除R223以外的17个算例上获得相对TS和LNS较少的车辆数。此外，相对于当前已知最好解，HVNS-TS在9个算例上均取得更少的车辆数。（2）从解的车辆总行驶距离看，结果最好的是HVNS-TS，其次是LNS，最差的是TS。在56个Solomon算例中，HVNS-TS在48个算例上获得了相对较好的结果，LNS在21个算例上获得相对较好的结果，而TS在所有算例上均未获得相对较好的结果。此外，相对于56个算例的当前已知最好解，HVNS-TS在17个C类算例中的11个算例上获得与当前已知最好解相同的车辆总算例（M*，D*）C101（10，828.94）C102（10，828.94）C103（10，828.06）C104（10，824.78）C105（10，828.94）C106（10，828.94）C107（10，828.94）C108（10，828.94）C109（10，828.94）R101（19，1 645.79）R102（17，1 486.12）R103（13，1 292.68）R104（9，1 007.24）R105（14，1 377.11）R106（12，1 251.98）R107（10，1 104.66）R108（9，960.88）R109（11，1 194.73）R110（10，1 118.59）R111（10，1 096.72）R112（9，982.14）RC101（14，1 696.94）RC102（12，1 554.75）RC103（11，1 261.67）RC104（10，1 135.48）RC105（13，1 629.44）RC106（11，1 424.73）RC107（11，1 230.48）RC108（10，1 139.82）误差均值误差方差TS9BM1111151511101212122921181422191614171514132221171420171613BD867.57871.701 199.301 230.37867.57839.67923.17923.17971.871 951.401 718.701 395.991 221.301 604.821 534.431 283.601 138.781 431.791 335.571 308.401 122.162 144.711 891.991 781.751 560.901 838.421 608.421 474.921 292.99Ber4.665.1644.8349.184.661.2911.3711.3717.2418.5715.657.9921.2516.5422.5616.2018.5119.8419.4019.3014.2626.3921.6941.2237.4712.8312.8919.8713.4418.81135.87AD867.57871.701 199.301 230.37867.57839.67923.17988.13971.871 951.401 718.701 395.991 221.301 604.821 534.431 283.601 138.781 431.791 335.571 308.401 122.162 144.711 891.991 781.751 560.901 838.421 608.421 474.921 292.99Aer4.665.1644.8349.184.661.2911.3719.2017.2418.5715.657.9921.2516.5422.5616.2018.5119.8419.4019.3014.2626.3921.6941.2237.4712.8312.8919.8713.4419.08133.82LNS8BM1010101010101010101918141515131210131211101514121115141413BD828.94828.94864.55862.98844.46828.94828.94828.94854.781 662.001 482.471 247.981 022.211 421.521 267.901 129.33987.211 265.711 154.571 105.791 019.451 672.111 511.851 357.631 186.091 558.951 442.261 347.951 259.59Ber004.414.631.870003.120.980.253.461.493.221.272.232.745.943.220.833.801.462.767.614.464.331.239.559.612.0711.50AD828.94833.45883.78892.94918.20828.94863.68857.00880.261 676.681 492.701 261.531 050.981 462.201 295.011 143.691 001.151 271.111 182.471 134.671 032.911 734.991 542.511 384.031 202.411 592.741 508.381 387.251 260.69Aer00.546.738.2610.7704.193.396.191.880.442.414.346.183.443.534.196.395.713.465.172.240.799.705.892.255.8712.7410.6019.08133.82HVNSTSBM1010101010101010101918151115131210131211101614121015141211BD828.94828.94828.94846.78828.94828.94828.94828.94854.781 656.501 477.701 247.701 017.501 416.701 269.301 118.70984.911 203.701 163.901 094.309 97.191 687.301 505.901 334.401 153.801 564.801 485.001 188.301 200.20Ber000.112.6700003.120.650.573.481.022.871.381.272.500.754.050.221.530.573.145.761.613.974.233.435.300.816.02AD828.94828.94846.38858.19832.41828.94838.22845.72854.951 668.261 488.861 253.341 041.471 439.151 298.131 132.55995.281 248.761 185.951 118.611 032.871 718.631 532.611 359.721 194.241 590.971 515.821 342.791 219.69Aer002.214.050.4201.122.023.141.370.183.043.404.513.692.523.584.526.022.005.171.281.427.775.172.366.399.137.012.758.92表2R1、C1、RC1类算例实验对比结果（Solomon）Table 2Comparative results of R1，C1 and RC1 study cases（Solomon）注：表中黑体数据表示算法获得的最好解。贺琪，等：硬时间窗VRP的混合变邻域禁忌搜索算法87Computer Engineering and Applications计算机工程与应用2023，59（13）算例（M*，D*）C201（3，591.56）C202（3，591.56）C203（3，591.17）C204（3，590.60）C205（3，588.88）C206（3，588.49）C207（3，588.29）C208（3，588.32）R201（4，1 252.37）R202（3，1 191.7）R203（3，939.54）R204（2，825.52）R205（3，994.42）R206（3，906.14）R207（2，893.33）R208（2，726.75）R209（3，909.16）R210（3，939.34）R211（2，892.71）RC201（4，1 406.91）RC202（3，1 367.09）RC203（3，1 049.62）RC204（3，798.41）RC205（4，1 297.19）RC206（3，1 146.32）RC207（3，1 061.14）RC208（3，828.14）误差均值误差方差TS9BM991011910101021161111141312101214102015141116151411BD932.39889.70997.631 054.02933.52954.80946.66958.931 547.761 357.401 213.23978.081 204.161 173.681 071.88979.601 111.471 159.94990.431 845.251 529.731 409.241 149.271 615.251 563.881 440.021 112.42Ber57.6250.4068.7678.4758.5262.2560.9262.9923.5913.9029.1318.4821.0929.5319.9934.7922.2523.4810.9531.1611.9034.2643.9424.5236.4335.7034.3337.01360.24AD932.39889.70997.631 054.02933.52954.80946.66958.931 547.761 357.401 213.231 120.521 204.161 173.681 071.88979.601 111.471 159.94990.431 845.251 529.731 409.241 149.271 615.251 563.881 440.021 112.42Aer57.6250.4068.7678.4758.5262.2560.9262.9923.5913.9029.1335.7421.0929.5319.9934.7922.2523.4810.9531.1611.9034.2643.9424.5236.4335.7034.3337.65346.67LNS8BM333333336654675456476547655BD591.5