【析博】带时间窗约束的车辆路径多目标优化_有时间窗的路径优化

带时间窗约束的车辆路径多目标优化

摘要

车辆路径问题(Vehicle Routing Problem，VRP)旨在通过合理规划行驶路径来优化运输成本，对于降低物流运营成本具有重要的应用价值。带时间窗约束的车辆路径问题(Vehicle Routing Problem with Time Windows，VRPTW)是在 VRP 问题基础上引入了时间窗口约束，因其更符合当前实际物流配送系统的运行情况和应用场景而成为 VRP 问题研究的热点。本文基于 VRPTW 模型的基本构成要素：配送网络、路径和节点，面向三种常见的应用场景：物流配送、仓储管理和旅游路线规划，研究了 VRPTW 的四个拓展问题。在此基础上，分别为每个问题建立了数学模型并设计了相应的求解算法。主要研究内容如下：

1. 针对具有多个时间窗口的车辆路径问题，将配送网络作为核心要素建立了多时间窗车辆路径问题(Vehicle Routing Problem with Multiple Time Windows ，VRPMTW)模型以降低物流商的配送成本。通过重新设计破坏算子和修复算子、改进自适应选择邻域算子策略并完善自适应大邻域搜索(Adaptive Large Neighborhood Search，ALNS)算法框架，解决了搜索过程中邻域数量多、邻域选择缺乏指导的问题，增强了局部寻优能力。通过设置可以自适应调整移除客户数量的移除池、允许不可行解参与迭代和定期重启策略，能够更好探索解空间。仿真实验结果验证了算法的有效性并取得了更好的解。
2. 针对时间窗约束下的配送工作量公平分配问题，以路径为核心要素建立了考虑路径均衡的带时间窗车辆路径问题 (Vehicle Routing Problem with Time Windows and Route Balance，VRPTWRB)模型，设计了改进的多向局部搜索(ImprovedMulti-Directional Local Search，IMDLS)算法求解该多目标优化问题，通过平衡配送成本和各司机的工作量实现更公平的分配方案。算法通过自适应调整存档大小、设计新的选解指标和改进大邻域搜索等策略，能够快速找到更有潜力的解并加快收敛。通过增加自适应方向上的搜索扩展了搜索空间，提高了非极端的帕累托解的数量和占比，为决策者提供更多的选择方案。通过在测试算例上的对比实验验证了算法的有效性，并进一步研究了工作量资源和公平函数的选择对均衡性的影响。
3. 针对仓储物流过程中堆垛机的拣选路径规划问题，以节点为核心要素建立了奖品收集带时间窗车辆路径问题(Prize-Collecting Vehicle Routing Problem with Time Windows ， PCVRPTW) 模 型 ， 设 计 了 改进多目标引导 式 局部搜索 (Improved Multi-Objective Guided Local Search，IMOGLS)算法实现拣选路径优化。通过设计自适应增强扰动算子和策略，增加解的跳跃范围以扩大搜索空间进而摆脱局部最优。通过提出的引导式局部搜索策略，将时间窗约束转化为节点相似度，减少在低质量空间中的随机搜索，从而加快算法的收敛速度。通过设置精英池策略对迭代进化中的高质量非支配解进行及时存储和更新。仿真实验结果表明，该算法在多项指标上优于比较算法且一致性更好，同时也为仓储堆垛机的拣选路径规划提供了可行的优化方案。
4. 针对为游客构建个性化旅游路线的旅游路线设计问题，考虑游客对到访时间准时性、参观景点多样性和多条路线均衡性的需求，以节点和路径为核心要素建立了计数依赖利润的选择性带时间窗车辆路径问题(Selective Vehicle Routing Problem with Time Windows and Count-Dependent Profits，SVRPTWCDP)模型，设计了带重启策略的多向局部搜索(Restart Strategy Multi-Directional Local Search，RS-MDLS)算法进行求解。通过为两个目标函数分别设计相应的邻域算子以增强各自搜索方向上的局部搜索。通过设计基于搜索空间切换的重启策略，增强对解的扰动幅度以提高搜索效率。相关测试集上的仿真实验和实际案例的模拟应用验证了所提算法的有效性。

第 1 章 绪 论

1.1 课题背景及研究的目的和意义

(只摘录有意义)
VRPTW 问题的构成要素主要包括配送网络、路径、节点、目标函数和约束条件。配送网络、路径和节点属于与模型相关的要素，也是基本的要素；而目标函数和约束条件属于与求解算法相关的要素。按照物流配送过程的参与方划分，三种基本要素配送网络、路径和节点分别对应于物流商、司机和客户，如图 1-2 所示。

1.2 国内外研究现状

1.2.1 车辆路径问题求解算法的研究现状

本节主要对车辆路径问题的求解算法进行综述，其拓展问题如 VRPTW 的求解算法也多基于此进行设计。现有研究中，VRPTW 的主流求解算法可划分为精确算法(exact algorithm)和近似算法(approximation algorithm)两类[18]，如图 1-3 所示。

元启发式算法是独立于问题的算法框架，提供一些标准和准则用来指导启发式算法的开发，可以用来描述针对特定问题设计的启发式优化算法。元启发式算法可以搜索非常大的候选解的空间，同时可以在合理的时间内提供可接受的解，以解决科学和工程方面的复杂问题。在元启发式算法的搜索中，集中性(intensification)与多样性(diversification)策略同等重要[21] Iterated local search: framework and applications。搜索的集中性策略用于对当前搜索到的优良候选解的邻域作进一步更为充分的搜索，以期能够找到局部最优解。集中性搜索可以提高候选解质量，但容易使搜索陷入解空间的一个不包含全局最优解的小区域内。搜索的多样性策略则用来拓宽搜索区域尤其是一些未知区域，特别是当搜索陷入局部最优时，多样性搜索可改变搜索方向，使其能够跳出局部最优并防止算法被困在没有希望的区域，从而实现全局优化。多样性搜索可以增加解的多样性，但可能错过搜索空间中某个区域内的最优解。一个好的元启发式算法应能很好地平衡集中性与多样性，这样才能够快速地找到高质量的解。因此很多学者从集中性和多样性搜索的分配与转换是否合理来分析并改进元启发式算法[22]。

依据上述搜索算法的集中性和多样性策略，求解 VRPTW 问题的通用算法框架
可归纳为以下三个主要组成部分：局部搜索过程(local search procedure)、跳出局部最优的策略(escape local optimal strategy)和选解策略(solution selection strategy)，如图1-4 所示.

(1)局部搜索过程
局部搜索过程是元启发式算法的核心组成部分，能够让一个当前解通过邻域动作产生若干个新的解(邻域解)。局部搜索过程的目的是对当前解进行深入的开发(exploitation)，寻找局部搜索范围内的最优解(局部最优)。局部搜索过程主要体现的是元启发式算法的搜索的集中性[23]。

(2)跳出局部最优的策略
在搜索过程中，局部最优的陷入无法避免。对于一般的组合优化问题而言，局部最优解的质量通常不能满足需求，因此跳出局部最优的策略对于元启发式算法非常重要。跳出局部最优的策略的目的是对解空间进行更大范围的探索(exploration)，避免算法在己经搜索过的区域或者不能提供高质量解的区域花费过多的时间。跳出局部最优的策略主要体现的是元启发式算法的搜索的多样性[24]。

(3)选解策略
元启发式算法的求解思路特征是迭代搜索、逐步改进。每一次迭代后需要对产生的新解根据解的质量进行选择或维护，以用于下一次的迭代过程[25]。因此需要将问题和求解算法结合考虑来制定相应的选解策略。此处的选解策略主要包括：①对当前迭代产生的局部最优解(集)的接受准则，即选出作为下一次迭代的(一个或若干个)当前解。②对于使用帕累托支配的多目标问题，选解策略还应包括对存档(帕累托解集、精英解集)的维护和更新策略，以明确每一次迭代时需要进行局部搜索的当前解。选解策略实质上体现了搜索过程的集中性和多样性的分配与转换，即平衡上面提到的局部搜索过程与跳出局部最优的策略，实现算法的整体改进与效能提升。

