带软时间窗随机需求车辆路径问题的算法研究
2021-09-13李国明李军华
李国明，李军华
(南昌航空大学 江西省图像处理与模式识别重点实验室，江西 南昌 330063)
0 引言
物流配送线路规划问题(logistics distribution route planning problem)是目前大型物流配送管理中的核心问题之一，通常归结为车辆路径问题(Vehicle Routing Problem, VRP)。该问题指配送中心根据客户需求安排车辆对货物进行派发，车辆从配送中心出发，到达指定地点，最后回到配送中心，其中需要考虑车辆的时间约束、容量约束等约束条件。因为研究VRP能有效处理运输过程中订单分配不合理、运输延误率高等情况，所以该问题自提出以来就受到国内外众多学者的广泛关注，并提出基于VRP的精确算法[1-3]和基于VRP的启发式算法[4-7]。VRP主要有3个不同的研究角度：
(1)带时间窗的车辆路径问题
在实际配送中，客户会对货物送达时间区间提出严格要求。针对此类问题，XU等[8]提出混合遗传算法和粒子群优化(Particle Swarm Optimization, PSO)算法，利用粒子实数编码方法对路径进行解码来减轻计算负担，同时与遗传算法的交叉算子相结合，避免陷入局部最优。NIU等[9]提出基于膜计算(membrane computing)的混合进化算法，将遗传算法中常用的二进制编码改进为整数编码，既可避免编码冗余问题，又可提高算法的实用性和计算效率。该方法在单次配送VRP中效果较好，但未考虑多个配送中心同时配送的情景。戚远航等[10]提出一种离散蝙蝠算法(Discrete Bat Algorithm,DBA)，利用DBA寻优能力强、鲁棒性好等特性来解决带时间窗的VRP，然而该算法未考虑客户需求的随机性。
(2)随机需求车辆路径问题
在实际配送中，若设定客户需求为随机变量，则称为随机需求车辆路径问题(Vehicle Routing Problem with Stochastic Demand,VRPSD)。为了解决这一问题，GUTIERREZ等[11]设计了一种混合元启发式算法，该算法结合了文化基因算法和贪婪随机算法，通过与现有的元启发式方法比较，验证了该方法的有效性；李阳等[12]根据先预优化后重调度的思想，提出两阶段混合变邻域分散搜索(Variable Neighborhood Scatter Search, VNSS)算法，该算法求解稳定且平均误差小，但求解大规模问题的能力较差，耗时较长。
(3)带时间窗的随机需求车辆路径问题
在实际配送中，若设定客户需求为随机变量，且客户对货物送达时间区间提出要求，则称为带时间窗的随机需求车辆路径问题(Vehicle Routing Problem with Stochastic Demand and Time Window, VRPSD-TW)，目前求解VRPSD-TW问题均采用两阶段带修正随机规划模型。第一阶段，制定一组预计送货路线；第二阶段，显示客户实际需求，采用修正算法对第一阶段所得解进行修正。修正算法主要包括两种：①车辆到达指定地点A后，直接回到配送中心重新对B点进行货物派送；②车辆到达B点后，才发现剩余容量不足，需要回配送中心重新装载货物。显然，情况②下的成本更大。
近年来，由于快递物流业飞速发展，带软时间窗的随机需求车辆路径问题(Vehicle Routing Problem with Stochastic Demand and Soft Time Window, VRPSD-STW)更符合实际。针对此类问题中的客户需求是随机的，LEI等[13]提出DTD(detour-to-depot)修正算法，即只有当车辆剩余容量为零时，车辆才会回配送点重新装载货物，否则继续为下一客户提供服务。该方法忽略了下一个客户的实际需求，导致车辆必须回配送中心重新装载货物，造成巨额成本。ZHANG等[14]提出一种预防性补货思想，即根据公式预先设定一个阈值，当车辆服务完一个客户后，如果剩余容量小于或等于该阈值，则回配送中心重新装载货物，然后为下一客户提供服务，否则直接为下一客户提供服务。文献[15-16]对预防性补货策略进行了进一步改进，文献[15]提出当车辆服务完当前客户后，若其剩余容量低于路线上下一个客户预期需求的η倍时(η通常取1)，则回到配送中心重新装载货物，否则继续为下一个客户提供服务，该策略进一步降低了修正成本；文献[16]提出一种混合算法，设定最大行进阈值和最小补货阈值，根据公式得出风险确定值，若该值大于最小补货阈值，则回配送中心重新装载货物，否则继续对下一个客户服务。本文在ZHANG等[14]提出的模型上进行扩展，在第一阶段制定车辆预计送货路线时便加入了软时间窗约束，并令客户需求服从离散均匀分布。
上述文献中，针对小规模随机需求车辆问题的求解效果较好，大规模随机需求车辆问题的求解过程则十分复杂，而且效果不是很好。目前，求解VRPSD-STW的启发式算法[4-7]较少，该类算法可以解决大规模VRP，且运算速度较快。
基于上述分析，本文主要研究VRPSD-STW，针对求解时间较长、客户需求随机且车辆行驶路径修正成本较大的问题，提出一种二阶段算法。第一阶段将客户的随机需求作确定化处理，使其等于期望值，再运用改进的禁忌搜索(Tabu Search, TS)算法进行求解；第二阶段用选择回配送中心(Select Return to Depot，SRTD)算法对第一阶段所得解进行修正，修正成本较小。
本文算法的主要创新点如下：①对第一阶段使用的TS算法[17-19]中的禁忌长度、邻域结构进行自适应调整，并引入自适应惩罚系数，不但有利于算法减少搜索最优解的时间，而且可以避免陷入局部最优。②第二阶段采用SRTD算法对第一阶段所得解修正。首先判断车辆剩余容量是否小于客户实际最大需求，是则计算车辆不考虑后续客户(i+2,i+3,…)，对客户i服务后继续对客户i+1服务所产生的成本及对客户i服务后直接回配送中心重新装载货物所产生的成本，然后将所得成本进行比较并确定阈值，最终决定车辆服务完当前客户后继续服务下一客户还是回配送中心重新装载货物。该方法提高了车辆的灵活性，极大地降低了修正成本。
1 相关工作
1.1 禁忌搜索算法
TS算法是一种现代启发式算法，由Fred Glover教授[20]于1986年提出，是一种改进的局部搜索算法。该算法在每次迭代时从当前解s∈S移动到其邻域N(s)的最优解来探索解空间，S表示满足约束条件的一组可行解。为了避免陷入局部最优，通过设置禁忌表来禁忌一些已经历的搜索过程。TS算法一般由禁忌长度、邻域结构、选择策略和特赦准则组成。
在TS算法中，邻域结构是算法有效与否的关键，目前主要的邻域结构有2-opt邻域、Relocate邻域和Swap邻域[17]。
(1)2-opt邻域 随机选取一条路径，在路径上随机选取两点Si-1和Sm-1，将Si-1到Sm-1之间的路径翻转。
(2)Relocate邻域 表示选取一条路径，在路径上随机选取一个客户，将其从目前所属的位置上移除，插入到其他任意位置。例如，将Si-1从路径上移除，插入到Si+1处；将Si从路径上移除，插入到Sm处；将Sm-1从路径上移除，插入到Si处。
(3)Swap邻域 随机选取两条路径，在每条路径上随机选取一个客户，交换其位置。例如，在路径s上选取si-1,在路径t上选取ti,交换其位置；在路径t上选取ti-1,在路径s上选取si,交换其位置；在路径s上选取si,在路径t上选取ti+1,交换其位置；在路径t上选取ti,在路径s上选取si+1,交换其位置。
图1所示为3种邻域结构的具体变换示意图。
在禁忌搜索算法中，只有当迭代次数超过最大预设值maxT或最优解连续T次不更新时，算法才停止迭代并返回最优解，具体流程如算法1所示。
算法1基本禁忌搜索算法框架。
1.随机产生初始解s，清空禁忌表
2.If s满足收敛条件
3. 将s作为当前解
4. Repeat
6. If s′在禁忌表中
7. If s′满足藐视准则
8. 将s′作为当前解
9. end
10. else
12. end if
13. 达到迭代终止条件
14. end
1.2 修正算法
修正算法(modified algorithm)主要用来解决带不确定信息的VRP，一般常用于随机VRP和动态VRP。如果配送中心对车辆行驶路径进行规划时未充分考虑不确定信息，则会导致车辆无法为规划路径上的所有客户提供服务，造成路线失败，使整个车辆配送系统瘫痪。修正算法能有效解决路线失败问题，使车辆配送系统重新运转，重新安排车辆为客户提供服务。目前，主要的修正算法如下：
(1)车辆为某客户提供服务后，其剩余容量为零，配送中心安排附近其他车辆为该路径的剩余客户提供服务。
(2)车辆为某客户提供服务后，其剩余容量为零，安排该车辆回配送中心重新装载货物，然后继续服务下一客户。
(3)车辆为某客户提供服务后，其剩余容量为零，配送中心按区域统计剩余客户，重新安排车辆分别服务不同区域的客户。
2 问题描述及数学模型
2.1 问题描述
在VRPSD-STW中，客户需求未知和每个客户都有其时间窗口的限制是两个重要的部分。
(1)需求未知 在制定行驶路线时，客户需求通常为随机变量，只知其满足某种概率分布，如正态分布、对数正态分布、离散均匀分布。因为客户的实际需求间断且不连续，所以本文采用离散均匀分布来显示客户需求。
(2)时间窗口 车辆未按设定的时间窗要求到达客户点时，虽然可以对客户进行服务，但是必须给予相应的惩罚，而且每个客户只可由一辆车服务。
如果该客户需求超过车辆剩余容量，则路线失败，车辆停止服务。此时需要采取措施进行弥补，例如在恢复送货服务前，车辆可以返回配送中心重新装载，从而增加了额外行驶时间，脱离了剩余客户原先设置的时间窗。因此，客户随机需求、时间窗的设定是影响车辆能否按时送货的一个关键问题。
2.2 建立VRPSD-STW数学模型
求解VRP首先需要综合道路网络信息。方便起见，道路网络用无向完全图G=(V0,A)表示，其中V0={0,V}为配送点与客户点之间的集合(0表示配送中心,V={1,2,…,n}表示客户点集)，A={(i,j):i,j∈V0,i≠j}为车辆在行驶过程中所经过路段的集合，该集合有3种情况：①当i=0,j∈V时，A表示车辆在配送点与客户点之间行驶所经过路段的集合；②当i,j∈V且i≠j时，A表示车辆在客户点之间行驶所经过路段的集合；③当i∈V,j=0时，A表示车辆在客户点与配送点之间行驶所经过路段的集合。C={c(i,j):i,j∈V0,i≠j}表示客户i与客户j之间的距离。假设车辆以单位速度行驶，则车辆从客户i行驶到客户j所需的时间tij等于客户i与客户j之间的距离c(i,j)，c(i,j)一般用最短路径算法[21]求解。
(1)目标函数
VRPSD-STW属于运筹学中的组合优化问题。假设有K辆车为分布在不同位置的n个客户提供服务，要求车辆在匀速行驶的情况下花费时间最少、违背约束惩罚成本和修正成本最小。因此，构建目标函数
(1)
式中：tij为车辆从客户i行驶到客户j所需的时间；xijk为决策变量，若车辆k从客户i行驶到客户j，则为1，否则为0；nk为车辆k服务的客户总数；λ1j为车辆提前到达客户j的惩罚系数；E(Wjk)表示车辆k到达客户j的期望提前时间；λ2j为车辆延迟到达客户j的惩罚系数；E(Pjk)为车辆k到达客户j的期望延迟时间；E(Lk)为配送中心对路径L进行修正所产生的期望成本。Wjk,Pjk,xijk的表达式分别为：
Wjk=max{aj-Ajk,0},j∈Rk,
1≤j≤nk,k∈K；
(2)
Pjk=max{Ajk-bj,0},j∈Rk,
1≤j≤nk,k∈K；
(3)
xijk={0,1},∀i,j∈V0,k∈K。
(4)
式中：Ajk表示车辆k到达客户j的时间；aj,bj表示客户j时间窗的下界与上界；Rk表示车辆k行驶的路径。
(2)约束函数
为了使所求解的VRP更加符合实际，构建约束函数如下：
1)需求不可拆分约束 该约束表示客户只能由一辆车服务。如果车辆已为某客户提供服务，则其他车辆不再考虑该客户；如果车辆剩余容量不满足该客户需求，则回配送中心重新装载货物。
(5)
2)车辆容量约束 该约束表示车辆行驶路径上的客户总平均需求量不能超过车辆的最大容量，如果达到车辆容量约束，则完成该路径规划。
(6)
式中：E(εi)为客户i的平均需求量；Q为车辆最大容量。
3)其他约束
(7)
(8)
(9)
其中：式(7)表示车辆k从配送中心出发服务完所有客户后必须回到配送中心。xi0k为决策变量，如果车辆k服务客户i后回到配送中心0则为1，否则为0；x0jk为决策变量，如果车辆k从配送中心0出发，行驶到客户j所在地并对其服务，则为1，否则为0。式(8)表示每辆车对客户服务后必须离开该客户所在地。式(9)表示避免车辆行驶路径中出现子回路，|Sk|为车辆k行驶路径上的客户总数。
3 VRPSD-STW所用算法
因为客户需求为随机变量，满足离散均匀分布，所以传统启发式算法不再适用。本文提出一种二阶段算法，在第一阶段将客户需求进行确定化处理，使其等于期望值，再采用改进的自适应禁忌搜索算法(Improved Adaptive Tabu Search algorithm, IATS)进行求解，然而客户需求为随机变量，确定化处理的误差较大；第二阶段采用改进修正方法修正第一阶段的所得解，最终目的是使总成本最小。
3.1 IATS算法设计
本文采用IATS对禁忌长度、邻域结构进行自适应调整，并在算法中引入自适应惩罚系数。
3.1.1 自适应禁忌长度
算法采用自适应禁忌长度与静态禁忌长度的对比结果如图2所示，可见算法采用自适应禁忌长度比静态禁忌长度更有优势。
3.1.2 自适应惩罚系数
为了避免陷入局部最优，本文加入一定非可行解以扩大搜索空间。针对带时间窗的VRP，候选路径是否可行与能否满足约束条件有关。
(1)初始状态下 对于初始解s∈S,c(s)表示车辆总行驶时间，q(s)表示违反容量约束的总容量，t(s)表示违反时间窗约束的总时间量，α,β分别表示对应的惩罚系数，定义函数f(s)=c(s)+αq(s)+βt(s)来评价解s的优劣。
(10)
(11)
(12)
3.1.3 邻域结构
为了使算法在更具灵活性同时避免陷入局部最优，本文吸取变邻域搜索算法的优点，使邻域结构动态变化。经过实验对比分析，采用改进Relocate邻域、“尾巴”交换和1-1交换组合的邻域结构，如果算法在当前邻域内搜索停滞不前，则跳到另一邻域内继续搜索。
(1)改进Relocate邻域 任意选取一个客户i，将其从原路径上移除，插入任意路径L上。若其插入后违反容量约束，则针对客户i将不再选取路径L；若客户i插入路径L上，路径L上存在两个客户p1,p2满足ap1≤ai≤ap2,bp1≤bi≤bp2，则将客户i插入这两个客户之间，否则将客户i插入路径L的末尾。
(2)“尾巴”交换 随机选择两条路径L0和L1，在路径L0上随机选取一点s0，在路径L1上随机选取一点s1，将s0和s1后面的“尾巴”(从被选顶点至线路终点)互换(配送中心除外)。
(3)1-1交换 随机选择两条路径L0和L1，在路径L0上随机选取一点s0，在路径L1上随机选取一点s1，将节点s1插入路径L0，将节点s0插入路径L1。
3.1.4 改进后的禁忌搜索算法步骤
在TS算法中，只有当迭代次数超过最大预设值maxT或最优解连续T次不更新时，才停止迭代并返回最优解。综上所述，IATS具体流程如算法2所示。
算法2自适应禁忌搜索算法。
输入：客户数量n，车辆最大容量Q，惩罚系数α，β，最大迭代次数Nmax，自适应因子δ，禁忌长度θ，邻域结构Nh(h=1,2,3)。
输出：全局最优解sbest。
1.初始化
2.随机生成初始可行解s
3.If s满足约束条件
4. sbest=s,f(sbest)=f(s)
5.else
6. f(sbest)=∞
7.WhileT 8. For h=1 To hmaxdo 11. Select s′ 12. If f(s′) 13. f(sbest)=f(s′) 14. s=s′ 15. θ=θ-1 16. Continue to search with N1(s)(h=1) 17. Otherwiseh=h+1 18. θ=θ+1 19. End for 20.更新禁忌表和惩罚系数 21.Endwhile 22.输出找到的最优解 因为设定客户需求为满足离散均匀分布的随机变量，将其进行确定化处理存在很大误差，所以在第二阶段采用修正算法修正第一阶段的所得解。本文提出一种新的修正算法—SRTD算法。 3.2.1 修正算法设计 为了使总成本最小，第二阶段提出的修正算法尤其重要，构建目标函数 (13) 式中：E(Lk)为配送中心对路径L进行修正产生的期望成本；nk为车辆k行驶路径上的总客户数；Fki为车辆k服务客户i后的修正成本。借鉴文献[22],Fki表达式为 (14) (15) (16) wi+1=max{ai+1-(di+ci,i+1+2c1,i+1),0}； (17) li+1=max{(di+ci,i+1+2c1,i+1)-bi+1,0}； (18) (19) (20) 其中：ai+1,bi+1为客户i+1时间窗口的左右边界；di为车辆离开客户i的时间；ci,i+1为车辆从客户i行驶到客户i+1所需的时间；c1,i+1为车辆从客户i+1所在地回到配送中心所需的时间；ci,1为车辆从客户i所在地回到配送中心所需的时间；c1,i+1为车辆从配送中心行驶到客户i+1处所需的时间。 车辆k服务客户i后,可采用DTD算法或PR(preventive restocking)算法进行修正，具体修正方案如图3所示。 图3a所示为第一阶段得出的一条规划路径，[0 300]为配送中心的时间窗口；[0 155]为26号客户的时间窗口；q=21为车辆服务完26号客户后的剩余容量；40为26号客户与34号客户之间的距离；[0 225]为34号客户的时间窗口；q={1,2,3,…,39}为34号客户的需求分布；50为34号客户与配送中心之间的距离。 图3b所示为用DTD算法和PR算法对路径进行修正的结果，可见两种算法的结果是一致的。点线线路表示车辆行驶至34号客户时，发现车辆剩余容量并不满足该客户的需求，车辆需要返回配送中心重新装载，因此产生额外成本；虚线线路表示车辆行驶至34号客户时，其剩余容量满足该客户需求，不会产生额外成本。 用DTD算法对路径进行修正，当车辆剩余容量为零时，车辆会回配送中心重新装载货物；用PR算法对路径进行修正，当车辆剩余容量小于下一客户的期望需求时，车辆会回配送中心重新装载货物。由于车辆服务完26号客户后的剩余容量大于零且大于34号客户的期望需求，用DTD算法和PR算法对该路径进行修正时的修正成本均为122.307。 用DTD算法和PR算法修正该路径，当车辆到达34号客户时，剩余容量大概率不满足该客户需求，必须回配送中心重新装载货物。车辆被动回配送中心不仅会产生额外的行驶成本，还会因车辆无法准时对客户进行服务而产生极大的惩罚成本。为了降低车辆被动回配送中心的概率，本文提出一种新方法，在车辆服务下一客户前进行判断，若直接回配送中心的成本小，则先回配送中心重新装载货物，再继续服务下一客户。该方法有效降低了车辆因剩余容量不足而回配送中心重新装载货物的概率，具体的修正方案如图4所示。可见，车辆服务26号客户后没有直接服务34号客户，而是先回配送中心重新装载货物，再服务34号客户，其中虚线线路为车辆将行驶的路径。因此本文方法能够避免车辆被动回配送中心装载货物，其修正成本为50，明显优于DTD算法和PR算法。 λ2,i+1li+1]pi+1； (21) (22) 3.2.2 修正算法步骤 本文所提算法要使每个客户修正成本均最小，从而使车辆行驶路径的修正成本最小。在车辆服务客户前进行选择，如果车辆继续服务产生的成本小，则继续服务下一个客户，否则回配送中心重新装载货物。因为客户需求满足离散均匀分布，所以确定客户i+1的最大需求值maxεi+1。若qi≥maxεi+1，则车辆继续服务客户i+1；否则，根据式(21)和式(22)计算其所产生的成本，选择车辆继续服务或回配送中心重新装载货物。 如果qi 因为本文最终目的是使修正成本最小，所以当qi 综上所述，修正算法的具体流程如算法3所示。 算法3SRTD修正算法。 输入：客户i+1需求εi+1，车辆服务客户i后的剩余容量qi，路线失败成本b，车辆违反时间窗的约束λ1,λ2。 输出：修正成本E(Lk)。 1.初始化 2.输入算法1所得最优解 3.For k=1 To K do 4. For n=i To ienddo 5. If qi≥max εi+1 6.车辆k服务当前客户后继续服务客户i+1 8. 车辆k服务当前客户后直接回配送中心 11. If qi 12. 车辆k服务当前客户后直接回配送中心 13. Else 14. 车辆k服务当前客户后继续服务客户i+1 15. End for 16. End if 17. i=i+1 18. End for 19.k=k+1 20.End for 21.输出找到的最优解 本文算法的相关实验均在同一实验环境中进行，其中CPU主频为2.80 GHz，内存为8 GB，操作系统为64位Windows10，编程语言为C++和MATLAB语言。 4.2.1 实验1 采用Solomon的6种类型VRPTW算例(C1类型、C2类型、R1类型、R2类型、RC1类型和RC2类型，共56个算例)[23]测试IATS，然后将IATS与DBA[10]、自适应文化基因算法(Adaptive Memetic Algorithm, AMA)[24]、PSO算法[25]进行对比，结果如表1和表2所示。表中：OS为算法独立运行10次后获得的最优解；AS为算法独立运行10次后获得的平均解；Time为算法运行时间。 表1 IATS与其他算法的对比实验结果 由表1可见，IATS具有鲁棒性较好、运行时间较短等优点，主要表现如下： (1)在C1类测试算例中，IATS的最优解略差于DBA和AMA，但优于PSO；在平均解和时间耗费方面，IATS略差于AMA，但优于DBA和PSO。 (2)在C2类测试算例中，IATS的最优解略差于其他3种算法；在平均解方面，IATS略差于AMA和PSO，但优于DBA；在时间耗费方面，IATS优于其他3种算法。 (3)在R1，RC1类测试算例中，IATS的最优解略差于DBA，但优于AMA和PSO；在平均解方面，IATS略差于DBA，但优于AMA和PSO；在时间耗费方面，IATS优于其他算法。 (4)在R2类测试算例中，IATS在最优解、平均解和时间耗费方面均优于其他3种算法。 (5)在RC2类测试算例中，IATS的最优解和平均解均优于其他3种算法；在时间耗费方面，IATS略差于DBA，但优于AMA和PSO。 由表2可见，在大多数情况下，IATS得到的最优解、平均解，以及在时间耗费方面均优于其他算法，具有一定的竞争性，主要表现如下： (1)在R201，C101，RC201测试算例中，IATS在最优解、平均解和时间耗费方面均优于其他3种算法。 (2)在R204测试算例中，IATS的最优解和平均解均优于其他3种算法；在时间耗费方面，IATS略差于DBA，但优于AMA和PSO。 (3)在C201测试算例中，IATS的最优解略差于其他3种算法；在平均解方面，IATS略差于AMA和PSO，但优于DBA；在时间耗费方面，IATS优于其他3种算法。 (4)在C204测试算例中，IATS的最优解略差于其他3种算法；在平均解方面，IATS略差于DBA和AMA，但优于PSO；在时间耗费方面，IATS优于其他3种算法。 (5)在RC101测试算例中，IATS的最优解略差于DBA和PSO，但优于AMA；在平均解方面，IATS略差于DBA，但优于AMA和PSO；在时间耗费方面，IATS优于其他3种算法。 (6)在RC208测试算例中，IATS的最优解优于其他3种算法；在平均解方面，IATS略差于AMA，但优于DBA和PSO；在时间耗费方面，IATS略差于DBA，但优于AMA和PSO。 4.2.2 实验2 首先在第一阶段用IATS求解R101-R110，C101-C105，RC101-RC105算例，然后将得到的解用SRTD算法、DTD算法[13]和PR算法[15]进行修正，结果如表3所示。将第一阶段用IATS对R101-R110，C101-C105，RC101-RC105算例进行求解所得的成本分别加上第二阶段SRTD算法、DTD算法、PR算法的修正成本，结果如表4所示。 表3 SRTD修正算法与其他修正算法的对比实验结果 续表3 表4 本文算法与其他算法的对比实验结果 由表3可见，在大多数算例中，SRTD算法的修正成本均明显低于其他算法，因此在第二阶段采用SRTD修正算法是有效且可行的。由表4可见，本文算法(IATS+SRTD)在大多数案例下均优于其他算法。因此，本文所提两阶段算法是有效且可行的。 本文对VRPSD-STW进行研究，提出一种两阶段算法。算法在第一阶段采用IATS，第二阶段采用SRTD算法。以Solomon的6种类型VRPTW算例为基础构造算例对算法进行测试,并将求解结果与相关文献的结果进行比较,结果表明IATS具有较强的寻优能力和较高的鲁棒性，SRTD算法较DTD算法、PR算法的效果更优；在测试C1，C2类算例时，因为客户集群分布，随机性较弱，所以IATS的寻优能力具有一定的局限性。由此可知，本文所提算法能够有效解决VRPSD-STW。 目前，针对VRPSD-STW的研究仍有进一步改进的空间，例如在模型中添加多配送中心约束或多时间窗约束。另外，为了更加符合实际情况，还可引入随机行驶时间和随机服务时间进行进一步研究。
3.2 修正算法
4 实验与分析
4.1 实验环境
4.2 实验结果与分析
5 结束语