1.2.2 带多个时间窗的车辆路径问题研究现状

由于 VRPMTW 问题具有较复杂的约束条件，因此现有的求解算法大多使用基
于邻域搜索的启发式算法。

• Favaretto 等[32]首次系统地研究了 VRPMTW，目标是尽量减少总路线持续时间和总行驶距离，并提出了一种蚁群系统算法，将时间窗口分为多次访问，但没有提供进一步的细节。
• 李寒梅[33]以卷烟厂之间的原料联合运输调运工作为实际背景，建立多时间窗需求可拆分的集送货车辆路径问题模型，使用改进局部搜索过程的变邻域搜索算法进行求解。
• Beheshti 等[34]以旅行成本最小化和顾客满意度最大化为优化目标，提出一种协同进化的多目标量子遗传算法用于求解具有多个优先时间窗的多目标 VRP。
• Belhaiza 等[35]将最小化总持续时间作为目标，提出了一种混合变邻域禁忌搜索(HVNTS)启发式方法。
• 随后，Belhaiza 等[36]提出了一种混合遗传变邻域搜索启发式算(HGVNS)，遗传交叉算子启发式被集成到变邻域搜索(VNS)的扰动阶段。由于缺乏有效的多样化策略，该算法会出现过早收敛。

多时间窗约束的存在使得问题的搜索空间急剧增大，并充斥着大量的不可行
解，此时需要更多类型的邻域算子并改进选取策略，从而更好地探索解空间.

• Ferreira等[37]修改了基于文献[36]的 VNS 算法框架。然而，该算法只在可行的搜索空间中进行搜索，导致得到的解缺乏多样性，在基准测试算例的整体改善仅为 0.02%。这表明必须采取有效措施处理和利用在搜索过程中产生的不可行的解。
• 马龙等[38]以最小化车辆运输总成本、运输距离和车辆数为优化目标，构建了多目标多时间窗车辆路径模型，并提出一种鸽群-智能水滴互补改进优化算法，利用自适应变邻域扰动策略提高了算法的开发和探索能力。
• Hoogeboom 等[39]提出了一种自适应变邻域搜索算法，并改进了 VRPMTW 的评估框架。当局部最优值在几次迭代中没有改善时，通过扰动过程获得新的解，该过程将当前解删除并重新插入 的客户。然而，该方法的扰动过程缺乏对破坏和修复算子的选择性指导，增加了算法的计算复杂性。

1.2.3 考虑路径均衡的带时间窗车辆路径问题研究现状

VRP 问题已被学者研究了几十年[40]，但现有研究主要集中在物流商利益的角度，以配送成本最小化为出发点[41]。Karsu 等[42]的评论表明，运筹学文献中对各个问题领域的公平性和均衡性的关注越来越受到重视，这也特别包括物流部门[43]。实际上，物流配送是一个涉及多方利益的过程[44]，作为配送方案的实际执行者，司机方的利益也需要得到考虑和满足。受客户点分布等因素的影响，分配给各司机的工作量往往存在差异。从长远来看，合理分配工作量能够提高司机的工作积极性，进而有利于物流企业的运营与管理。与配送工作量公平分配相关的 VRP 问题被归纳为考虑路径均衡的车辆路径问题(Vehicle Routing Problem with Route Balance，VRPRB),

当前，许多 VRP 问题的实际应用开始考虑均衡性指标，这些指标大多与原优化目标一起构成多目标优化问题。

• 孙丽君等[48]引入公平理论中社会比较的思想，构建了考虑司机工作量均衡的成品油配送的多目标优化模型，为有较高工作量均衡性要求的成品油配送方案的制定提供决策支持和管理启示。
• 李珍萍等[49]研究了考虑工作量均衡的成品油二次配送车辆路径问题。以总配送成本最小化和不同车辆路径长度之差最小化为目标，避免工作量分配不均。
• 樊航等[50]研究了带时间窗约束的车间物料配送优化问题，以最小化调用作业人数、最小化总配送时间和均衡车辆负载为目标建立了多目标优化模型并提出一种改进的混合教与学算法对模型进行求解。
• 李明琨等[51]针对金融押运成本高且各押运线路工作量不均衡等问题，建立以押运成本最优化和押运线路工作量均衡为目标的多目标优化模型。上述文献从实践上表明，在VRP 模型中考虑均衡目标，可以进一步优化各个配送路线，为司机方带来更好的公平收益.

在求解多目标的 VRPRB 问题时，需要重点改进算法的局部搜索策略和选解策
略，以平衡算法的开发与探索能力，从而快速找到所需的非支配解集.

• Ibarra-Rojas等[52]通过优化需求满意度和交货时间的公平性来定义 VRPRB 问题。但作者使用计算时间限制为三小时的商用求解器无法获得大型实例的可行解，这表明使用精确方法并不能有效地解决大规模 VRPRB 问题。
• Melian-Batista 等[53]考虑了时间窗约束，并设计了一种基于散点搜索(SS)的启发式算法。该方法在小规模的算例上可以很好地逼近精确的帕累托前沿，并且在大规模算例上优于 NSGA-II，表明启发式算法具有进一步改进解质量的潜力。

  • 帕累托前沿（Pareto Frontier）是一个经济学和优化领域的概念，也在多目标优化问题中广泛应用。它是指在多目标优化问题中，所有非劣解（Pareto-optimal solutions）的集合，即在改善一个目标函数的同时，不会恶化其他目标函数的解的集合。换句话说，帕累托前沿包含了所有无法被其他解所优于的解，因此它代表了一系列最优解的集合。
  • NSGA-II（Non-dominated Sorting Genetic Algorithm II）则是一种多目标优化算法，它是Niching方法的一种改进，可以用于解决具有多个目标函数的优化问题。NSGA-II算法通过非支配排序和拥挤度距离的概念，保持了解的多样性和收敛性。其基本思想是将个体分为不同的等级，其中第一等级包含那些在所有目标函数中都最优的个体，第二等级包含那些不属于第一等级但在至少一个目标函数上优于第一等级的个体，以此类推。同时，NSGA-II算法还使用了拥挤度距离的概念，以避免解集中在同一区域。

• Lehuede 等[54]定义了考虑运输成本和工作量平衡的双目标优化的 leximax 车辆路径问题，并通过基于多向局部搜索(MDLS)框架的启发式求解。但该算法并没有限制当前解集的大小，导致了冗余搜索和计算资源的浪费，严重减慢了算法的收敛速度。
• Oyola 等[55]提出了贪婪随机自适应搜索过程(GRASP)启发式方法解决 VRPRB。尽管所获得的解声称提供了公平性更好的质量，但也消耗了更多的计算时间。
• Eskandarpour 等[56]以货币成本和环境成本为目标，并提出了一种增强的多向局部搜索(EMDLS)算法来解决具有多个行驶里程的异构电动车辆路径问题。然而，该文中“环境成本”的定义是 CO2 排放量，这过于具体，不利于提高模型的普适性和可扩展性。此外，算法的收敛速度也需要加快。
• Matl 等[57]确定了VRP 问题的一组理想公平函数应该满足的公理属性，并使用它们来评估六种公平函数。实验表明，既没有能够满足所有公理的公平函数，也没有在所有指标方面都占优的公平函数，并指出公平函数的选取应取决于具体的优化问题.
• Sivaramkumar 等[58]指出，在 VRPTW 中使用总时间平衡(TTB)可以比使用路线平衡(RB)获得更好的平衡效果。作者将 TTB 指标定义为最小化最长路线与最短路线的时间差值，并提出适应性聚合遗传算法(FAGA)求解问题。然而，该文只选择了一个公平函数来衡量不平等程度，适用范围较窄，并且使用遗传算法框架导致收敛速度较慢。

一些研究从理论上表明，在 VRP 问题中添加均衡目标能够产生公平性更好的解决方案，并且对原目标的影响较小。

• 均衡目标通常指的是在优化主要目标（如总行驶距离最短、总成本最低等）的同时，考虑其他次要目标，以实现更公平或更均衡的解决方案。这些次要目标可能与资源分配、工作负载、服务质量、环境影响等方面有关。

• 不仅要追求整体效率或成本的最优，还要考虑各个节点、路径或车辆之间的均衡性和公平性。这样可以避免某些节点或路径过度使用或负载过重，而其他节点或路径则闲置或负载过轻的情况。

• 假设在一个物流配送问题中，主要目标是最小化总行驶距离。然而，如果只考虑总行驶距离，可能会导致某些配送点频繁被某些车辆服务，而其他车辆则很少或从未服务这些点。这样就造成了车辆之间工作负载的不均衡，可能导致某些车辆过度劳累，而其他车辆则相对空闲.自己查资料解释均衡目标的作用，然后添加的

• Banos 等[59]研究了距离和负载的路线范围公平性，他们的结果表明，上述两个公平性目标会产生明显不同的解。
• Galindres-Guancha等[60]求解了多站点车辆路径问题(MDVRP)中成本和工作量的平衡问题。考虑了两个目标函数：第一个是最小化运营成本，第二个是使用路线之间的标准差作为实现上述目标的标准的路线平衡。该文指出，两个目标之间的公平程度可以通过使用相对成本较低的函数进行衡量。
• 刘恒宇等[61]结合快递公司稳定性配送服务背景，提出了考虑交通拥堵和员工工作量的稳定性车辆路径问题。结果表明，改善快递人员工作量的公平分配对配送成本的影响很小。
• Zhang 等[62]研究了具有外包和利润平衡(VRPOPB)的车辆路径多目标优化问题，以最大限度地降低总旅行成本和平衡所有运输公司之间的利润。结果表明，通过最大化利润来平衡利润所有运输公司的单位利润，可以有效避免扭曲解的发生。

综上所述，现有研究对时间窗约束下的路径均衡问题关注较少，因此本文从物流过程配送司机的视角出发，以路径为核心要素研究了考虑路径均衡的带时间窗车辆路径问题(VRPTWRB)。该模型较传统的无时间窗模型更接近实际物流应用场景，具有重要的实践意义和理论研究价值。在求解算法方面，现有方法在局部搜索过程和寻找较大潜力的解方面仍需进一步改善，特别要解决在搜索过程中因存档规模过
大而造成算法收敛速度变慢的问题。此外，还需要进一步研究公平目标对原目标的影响程度，进而通过综合考虑总成本和各司机(路径)间的工作量差异，保障司机方的综合利益。

1.2.4 奖品收集带时间窗车辆路径问题研究现状

1.2.5 计数依赖利润的选择性带时间窗车辆路径问题研究现状

1.3 研究内容及研究框架

本文以带时间窗约束的车辆路径问题(VRPTW)为研究中心，基于 VRPTW 模型的基本构成要素：配送网络、路径和节点，面向三种常见的应用场景：物流配送、仓储管理和旅游路线规划，探讨了四种 VRPTW 问题。具体研究内容如下：
(1)对具有多个时间窗口的车辆路径问题(VRPMTW)进行研究。该问题从物流商的利益出发，以配送网络为核心要素进行路径优化，实现以较低的成本向客户提供配送服务。在实际配送过程中，客户可以提供多个时间窗口，物流商需要选择其中一个时间窗口进行服务。因此该问题具有广泛的应用和研究价值。在处理时间窗口约束时，需要同时解决时间窗的限制和路径的优化。现有研究使用几种基于邻域搜
索的方法来解决这类问题，但仍然具有生成大量不可行的解并且容易落入局部最优的缺点。为此，对自适应大邻域搜索(Adaptive Large Neighborhood Search，ALNS)框架进行了修改，并添加了额外的组件来增强搜索过程。通过设计基于破坏和修复算子的自适应选择邻域算子策略并完善 ALNS 算法框架，解决了搜索过程中邻域数量多、邻域选择缺乏指导的问题，增强了局部寻优能力。通过设置可以自适应调整移除客户数量的移除池、允许不可行解参与迭代和定期重启策略，能够更好探索解空间，增加解的多样性。最终获得了符合物流商利益的综合成本更低的配送方案。

(2)对考虑路径均衡的**带时间窗车辆路径问题(VRPTWRB)**进行研究。现有研究主要集中在物流商利益的角度，而考虑路径均衡的车辆路径问题能够平衡配送成本和司机的工作量，并通过更公平的分配方案更好地照顾司机的公平性，从而实现多方利益的平衡。VRPTW 的时间窗口限制将对工作量的均衡产生影响，传统的基于无时间窗模型下的分析方法不再适用。针对 VRPTWRB 模型，以路径为核心要素，
设计了改进的多向局部搜索(Improved MultiDirectiona LocalSearch，IMDLS)算法进行求解。算法通过对存档规模进行限制和设计使用 ICHV 指标选择索过程中产生的具有较大探索潜力的解以实现快速收敛。通过增加在自适应方向的搜索来扩展搜索空间，从而增加解的多样性。最后对工作量资源和公平函数的合理选择进行了数值研究.

(3)对奖品收集带时间窗车辆路径问题(PCVRPTW)进行研究。在仓库自动化过程中，高效的拣选路径策略是提高仓库效率的关键因素之一。针对堆垛机储货箱的容量限制、出货时间的要求和货物的优先级，以节点为核心要素进行路径优化，建立了 PCVRPTW 模型，并设计了改进的多目标引导局部搜索(Improved MultiObjective Guided Local Search，IMOGLS)算法进行求解。通过设计的自适应增强扰动算子和策略，增加解的跳跃范围，通过扩大搜索空间来跳出局部最优。设计的引导局部搜索策略，通过将时间窗约束转化为节点相似度，减少在低质量空间中的随机搜索，从而加快算法的收敛速度。该问题的建模与求解能够较为客观地反映实际的作业过程、贴合实际的拣选作业场景。同时，优化多个目标可以更准确地反映生
产实际，方便决策者选择合适的拣选路径，节省拣选环节的作业成本，进而降低物流企业的综合成本。

(4)对计数依赖利润的选择性带时间窗车辆路径问题(SVRPTWCDP)进行研究。该问题考虑联合节点和路径作为核心要素，以旅游路线设计为应用场景开展优化。针对游客对到访时间准时性、参观景点多样性和多条路线均衡性的需求，将不同类型的访问景点进行分类，目标是制定游客满意度高、游览计划更均衡的旅行路线。建立了 SVRPTWCDP 模型，设计了带重启策略的多向局部搜索(Restart Strategy Multi-Directional Local Search，RS-MDLS)算法进行求解。通过为两个目标函数分别设计相应的邻域算子以增强各自搜索方向上的局部搜索。通过设计基于搜索空间切换的重启策略，增强对解的扰动幅度以提高搜索效率。该问题的提出和求解不但进一步扩展了 VRPTW 问题的研究领域，还对未来求解相关问题的算法提供了参考。

本文的研究框架如图 1-5 所示。针对带时间窗约束的车辆路径问题(VRPTW)，首先分析和整理大量的文献，总结出前人研究的局限性，并归纳相关问题建模和求解算法。随后在满足实际需求和约束的情况下，针对各个具体问题中的核心要素建立了相应的数学模型。最后在分析与反复测试的基础上，设计有效的启发式算法求解各个问题。

第 2 章 带多个时间窗的车辆路径问题研究

2.1 引言

作为物流过程的组织者，物流商的核心利益诉求是降低运输成本以提高综合利润。制定高效的运输组织方案能够有效降低运输成本，尤其是对时效性要求较高的应用场景。随着现代物流配送系统的建立和电子商务的快速发展，传统的基于单时间窗场景的物流运输模型已经难以适应现代物流准时、高效的配送需求。许多实际物流场景，如同城快递、生鲜和外卖的配送业务等往往具有多时间窗的特征[104,105]。带多个时间窗的车辆路径问题(VRPMTW)是现实生活中物流配送问题的推广，对其进行研究能够有效降低物流商的配送成本，具有广泛的应用和研究价值。

现有研究主要采用基于邻域搜索的元启发式方法，该方法的核心思路是设计针对性的邻域算子以充分探索和开发搜索空间。多时间窗约束的存在使得问题的搜索空间急剧增大，并充斥着大量的不可行解。此时需要更多类型的邻域算子并改进选取策略，还需要完善不可行解的处理和修复策略，从而更好地探索解空间。为了解决上述问题，本章对自适应大邻域搜索(ALNS)框架进行了修改，并添加了额外的组件来增强搜索过程，解决了搜索过程中邻域数量多、邻域选择缺乏指导的问题，增强了局部寻优能力。通过设置可以自适应地调整移除客户数量的移除池、允许不可行解参与迭代和定期重启策略，能够更好探索解空间。最终获得符合物流商利益的综合成本更低的配送方案.

2.2 问题描述及模型建立

VRPMTW 问题可以用有向图描述。令$G=(V,A)$ 为完全图，其中$V$代表顶点集，$A$代表弧集。
顶点集可以分为 V = { I , D } V=\{I,D\} V={I,D} ，其中$I$ 代表一组客户， $D$代表仓库。
用$K$ 表示参与配送的车辆总数量。每辆车$k\in K$的最大载重量记为$Q_k>0$.车辆$k$离开车场 d k ∈ D = { 1 , ⋯   , d } d_k\in D=\{1,\cdots,d\} dk​∈D={1,⋯,d} 后需要为子集$N_k$ 中的客户提供服务，最后返回$d_k$形成一个完整的循环。
每个客户$iinI$有其需求$q_i$ 和服务时间$s_i\ge 0$。每个客户有$\overline{p_i}$ 个可选的交货时间窗口 W i = { w 1 , ⋯   , w p i ˉ } W_i=\{w_1,\cdots,w_{\bar{p_i}}\} Wi​={w1​,⋯,wpi​ˉ​​}，其中$l_{p_i}$和$u_{p_i}$ 分别是时间窗$w_{\overline{p_i}}$的下界和上界，并满足$0<l_1\le l_{p_i}<u_{p_i}\le u_{\overline{p_i}}<\infty$.一个客户只能由一辆车进行访问服务。如果车辆在时$l_{p_i}$ 之前到达客户$i$ ，则应原地等待至$l_{p_i}$ 时刻再开始服务客户。
每辆车对应一条路线$k$，包含总行驶距离、总行驶时间和总持续时间$D_k$ ，其中总持续时间等于服务时间、等待时间和行驶时间的总和。
VRPMTW 的目标是最小化满足所有客户需求的总成本$f_1(X)$ ，其中$X$ 代表 VRPMTW 的解。总成本$f_1(X)$ 由四部分组成：总行驶时间、总等待时间、总服务时间和车辆的固定成本，上述都已转换为时间单位表示。VRPMTW 可以用混合整数线性规划模型描述。式中使用的决策变量和参数定义如表 2-1 所示:

• 约束(2-2)确保每个客户只能由一辆车提供服务约束.
• (2-3)保证车辆 的每条路线都在仓库点开始和结束，并且离开客户节点 的弧等于进入其节点的弧.
• 约束(2-4)和(2-5)分别保证每个客户 只能有一次进入和一次离开的访问。
• 约束(2-6)规定了车辆k的累积容量不超过$Q_k$

• 约束(2-7)保证车辆$k$离开仓库点$d$ 的时间不超过 $l_d$。
• 约束(2-8)保证车辆$k$返回仓库点的时间小于等于$u_d$ 。
• 约束(2-9)要求当客户$i$ 被分配到车辆$k$时，车辆$k$在客户 的出发时间至少等于车辆$k$到达客户 的时间加上车辆$k$的等待时间和客户$i$的服务时间。
• 约束(2-10)表示如果弧$(i,j)$已经分配给车辆$k$ ，则车辆$k$ 到达客户$j$的时间等于车辆$k$ 离开客户$i$的时间加上客户$i$到$j$ 的行程时间$t_{ij}$ 。
• 约束(2-11)和(2-12)表示当客户$i$在时间窗口$p$内由车辆$k$服务时，车辆$k$的到达时间加上它在客户$i$ 处的等待时间在时间窗口$[l_i^p,u_i^p]$内。
• 约束(2-13)为每个客户$i$ 选择一个唯一的时间窗。
• 约束(2-14)表示只有在使用车辆的情况下车辆$k$才能为给定的客户$i$提供服务。

约束(2-15)至(2-17)约定了决策变量和相关参数的范围。

2.3 算法设计

作为 VRPTW 的拓展问题，VRPMTW 也是一个 NP-hard 问题，使用精确算法很难在有效时间内得到最优解，而许多元启发式算法已成功应用于带时间窗口的车辆路径问题。本章算法以 ALNS 为框架，并根据 VRPMTW 问题的特点，增加了保持多样性和处理不可行解的机制，以提高优化效果。这些组件尝试在执行破坏算子和修复算子的过程中修复不可行的解，并在搜索过程中充分利用与 ALNS 框架相关的可用信息。ALNS 是对大邻域搜索(LNS)的改进，特别适用于严约束的组合优化问题。目前，ALNS 算法已成功应用于解决车辆路径问题的几种变体。然而，当涉及到特定的变体问题时，需在原始框架的基础上添加用于处理特定问题或提高算法性能的其他组件。

2.3.1 自适应大邻域搜索算法框架

本章的方法遵循表 2-2 中描述的 ALNS 算法框架。该算法从自适应最小成本插入(MCI)方法生成的初始解开始搜索。迭代开始时，将当前解$S_{curr}$和最优解$S_{best}$ 同时作为初始解。然后，选择破坏(移除)算子从当前解中删除$\psi$ 个客户，并选择修复(插入)算子将这些客户重新插入。该算法通过轮盘赌机制自适应地选择过去表现良好的移除和插入算子。整个搜索过程分为多个迭代段，在每个迭代段结束时，更新算子得分。局部搜索过程由四个邻域算子组成以减少或消除每次迭代段内循环中未得到服务客户的数量。如果上述方法生成的新邻域解满足基于模拟退火的接受准则，则可以作为下一次迭代的新当前解。算法的停止条件是达到最大迭代次数。为了增强搜索能力，提出的算法接受不可行的解并进行修复.

• 模拟退火算法是一种用于求解优化问题的随机搜索算法，其接受准则通常采用Metropolis准则。根据这个准则，当新解的目标函数值比当前解的目标函数值更优（即目标函数值更小）时，新解总是被接受作为当前解。然而，当新解的目标函数值比当前解的目标函数值更差时，新解仍然有可能被接受，接受的概率取决于目标函数值差的大小和当前温度参数T。
• 具体来说，接受概率的计算公式为exp(-Δt’/T)，其中Δt’为新解与当前解的目标函数值差，T为当前温度参数。这个公式表明，当Δt’较大时（即新解比当前解更差时），接受概率较小，算法更倾向于保留当前解；而当Δt’较小时（即新解比当前解稍差时），接受概率较大，算法有可能接受新解以跳出局部最优解。
• 随着温度参数T的逐渐降低，接受较差解的概率也会逐渐减小，使得算法逐渐趋向于全局最优解。因此，模拟退火算法通过控制温度参数T和接受准则，实现了在搜索过程中的随机性和全局性，从而能够有效地求解优化问题。自行查找模拟退火的接受准则

2.3.2 初始解的构建

为了生成初始解，改进了称为最小成本插入(Minimal Cost Insertion，MCI)的启发式方法。首先随机选择一个客户并将其插入当前解。此位置应最小化成本$f_1(X)$ 的增量值，而不会违反容量和时间窗限制。设最多可使用的车辆数上限为：

$$最多使用车辆数上限=\lceil 权重\cdot \frac{所有客户的需求之和}{所有车辆的最大载重之和}$$

如果此过程仍有空闲车辆(也称为空路径)可用，则可以将客户插入到非空路径中或直接分配到其他空的路径。如果当前客户无法插入任何路径，则将其放置在未服务客户池(Unserved CustomersList，UCL)中。然后，反复尝试将客户插入当前解或 UCL，直到分配完所有客户。尝试此方法 10 次，并将 UCL 中客户数量最少的解作为最终的初始解。

2.3.3 自适应权重和分数调整

接下来将详细解释如何在 ALNS 算法的每次迭代中选择这些算子。有关五个移除算子和三个插入算子的更多详细信息将在 2.3.4 节中介绍。

本章算法通过选择破坏(移除)算子和修复(插入)算子来破坏和修复当前解。每个算子$i$ 都有一个分数$p_i$ 和一个权重$w_i$ 。在每个段的开始，所有算子的权重相等，所有算子的得分也都等于 1。破坏和修复算子在迭代过程中的得分管理如下：
每当找到新的全局最优解时，破坏和修复算子的得分将增加${\sigma }_4.$
当有比当前解更好且之前没有出现过的新解时，该算子的得分将增加${\sigma }_3$ 。
如果新解改进了当前解，但该解之前出现过，则该方法的得分增加${\sigma }_2$。
如果新解满足以下三个条件：比当前解差，但被接受准则接受，并且以前从未遇到过，则该算子的得分增加 ${\sigma }_1$。
后根据这些算子的权重，将轮盘赌机制应用于选取相应的破坏和修复算子。

本章算法将整个迭代过程分成若干段，用$i_{seg}$表示一个迭代段，其中包含若干次迭代。设置迭代段的目的是在每个迭代段内，所有破坏和修复算子的权重保持不变；并在每个迭代段的末尾按如下方式更新：
$w_{i+1}=(1-\zeta )w_i+\zeta {\pi }_i/{\varphi }_i$,其中
${\pi }_i$表示移除和插入算子的分数，
${\varphi }_i$表示该算子在段$i_{seg}$ 中执行的次数,
$\zeta$是调整参数。
反应因子$\zeta \in [0,1]$控制算法对每个破坏/修复算子分数变化的反应速度。
如果$\zeta$设置为 1，则算子的选择仅取决于在刚结束的迭代段期间获得的分数。
如果$\zeta$设置为 0，则算子的选择仅取决于之前迭代段中获得的权重，而不考虑刚结束的迭代段中获得的分数。
另外，此处设置了两个单独的轮盘赌用以区分破坏算子和修复算子.

2.3.4 改进的破坏和修复算子

2.3.4.1 破坏算子

本章使用五个改进的破坏算子(移除算子)。破坏阶段的任务是从当前解中删除个客户，并将这些客户移动到 移除池(Removal List，RL) 中。如果在破坏阶段之前 UCL 中仍有未服务的客户，则将这些客户保留在 RL 中并清空 UCL。接下来将一一介绍此阶段中使用的破坏算子。

(1)最差移除算子(Worst Removal)

删除当前解 中的某个客户会导致节约值的改变。此处将客户$i$在解中的成本与删除此客户后的成本之间的差定义为节约值：${\Delta }_i=F(S)-F_{-i}(S)$ ，其中 $F_{-i}$表示没有客户$i$ 时解的成本。最差移除算子尝试删除那些可以带来最大节约值的客户，那些具有较高节约值的客户节点更有可能被选中。最差移除算子的伪代码详见表 2-3。

如上图所示，是一个移除客户5的操作示意图。移除前后的其成本节约值=$x_{45}+x_{56}-x_{46}+节点5的服务成本$

(2)基本相关移除算子(Basic Related Removal)

相关移除(又称 Shaw 移除)的原理是移除特征相似的客户节点，使得后续的修复算子能够有机会重新安排这些客户，从而生成新的解。在许多研究中，Shaw 移除算子已被证明是一个非常有效的邻域算子，因此本章基于 Shaw 移除算子重新设计了处理 VRPMTW 模型的基本相关移除算子。基本相关移除算子的伪代码参阅表 2-4。

猜测：在while的内循环中，每次都在$S_{curr}^{\prime }$随机选择一个客户i,然后删除其相似度高的节点j。也就是对于相似度高的节点对保留了一个。

相关移除通常涉及以下几个步骤：自查资料

1. 选择要移除的元素：根据某种策略（如随机选择、基于启发式规则的选择等），从当前解中选择要移除的元素。
2. 移除元素：将选择的元素从当前解中移除，生成一个候选解。
3. 评估候选解：计算候选解的目标函数值，以评估其质量。
4. 更新当前解：如果候选解的质量优于当前解，则将其作为新的当前解；否则，根据某种策略（如概率接受准则）决定是否接受候选解作为新的当前解。

首先随机选择一个基准客户，然后计算其他客户的相关性并排序，再将具有高相似性的客户移动到删除列表中。客户的相似性可定义为相似指数${\gamma }_{ij}$:

• 距离相似指数${\gamma }_{ij}^s$:可由距离$d_{ij}$ 和两个点之间的最大距离$d_{max}$直接得出. $\frac{d_{ij}}{d_{max}}$
• 需求相似指数${\gamma }_{ij}^q$: $i$和$j$点的需求以及所有客户的最大和最小需求($q_{max}和$q_{min})得出.$\frac{|q_i-q_j|}{q_{max}-q_{min}}$
• 时间窗口相似指数${\gamma }_{ij}^t$:表示客户$i$和$j$之间的相对时间窗口重叠。

直观来看，越相似的客户越有可能在不违反约束的情况下进行交换等邻域动作。

(3)改进相关移除算子(Improved Related Removal)

该启发式是对上面介绍的基本相关移除算子的改进，伪代码如表 2-5 所示。改进相关移除算子不是从所有客户中随机选择基准客户而是从 UCL 中选择。在保证选取的客户总数不大于$\psi$ 的情况下，尝试在 UCL 中为每个客户尽可能地选取均匀数量的高相似度客户，然后将其添加到 RL 中。设计此算子的目的是尝试将客户从 UCL插回至解中，从而降低成为不可行的解的可能性 。为避免重复移除某些客户，在计算之前先统计已经被选作基准客户的次数。那些被选中频率较低的客户将有更大的机会在下一次迭代中被选入 RL，有助于增加多样性。

(4)路径移除算子(Route Removal)

如名称所示，路径移除算子从当前解中随机选择一个路径并删除其所有客户。如果当前路径中的客户数量少于$\psi$ ，则会随机选择并删除另一条路径。重复上述操作，直到删除的客户总数达到或超过$\psi$ 。

示意图

(5)随机移除算子(Random Removal)

此算子从当前解中随机删除$\psi$个客户，从而助于扩展搜索空间。

2.3.4.2 修复算子

修复算子(插入算子)的作用是将移除池 RL 中的客户插入到由破坏算子根据某些规则处理后的解中。如果在插入操作后仍有无法插入的客户，则这些未服务的客户将保留在 UCL 中。本章使用了三个修复算子。

(1)贪婪插入算子(Greedy Insertion)

基于贪婪策略的思想，该算子将选定的客户插入其最佳位置和最佳路径。如果客户 可以在插入到路径 的位置 处，则插入成本可以计算为：

(2)后悔插入算子(Regret Insertion)

后悔插入算子旨在选择那些如果未在当前迭代中插入而后悔最多的客户。基本后悔插入算子根据后悔值对删除的客户进行排序。对于某个客户来说，其后悔值可以表示为客户的最佳插入位置(插入成本最低)与其第二好的插入位置(插入成本次低)的插入成本值之差。换句话说，基本后悔插入算子选择当前未插入将产生最大后悔值的插入位置。 k-后悔方法扩展了基本后悔插入方法，该方法最终选择的客户 满足：

(3)随机插入算子(Random Insertion)

随机插入算子以随机顺序将客户从 RL 插入到当前解中。在插入过程中不能违反时间窗约束，设置此算子也是为了保持解的多样性。

2.3.5 局部搜索过程

如前所述，ALNS 算法使用插入算子将客户从移除池 RL 插入到当前解中，此过程可能会导致一些客户无法插入。为此，创建了一个 UCL 池来存储这些客户。如果 UCL 在每次迭代时都不为空，即仍有多个客户未得到服务，则将为当前解执行由四个算子组成的局部搜索过程。选择两个破坏算子：改进相关移除、随机移除；和两个修复算子：后悔插入和随机插入。所提出的局部搜索对当前解执行四次破坏-修复操作(每次执行一次破坏操作和一次修复操作)，并采用首次改进接受原则——一旦 UCL 变空，则结束局部搜索过程，并更新当前解。若经过四次操作，UCL 中仍有客户，则选择客户数量最少的 UCL 对应的解作为当前解。表 2-8 详细介绍了局部搜索过程。

在伪代码的设置中都是先选择删除位置，再删除节点。先选择最佳的插入位置，再判断是否满足约束。也就是说，删除节点必定能够成功，而修复过程不一定能满足。？？？

设置局部搜索过程的目的是将 UCL 中的客户数量减少到零，并将不可行的解修复为可行的解。移除池 RL 的大小${\psi }^{LS}$ 表示要删除和插入的客户数，这对当前解有不同的影响。此处的策略是在迭代开始时将局部搜索过程中 RL 的大小设置为$\psi$ ，保持与主循环中的值相同；如果 UCL 中的客户数在$no{i}_{max}$次迭代中没有减少到零，则 RL 的大小将增加 1，最多到${\psi }_{max}^{LS}$。增大 RL 的目的是扰动当前解，从而跳出局部最优。相关参数的设置将在 2.4 节中详细介绍。

开始的时候移除池的大小设置为${\psi }^{LS}$,每次删除对应两次修复，如果都可修复则客户数量减少。如果不可修复，则将RL的大小增加1.

2.3.6 接受准则

为了使算法脱离局部最优，在 ALNS 算法框架中嵌入了模拟退火(SA)接受准则。具体的接受规则如下：
如果邻域解改进了通过移除和插入方法生成的当前解，则该邻域解始终被接受；
否则，该邻域解以概率 $e^{-(f(S_{curr})-f(S_{new}))/T}$被接受，其中 $S_{curr}$是当前解， $S_{new}$是邻域解， $T$表示温度，初始温度设置为 $T_0$。

在算法迭代过程中，当前温度按比例降低到$c\cdot T$ ，该比例系数$c$介于 0 和 1 之间，通常接近 1 以实现缓慢冷却。采用 SA 作为接受准则的主要目的是通过在开始时接受更差的解来扩展搜索空间从而增加解的多样性.

2.3.7 处理不可行解的策略

(1) 目标函数的惩罚项
为了评估不可行的解，本节通过添加一些惩罚项对目标函数进行了适当的修改。新构建的目标函数(2-23)增加了时间窗违规$\mu$ 和车辆超载$v$ 的加权惩罚。具体表达式如下所示：

每个客户$i$ 违反时间窗口约束的程度可以用式(2-24)表示，其中$a_i$ 是车辆开始为客户$i$提供服务的时间。对于每辆车$k$ ，容量超载量按式(2-25)计算。每个客户或车辆的两个违约量${\mu }_i$ 和$v_k$ 对应于惩罚项${\beta }_1{\mu }_i$ 和${\beta }_2{v}_k$ ，其中 ${\beta }_1$和${\beta }_2$ 代表权重。 $f_1(X)$表示原来的目标函数，算法中将采用新的目标函数$f(X)$ 。

(2) 当前可行解池

在每次迭代中，可行解将送入当前可行解池(Current Feasible Solutions Pool，CFS_Pool)的存档中，大小为 $N_{cfsp}$。当解的数量超过 $N_{cfsp}$时，将自动删除最差的解以保持池的大小。如果生成的解在每个迭代段结束时不可行，则最优解将作为当前解从 CFS_Pool 中弹出。该机制的目的不仅是充分利用迭代过程中产生的不可行解，特别是其中包含的高质量解信息，而且将不可行解修复为可行解，使算法逐渐收敛到最优目标。

2.4 仿真实验与结果分析

本节将展示进行的相关实验。2.4.1 节介绍了本章中使用的基准测试实例。然后，2.4.2 节介绍了如何调整 ALNS 算法参数。2.4.3 节中评估了 ALNS 算法在解质量方面的性能。2.4.4 节探究了破坏算子和修复算子的表现情况。提出的算法使用 Java语言编程，并在具有 16GB 内存的 Intel i5 2.7 GHz 处理器计算机上进行了测试。

2.4.1 基准测试集

文献[35]根据广泛使用的 Solomon VRPTW测试集生成了 VRPMTW的基准测试集。该测试集含 6 类共 48 个算例，每个算例中都有 100 个客户。根据客户时间窗口的宽度，这些算例可以分为两种类型：类型 1(含 RM1、CM1 和 RCM1 类)的时间窗较窄而类型 2(含 RM2、CM2 和 RCM2 类)的较宽。根据客户点分布则可以分为三类：聚类分布(CM1 和 CM2 类)、随机分布(RM1 和 RM2 类)和随机聚类分布(RCM1和 RCM2 类)。每个算例都有 1 到 10 个不重叠的时间窗口，每个算例的最优解未知。车辆成本(以时间单位)包括等待时间、行驶时间和服务时间以及固定成本。固定成本设定等于车辆容量，为 CM1、CM2、RCM1、RCM2、RM1 和 RM2 类型分别设置为 200、700、200、1000、200、200 和 1000。

2.4.2 参数设置

为了获得更好的结果，需要设置算法的各种参数。参数调整的原则是循序渐进，具体操作过程如下。作为 ALNS 中最重要的组成部分，首先要确定破坏和修复算子的参数。这里首先尝试调整基本相关移除算子的参数。然后使用贪婪插入算子作为修复算子来执行 ALNS 算法。请注意，该算法在此步骤中没有使用模拟退火接受准则。然后，在其他参数相同的条件下着重调整其中一个参数，并进行多次测试。具体来说，使用待测的参数值在每个算例上求解五次，并保留那些提供最佳平均解质量的参数值。下一步使用上述方法调整最差移除算子，主要调整各成分的权重值。在调整后续参数时，采用了调整后的所有破坏和修复算子，而不是使用单一的算子进行删除和插入。

在完成破坏和修复算子的参数调整后，继续调整模拟退火接受准则中的一些相关参数，这也是该方法能够找到高质量解的重要措施之一。为了调整 2.3.3 节介绍的轮盘赌机制的${\sigma }_1,{\sigma }_2,{\sigma }_3,{\sigma }_4$ 和$\xi$，对所有算例进行了数值试验调整。冷却速率参数$c$ 控制着第 2.3.6 节中模拟退火接受准则阶段的温度下降。根据现有研究和实际测试的经验，将该值设置为 0.9，用于后续的计算实验。更高的温度值意味着温度下降得更慢，导致在迭代中接受较差的现有解的可能性更高。因此，尝试了多组值作为初始温度 并最终选择了 0.4。表 2-9 列出了所有采用的参数。

为了调整局部搜索过程中移除池(RL)的参数，包括${\psi }^{LS},{\psi }_{max}^{LS}$和$no{i}_{max}$,根据ALNS 算法的经验，设置了几组不同的值。通过使用第 2.4.2 节中设置的参数，在所有测试算例上运行了完整的算法。此测试中考虑了 9 种组合：(12,20,200)、(12,20,500)、(12,20,800)、(15,22,200)、(15,22,500)(15,22,800)、(18,25,200)、(18,25,500)和(18,25,800)。每个算例运行 5 次并取平均值。表 2-10 中给出的结果表明，参数组合(15,22,500)在平均值方面表现最佳。因此，基于此分析，选择在其余数值实验中使用以下参数$({\psi }^{LS},{\psi }_{max}^{LS},no{i}_{max})=(15,22,500)$.

2.4.3 算法对比实验

在最终的实验中，将 ALNS 算法的性能与在文献[35]、文献[36]和文献[39]上发表的最先进的结果进行比较。由于文献[36]和文献[39]执行了 100000 次迭代，因此ALNS 算法执行 100000 次迭代。每个测试算例的计算结果在表 2-11 至表 2-16 中给出。连续运行 ALNS 算法 30 次，并在表 2-11 至表 2-16 中列出获得的最佳解值。在表 2-11 至表 2-16 中，每一列表示如下：第 2 列表示车辆数；HVNTS、HGVNS 和
EAVNS 列分别代表文献[35]、文献[36]和文献[39]获得的最优值；ALNS 表示本章方法获得的最优值；$ga{p}_1$、$ga{p}_2$ 和$ga{p}_3$ 分别表示 ALNS 对应于 HVNTS、HGVNS 和EAVNS 的相对改善百分比. 从表 2-11 至表 2-16 可以看出，ALNS 算法相对于
HVNTS、HGVNS 和 EAVNS 的总体平均改进分别为 1.19%、0.79%和 0.41%。表 2-16和表 2-14 还表明，ALNS 和 EAVNS 这两种算法在 RM2 类和 RCM2 类上获得了几乎相同的平均最优解值，但 ALNS 在其余几类实例上的性能都略好于 EAVNS。RM2
类算例的客户时间窗数量少但分布广，平均时间窗数量最少，每对连续时间窗之间的距离较大。由于时间窗的特点，RM2 类比其他类更容易求解，这使得两种算法找到的最优解非常接近(尤其是算例 RM204 至 RM208)。ALNS 算法还在全部 48 个算例中找到了31个算例的新的最优解，并将所有测试算例的解质量平均提高了 0.80%。

2.4.4 破坏算子和修复算子的相对表现

在 ALNS 算法的每次迭代中，通过使用一个破坏算子和一个修复算子生成新的解。这些算子是通过第 2.3.3 节中提出的自适应选择机制执行的选择。在第一个实验中，检查了所有算子是否都能产生更好的邻域解。在所有算例上执行调整后的算法，当每次生成新的最优解时，记录下使用的算子。由于在算法迭代的早期阶段可以相对容易地改进最优解，因此跳过前 10%的迭代后再进行计数统计。统计数据如图 2-2 所示。可以看到，所有的破坏或修复算子都能够产生好的邻域解，但所占比例不同。几种破坏算子的使用数比较平均，而对于修复算子来说，仅后悔算子就占据了近一半的比例。

具体分析，从修复算子的性能来看，后悔算子的计算复杂度略高，但能带来更好的解改进。为验证每个算子的性能，继续进行第二个实验。该实验将每个测试算例运行 10 次，同时屏蔽一个算子而保留其他算子。实验的评判指标是解质量下降的平均百分比以及解质量下降的最大百分比。解质量下降指标是指实验中排除某个破坏/修复算子后解质量的下降程度。表 2-17 列出了算子的统计数据。结果表明，排除任何破坏或修复算子都会导致解质量的下降(相对于最优解)。该结果进一步表
明，本章设计的所有的破坏和修复算子都发挥了作用。因此，在后续实验中继续保留所有破坏和修复算子，因为这些算子的组合能够找到最优解。

为进一步探索每个算子在解改进过程中的效果，继续评估了这些算子在寻找下列解的有效性：①新的最优解、②更好的当前解以及③通过模拟退火接受的新解。在此测试中，算法在每次执行中保留一个破坏(或修复)算子和所有修复(或破坏)算子，统计所有 48 个算例中累计运行 5 次的结果。如表 2-18 所示，第 2 列至第 4 列分别对应于情形①至③。与其他算子相比，改进相关移除算子在寻找新的最优解以及更好的当前解方面更有效。后悔插入算子在更新最优解和当前解方面也更有效。如前所述，多样化的算子和自适应选择是 ALNS 算法最强大的特征。虽然一些算子表现出了更好的效果，但如果没有其他算子的协助配合，也很难产生较好的解。分析表明，ALNS 算法设计中包含的所有算子都能凭借其问题针对性，进而通过增强局部搜索或多样化搜索来为其整体性能做出贡献。

2.5 本章小结

本章针对具有多个时间窗口的车辆路径问题进行研究。建立了多时间窗的车辆路径问题(VRPMTW)模型，并改进了自适应大邻域搜索(ALNS)算法框架。通过设计基于破坏和修复算子的自适应选择邻域算子策略并完善 ALNS 算法框架，解决了搜索过程中邻域数量多、邻域选择缺乏指导的问题，增强了局部寻优能力。通过设置可以自适应地调整移除客户数量的移除池、允许不可行解参与迭代和定期重启策略，能够更好探索解空间。随后，在 VRPMTW 的基准测试集上测试了所改进的算法。实验结果表明，该算法总体上得到了较好的解，在 48 个算例中找
到了 31 个算例的新的最优解，并将所有测试算例的解质量平均提高了 0.80%。进一步的实验分析表明，所有针对 VRPMTW 问题设计的算子都通过增强集中性搜索或多样化搜索来提高求解质量，从而为算法性能做出了贡献。

第 3 章 考虑路径均衡的带时间窗车辆路径问题研究

3.1 引言

。司机作为配送方案的实际执行者，需要按照预先分配的路线逐个服
务路线上的客户，受客户分布的影响，各司机的工作量存在差异。因此，越来越多的路径优化问题开始考虑公平因素，并产生了考虑路径均衡的车辆路径问题(VRPRB)。

公平问题通常涉及公平分配司机的工作量和资源，其本质是围绕 VRPTW 模型中的路径要素开展路径规划。路径要素是配送网络要素的细化，以路径为核心要素的路径规划已出现在救灾物资配送和公益性物流等实际应用中，这些应用场景往往较少关注配送成本，而更关注路线的均衡程度，因此有必要对此类路径规划问题进行研究。

3.2 问题描述

VRPTWRB 的目标是综合考虑成本指标(总工作量)与公平指标(工作量的公平分配)，以实现更有利益包容性和人性化的配送方案。工作量的公平分配是指在$n$个司机(或路径，假设每位司机被分配一个路径)之间以尽可能公平的方式分配工作量或任务量。如图 3-1a)所示，均衡程度较好的配送方案能够较好地分配每位司机的工作量，包括行驶的总路程、服务的客户数等。而均衡程度较差的配送方案，司机的工作量存在较大差异，如图 3-1b)中的路线 1 和路线 3。因此，有必要研究工作量的公平合理分配，以充分照顾各配送司机的综合利益。从长远来看，公平合理的工作量方案有利于提高司机的工作积极性，从而有利于物流企业的运营与管理。

大多数 VRP 问题将基于总行驶距离的成本指标作为优化目标的核心组成部分，而公平指标的选择亦是本章研究的重点。对于这种考虑路径均衡的多目标优化问题，很明显，任何能实现公平分配的解都应该是工作量分配的帕累托最优解。然而，如果将路径均衡问题直接建模为一个 目标问题来求解，随着问题的目标维度的增加，经典的帕累托支配关系将难以发挥作用，带来“维度灾难”。因此，在处理路径均衡问题时，先要创建一个合理的公平指标，然后引入多目标优化算法来有效评估均衡程度。

通常，均衡或公平不是 VRP 的主要优化目标，但通过在单目标 VRP 模型中使用均衡或公平约束/目标拓展原始问题，将获得一系列帕累托最优折中解。因此，适当选择公平指标将具有与主优化目标相同的影响和研究价值。参考文献[57]中引入的均衡 VRP 的不同属性，将均衡模型分为三种类型的工作量资源：每条路径的行驶距离、装载量以及服务的客户数量。本章研究在考虑了时间窗约束之后认为，工作量资源还应加入持续时间(Duration)。

对于 VRP 模型，一些文献认为一条路径的行驶距离(TD)和持续时间(Duration)是相同的，本章认为这种认识不够严谨。时间窗约束不允许车辆在客户的时间窗关闭后提供服务，但车辆可以提前到达并产生额外的等待时间。等待时间的存在导致行驶距离不再与每辆车的总配送时间(工作量)成正比，因此，VRP 上的公平性指标不完全适用于 VRPTW 模型。

具体而言，在 VRP 的解中，车辆按顺序为客户服务，当考虑服务时间(即为客户服务的时间不为零)因素时，TD 和 Duration 本质上是不等价的。TD 是指车辆(路线)完成配送所行驶的总行驶距离，而 Duration 需要在每个客户处加上服务时间。换句话说，如果两辆车(两条路径)的 TD 相同，但服务更多客户的车辆的 Duration 值会更大，则 TD 和 Duration 不再等价。如图 3-2 所示，圆点代表客户，每个客户都标有编号和时间窗(中括号内)；方块代表仓库(0 号点)，两辆车分别从仓库出发和返回，形成路线 1 和路线 2；每条弧都标有距离，在大多数情况下，行驶时间和行驶距离的数值关系设定为 1:1。

在 VRP 模型中，路线 1 和路线 2 的 TD 值 相同(表 3-1 第 3 列和第 4 列)，但当服务时间不为 0 时，Duration 值不再同(表 3-1 第 5 列和第 6 列)。此外，在考虑时间窗约束后，Duration 的变化也受车辆到达客户时间的影响，即，如果车辆到达时间早于客户允许的最早服务时间，则必须在原地等待，从而产生等待时间。等待时间的出现使得 Duration 的计算变得更加复杂，所以 Duration 也可以用来衡量一条路线的公平性。

根据文献[57]对 VRP 平衡的研究方法，本章探索了 VRPTW 模型下的路线平衡问题。随着时间因素的加入，在公平性衡量标准中自然而然地包括与时间相关的数量。为充分利用现有的结论，本章重新划分了工作量资源和公平函数，将工作量资源分为两类：每辆车(路线)的行驶距离(TD)和完成配送所需的时间(Duration)。选择四个常用的公平函数，如表 3-2 所示。

本章的 VRPTWRB 问题的目标函数设为两个：第一个目标是最小化工作量资源，即最小化每条路线的行驶距离或完成时间；第二个目标是最小化路线间的不公平程度，分别使用上述的四个公平函数表示。

3.3 算法设计

本章基于改进的多向局部搜索(IMDLS)算法框架，并对原始 MDLS 算法的局限性做了改进，研究了 VRPTW 模型下的路线均衡问题。在以下部分中，3.3.1 节解释了原始的多向局部搜索(MDLS)算法及其不足；作为对原始 MDLS 的改进，3.3.2 节描述了改进的多向局部搜索(IMDLS)算法；3.3.3 节详述了限制存档大小、确定要探索的解的数量的策略；3.3.4 节讨论了计算自适应方向；最后，3.3.5 节介绍了作为算法局部搜索过程的大邻域搜索框架。

多向局部搜索(IMDLS)算法的基本步骤自查资料：

1. 初始化：生成一个初始解作为起点，该解可以是随机生成的，也可以是基于启发式规则生成的。初始解表示了车辆配送的路径安排。
2. 定义邻域结构：定义一种或多种邻域结构，用于在解空间中生成新的候选解。邻域结构定义了如何在当前解的基础上进行小的变动，以生成新的路径安排。常见的邻域结构包括交换两个客户点、插入一个客户点到现有路径中、删除一个客户点等。
3. 选择搜索方向：根据定义的邻域结构，选择多个搜索方向。这些方向代表了不同的路径变动方式，旨在探索解空间的多个区域。
4. 局部搜索：在每个选定的搜索方向上执行局部搜索。局部搜索使用适当的启发式规则或优化算法来找到给定方向上的最优解。这可以通过评估候选解的目标函数值来实现，如总成本或总行驶距离。
5. 接受准则：根据一定的准则决定是否接受新生成的候选解作为当前解。常见的接受准则包括接受更好的解（即目标函数值更优的解）或根据某种概率接受较差的解（如模拟退火算法中的Metropolis准则）。
6. 迭代过程：重复步骤3至步骤5，直到满足某个停止准则。停止准则可以是达到预定的迭代次数、解的质量在一定迭代次数内没有明显改进、或达到预设的时间限制等。
7. 输出结果：输出最终得到的最优解或近似最优解。这个解代表了车辆配送的最佳路径安排，以最小化目标函数值.

3.3.1 多向局部搜索

多向局部搜索(MDLS)是一种基于支配的多目标局部搜索[107]，它将局部搜索的概念扩展到多目标，并已应用于多目标组合优化问题，如电话叫车问题[108]，车辆路径问题[54]和火车装载计划问题[109]。MDLS 算法属于基于帕累托支配的多目标元启发式算法。为了找到当前解$x$ 的有效邻域解$x^{\prime }$ ，沿一个目标方向使用单目标局部搜索启发式。从初始解集$F$ 选取非支配解作为 MDLS 的起点。对于每次迭代中的所有目标，随机选择 $F$中的解$x$ ，并使用相应的局部搜索来生成$x$ 的邻域解$x^{\prime }$ 。随后，将 $F$中的解与非支配排序后的新邻域解合并，删除所有支配解，并更新$F$ 。MDLS算法最终返回非支配解集$F$.

⭐️疑问1：有效邻域解$x^{\prime }$是什么样子？
答案：这里的有效邻域解是指那些在某些目标函数上相对于当前解x有所改善，同时满足问题约束条件的解。具体来说，有效邻域解不一定需要在所有目标上都更优，而是至少在某个特定的目标方向上有所改进。这意味着算法在搜索过程中会权衡不同目标之间的折衷，并尝试找到那些在不同目标之间达到良好平衡的解。同时，这些解还必须满足VRP的约束条件，如车辆的容量限制、客户的需求满足等。
⭐️疑问2：为什么选取非支配解作为搜索起点？
答案：非支配解是指在多目标空间中，没有任何其他解在所有目标上都优于它的解。换句话说，非支配解在至少一个目标上是最优的，且在其他目标上至少与其他解一样好。因此，选择非支配解作为搜索起点有助于算法从一开始就关注那些在多个目标上表现良好的解。支配解在至少一个目标上比其他解差。算法可能会陷入局部最优。
⭐️疑问3：F是如何更新的？
猜测：因为是多目标的，对于每个目标，首先在F中随机抽取一个解$x$,然后基于该目标选择对应的搜索启得到邻域解$x^{\prime }$.将$x^{\prime }$放入F中，然后删除F中$x^{\prime }$支配的解，更新F.这样F始终保持是一个非支配解集。

上述文献中使用的 MDLS 有两个明显的局限性，严重影响了算法的求解效果。第一个局限性是 MDLS 在探索期间没有采取措施限制外部存档的大小，对整个外部存档中的解进行全面而完整的探索，并维护一个大的非支配集。该过程对过多解的耗尽式邻域探索导致算法收敛速度严重放缓并消耗大量的计算时间，这对于VRPTWRB 等复杂问题来说可能是不可接受的。第二个局限性是 MDLS 仅关注随机选择的解，并在每次迭代中进行改进。但这可能导致最终非支配集的收敛速度变慢和多样性变差。因此，有必要改进解的选择和探索策略。

本章进一步改进了 MDLS 方法，以更有效近似帕累托前沿。提出的 IMDLS 与 MDLS 有以下改进：
(1)确定每次迭代中要探索的解的数量$\alpha$，限制存档中解的数量上限(规模上限)$F_{max}$； 缺陷的变化
(2)选择要探索的$\alpha$个解$F_{\alpha }$ ，并确定搜索方向(主要是确定自适应方向)；
(3)沿着上一步确定的每个搜索方向对$F_{\alpha }$ 中的每个解进行局部搜索，以获得新的邻域解；
(4)使用改进超体积贡献指标(ICHV)来选择具有潜力的解。

3.3.2 改进的多向局部搜索

• 疑问1：第一目标是最小化行驶距离(或完成时间)，第二目标是最小化路线间的不公平程度(假设使用标准差)。在3.3 伪代码中第一黄色框中，如何向着单一目标进行具体的搜索呢？
  猜测：第一种是以目标为结果，随机做一个邻域变动，然后得到的结果要以单一目标优化了为新邻域解。第一种猜测是确定某种对应的搜索算子，比如第一个目标对应是最大破坏和贪婪修复算子的结合，第二个目标对应着在最大一条路线中移除节点插入到最小的路线中的算子。
• 疑问2：支配规则？
  答案：解x1在目标1和目标2上都比解x2小，更优。则选择解x1而舍弃解x2.
• 待求证的细节：
  1. 选取$\alpha$个解，$\alpha$值的变化规则
  2. 自适应方向如何确定？
  3. 如何计算HI(f)?

IMDLS 算法以非支配集F及其规模上限$F_{max}$ 作为输入，通过对每个目标$t(t\in T)$求解数轮并应用支配规则得到初始非支配解集。具体来说，