通过学习增强的列生成方法快速重新优化车辆路径规划，同时考虑驾驶员休息时间安排

《TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW》：Rapid re-optimization via learning-enhanced column generation for vehicle routing with driver break scheduling

　　宁雪|崔天祥|史成
诺丁汉大学计算机科学学院，中国宁波
中国浙江省宁波市太康东路199号，315100

**摘要**
在世界许多地区，道路货运运输行业受到关于驾驶员工作时间的严格法律规定的约束。这些规定为制定实用且高效的调度方案带来了重大挑战。车辆路线规划和驾驶员休息时间安排的同步优化构成了一个复杂的计算问题。在实践中，许多实际的车辆路线问题需要定期规划，并且必须能够适应突然的需求变化；这就需要具备高效的重新优化能力。本文提出了一种用于带有驾驶员休息时间安排的车辆路线规划的快速重新优化框架，以满足这一需求。我们的方法将列生成算法与专门为快速优化设计的机器学习启发式方法相结合。我们使用两组基准实例（一组基于合成数据，另一组基于真实数据）来评估所提出的方法在欧盟法规（EC）561/2006和指令2002/15/EC下的性能。结果表明，采用机器学习增强的方法比不使用机器学习预测组件的方法快得多，运行时间减少了96%以上（仅需几秒钟），同时路线成本增加了不到2%，最终解决方案与估计的下限之间的差距为2.7%。

**1. 引言**
对卡车和公共交通驾驶员的驾驶及工作时间进行监管是公共政策的重要组成部分，旨在提高城市流动性并确保乘客和货物运输的安全。这些规定在世界各地的许多司法管辖区都得到执行，旨在减轻与驾驶员疲劳相关的风险，从而促进更安全、更高效的运输系统。例如，在欧盟和英国，法规如（EC）561/2006和2002/15/EC对驾驶时间设定了严格限制，并规定了休息时间。同样，在澳大利亚，实施了标准工作时间、基本疲劳管理和高级疲劳管理框架来规范驾驶员疲劳。新西兰的《道路法》中的工作时间要求以及美国的《服务时间规定》也规定了类似的指导方针，对不合规行为有严厉的处罚，这凸显了全球对安全和运营效率的重视。在中国，也有针对长途客运车辆、旅游客车和货运卡车的具体休息时间规定。例如，驾驶员连续驾驶超过四小时后必须至少休息20分钟。这些措施对于保持驾驶员警觉性和减少事故发生的可能性至关重要，从而有助于提高城市流动性。

同时解决路线规划和优化驾驶员休息时间安排问题是一个重大的计算挑战。根据（EC）561/2006法规，驾驶员休息时间分为两部分：首先是15分钟的休息时间，然后是30分钟的休息时间。如果允许分段休息，单次行程可能需要多达四次休息，这使得可能的调度组合数量增加到O(n^4)，其中n表示路线上的访问次数。这种复杂性还因需要符合指令2002/15/EC关于工作时间的规定而加剧，因为休息时间安排必须同时满足这两个法规的要求。

在本文中，由于城市物流规划的短期性质（通常涉及次日的路线优化，尤其是为了满足重新优化的需求，这通常将规划范围限制在几小时内），因此案例研究的监管框架同时参考了（EC）561/2006法规和指令2002/15/EC。然而，本文提出的算法也适用于其他法规。简而言之，（EC）561/2006法规为驾驶员的驾驶时间和强制休息时间设定了标准，而指令2002/15/EC则规定了工作时间要求，包括其中规定的强制休息时间。在其他地区，类似的法规可能有不同的名称。为了清晰和通用性，在本文中，“驾驶休息时间规定”指的是（EC）561/2006法规下的休息时间要求，“值班休息时间规定”指的是指令2002/15/EC下的休息时间义务。一般来说，驾驶休息时间规定为驾驶时间和强制休息时间设定了标准。对于单日的调度，这些规定指定了每天最多9小时的驾驶时间，并要求每驾驶4.5小时后至少休息45分钟，同时允许将休息时间分成更小的间隔。值班休息时间规定管理驾驶员的工作时间，包括驾驶和其他与工作相关的活动。它们规定工作6小时后至少休息15分钟，6至9小时的工作期间休息30分钟，以及超过9小时的工作期间休息45分钟。关于这些规定的更多细节可以在Xue等人（2025a）的研究中找到。

在传统的路线问题（如取货和送货问题（PDP）、叫车问题（DARP）和车辆路线问题（VRP）的基础上，广义取货和送货问题（GPDP）（Savelsbergh和Sol，1995）提供了一个更现实的物流运营建模框架。与这些假设固定仓库的简单变体不同，GPDP处理车辆可能有不同的起始和结束位置的情况，以及货物可能需要多个取货或送货点的情况（Gómez-Lagos等人，2022）。其目标是找到满足所有运输需求的路线解决方案，同时保持每个货物的完整性。GPDP处理复杂约束的能力使其在实际应用中更加现实，尽管计算难度大于传统的路线问题（Wang等人，2023）。

许多GPDP和驾驶员休息时间安排问题需要重复或定期的安排，这在各个行业中都很常见。例如，超市和便利店定期从供应商处接收货物，而啤酒厂按照固定时间表向酒吧运送新鲜啤酒并收集使用过的桶进行回收。在电子商务中，像亚马逊这样的公司处理预订单商品的重复配送，快餐连锁店也频繁推广和分发他们的产品。同样，共享单车公司也定期将自行车重新定位到不同的地点以满足需求。这些用例表明，反复解决GPDP是一个常见且普遍的运营需求。然而，即使有一组稳定的常客，运营计划也很少是静态的。需求量可能会大幅波动，临时变更或紧急请求也经常在短时间内发生。因此，初始的定期计划通常需要快速高效的重新优化，以保持可行性、成本效益和合规性。有效应对这些挑战对于降低运营成本、提高服务质量以及确保客户满意度至关重要，这是现代供应链管理的关键焦点。从运营规划的角度来看，调度员通常会将熟悉的路线或区域分配给经验丰富的驾驶员，因为他们能够在已知路况下更高效地导航并与常客互动（Quirion-Blais和Chen，2021）。此外，一致的休息模式为驾驶员在安排饮食和选择休息地点方面提供了灵活性，从而提高了运营效率和工作的满意度（Kraul等人，2024）。

图1展示了实际车辆路线和休息时间安排问题中12小时周期内的驾驶员轮班安排。每个轮班都有其开始时间、结束时间和休息模式（由分配给车辆上驾驶员的每次休息的开始时间和持续时间定义）。图2展示了少于12小时的轮班的几种常见休息模式。在图1中，横轴代表轮班ID，纵轴表示解决方案中每个轮班的频率。该图展示了通过将客户需求随机调整±30%从原始问题实例中获得的解决方案。原始需求场景和修改后需求场景中ID相同的轮班（尽管频率可能不同）都被绘制出来；不匹配的轮班被排除在图中，从而在它们应该出现的位置留下了空白。这些结果表明，即使需求变化高达30%，解决方案之间也存在显著的相似性。这表明，对于路线和驾驶员休息时间安排问题来说，预测并修复在需求波动下仍然稳定的部分解决方案是可行的，这与Morabit等人（2024）报告的结果一致。通过在优化过程之前向求解器提供这些预先确定的模式，我们可以提高计算效率并更快地收敛到最优解。

**下载：** 下载高分辨率图像（596KB）
**下载：** 下载全尺寸图像
图1. 需求变化30%时的轮班比较。
**下载：** 下载高分辨率图像（284KB）
**下载：** 下载全尺寸图像
图2. 驾驶员休息模式示意图。

最近的算法进展解决了物流中的动态调度挑战，包括蒙特卡洛方法（Okulewicz和Mándziuk，2020）、马尔可夫决策过程（Zhang等人，2023）和强化学习方法（Zhou等人，2023）。尽管有这些发展，现有研究很少考虑路线和驾驶员休息时间安排的同步快速重新优化。尽管研究表明数据驱动的优化在解决动态路线问题方面具有巨大潜力，但由于对可解释性的担忧、调试不满意解决方案的难度以及实施全新框架的高成本，物流公司在实践中采用这些方法的步伐较慢。因此，改进当前部署的方法（如启发式算法或基于数学规划的方法）以实现快速重新优化而不需要进行重大基础设施变更非常重要。

据我们所知，现有的路线和驾驶员休息时间安排方法没有充分解决现实世界物流操作的重复性，也没有提供针对突然需求变化的快速重新优化机制。这一差距突显了需要利用历史模式来提高计算效率的先进解决方案方法。在实践中，许多路线和休息时间安排问题必须反复解决，例如每天甚至更短的时间间隔内，其中只有数据（而不是问题结构或目标）在每次实例之间发生变化。

为了解决上述挑战，包括（1）路线和驾驶员休息时间安排的计算复杂性，（2）对需求波动的快速重新优化需求，以及（3）对可解释性和可调试性的担忧，我们提出了一种基于机器学习的启发式列生成方法。这种混合方法利用历史专家生成的调度来快速识别在需求变化时保持不变的稳定解决方案组成部分。此外，它利用数学规划中的双重值来指导启发式搜索，以找到有希望的解决方案；其思想是利用严格的数学规划获得的信号来高效地引导启发式搜索，从而加快收敛速度。具体来说，本文的主要贡献如下：
1. **机器学习增强的启发式列生成**：我们提出了一种用于GPDPTW-DBS的机器学习增强型列生成框架，该框架利用线性规划松弛中的双重值来启发式指导邻域搜索，显著加快了优化过程。
2. **稳定解决方案组件的预测**：我们的方法利用机器学习来识别接近最优解中的持久路线边缘和休息模式。这使得重新优化过程能够专注于受需求波动影响的区域，而不是从头开始生成完整的解决方案。
3. **通过变量固定减少搜索空间**：我们通过策略性变量固定来降低计算复杂性，采用双重方法：（1）固定预测的稳定路线边缘以缩小解决方案空间；（2）预测高级休息策略，从中得出休息模式，从而减少更新时间标签所需的计算时间。

我们的方法通过将机器学习与现有的优化范式（例如MIP求解器和启发式方法）相结合，弥合了理论进展和实际物流应用之间的差距。这使得实际解决方案时间缩短，可解释性提高，实施成本可控，这些都是之前限制数据驱动方法在行业中采用的关键因素。此外，所提出的框架可扩展到其他领域的各种重复优化问题，只要历史解决方案模式可以指导未来的决策。

本文的其余部分结构如下：第2节提供了相关文献的全面回顾。第3节详细描述了所研究的问题。随后，第4节介绍了为解决问题而开发的列生成公式。第5节详细阐述了所提出的解决方案框架。第6节讨论了实验分析和结果。最后，第7节总结了关键发现及其意义。

**2. 文献回顾**
本节回顾了与我们研究最相关的工作，重点关注两个相互关联的研究方向。首先，我们研究了结合驾驶员休息时间规定的车辆路线方法。其次，我们回顾了学习增强型列生成（CG）领域，该领域旨在提高CG在大规模调度中的效率和可扩展性。3. 问题定义
GPDPTW-DBS（车辆路径规划与驾驶员休息时间调度）可以在有向图G=(N,A)上定义，其中N=P∪D∪W表示节点集，A表示连接这些节点的弧集。在这里，P 是所有取货地点的集合，D 代表所有送货地点，W=M+∪M? 表示车辆的起始和结束地点集合。每条有向边 (i, j) ∈ A 都有一个从点 i 到点 j 的行驶时间 δij。请求 k ∈ K 表示为一对节点 (p, d)，其中 p ∈ P 且 d ∈ D，表示货物必须从 p 运送到 d。每个节点 i ∈ N 都有一个时间窗口 [ei, li]，其中 ei 表示最早可能的开始时间，li 表示最晚允许的开始时间。车辆可以在 ei 之前到达并等待服务开始，但不得在 li 之后到达。节点 i 的需求量用 qi 表示，对于每个请求 (p, d)，有 qp ≥ 0 且 qd = ?qp。一个可行的解决方案包括一组选定的路线 R ? Ω，这些路线满足所有（或几乎所有）客户请求。每条路线 r ∈ Ω 表示一个有序的访问序列 {0, 1, …, n?1}，并附带一个休息时间表，每个休息时间由开始时间和持续时间定义。路线 r 的休息时间表可以正式表示为 Br = {(sb, db) | b = 1, …, |Br|}，其中每对 (sb, db) 表示时间表中第 b 次休息的开始时间和持续时间。解决方案受以下约束：
- 所有服务必须在每个地点的指定时间区间 [ei, li] 内完成。
- 在每条路线 r 的整个过程中，总负载必须满足 ∑i ∈ r qi ≤ Q。
- 对于每个请求 k = (pk, dk) ∈ K，访问顺序必须满足 ψ(pk) < ψ(dk)，其中 ψ(i) 表示节点 i 在路线中的位置。
- 每对取货-送货地点 (p, d) 必须由同一条车辆路线服务。
- 每条车辆路线 r 必须从其起始仓库 M+ 开始，并在其目的地仓库 M? 结束。

GPDPTW-DBS 的目标是最小化总成本，即所有选定路线 r 的成本 cr 之和。路线的成本 cr 通过总工作时间来衡量。对于一条有 n 次访问的路线，总工作时间计算为 a7?a0，其中 ai 表示到达地点 i 的时间。

为了说明休息时间安排如何影响 GPDPTW-DBS 中路线的可行性和效率，图 3 比较了同一组取货-送货请求 k ∈ K 在单条车辆路线 r ∈ Ω 上的两种不同的休息策略。这条路线包括 n=8 次有序访问（节点 {0, 1, 2, 3, 4, 5, 6, 7}。它从起始仓库（节点 0）开始，结束于目的地仓库（节点 7）。水平时间轴跟踪两种任务类型的执行：取货任务（即访问 1、3、5 处的向上箭头）和送货任务（即访问 2、4、6 处的向下箭头）。行驶时间在连续访问之间累积。

**下载：** 下载高分辨率图像（253KB）
**下载：** 下载全尺寸图像

**图 3. GPDPTW-DBS 路线执行的示意图。**
第一个时间表（顶部）遵循法规 (EC)561/2006 要求的合规驾驶员休息策略。在累计行驶 4.5 小时后，完成了访问 0–4（对应于两个取货-送货请求），驾驶员休息了两次：Br = {(s1=14:00, d1=30), (s2=14:30, d2=30)}。这些休息时间安排在节点之间，不对应于任何特定节点。第一次 30 分钟的休息是指令 2002/15/EC 要求的，该指令规定工作 6 小时后必须休息 30 分钟。这里，驾驶员从 8:00 工作到 14:00，达到了 6 小时的阈值。再行驶 30 分钟后，安排了第二次 30 分钟的休息。这第二次休息是法规 (EC) 561/2006 要求的，该法规规定每行驶 4.5 小时后必须休息 45 分钟。该法规允许两次较小的休息：一次至少 15 分钟，另一次至少 30 分钟。由于驾驶员已经休息了 30 分钟，第二次 30 分钟的休息满足了这一要求。休息后，驾驶员继续驾驶以完成访问 5–6（另一个请求），并在 17:30 到达终点（节点 7）。总工作时间（路线成本 cr）为 a7?a0=9.5 小时。

如图 3 中的第二个时间表（底部）所示，这个时间表可以改进。在完成相同的初始访问 0–4 后，将分段休息替换为一次 45 分钟的驾驶员休息：Br = {(s1=14:00, d1=45)}。这次单次休息同时满足了所有法规要求，并减少了停机时间。它允许驾驶员完成访问 5–6，并在 17:15 到达终点。总工作时间为 a7?a0=9.25 小时。改进的原因是，当工作时间达到 6 小时时进行的 45 分钟休息也根据法规 (EC)561/2006 重置了驾驶小时计数器。因此，在行驶 4.5 小时后不再需要额外的 30 分钟休息。

这个例子表明，虽然休息时间表 Br 必须遵守法规要求，但其模式直接影响总工作时间，而这正是 GPDPTW-DBS 的目标。它还强调了在可行路线中灵活安排休息时间的价值，可以在访问之间插入休息时间以提高效率。

**4. 带有驾驶员休息时间限制的列生成公式化**
列生成（Column Generation，CG）被认为是一种解决各种优化问题（如路由和调度）的精确算法。该方法通过迭代操作，交替执行两个核心步骤：（1）解决原始线性松弛问题的简化版本，称为受限主问题（Restricted Master Problem，RMP，第 4.1 节讨论）；（2）解决定价子问题（第 4.2 节解释），该问题旨在发现具有负减少成本的新列（用于最小化目标），并将其纳入 RMP。当无法再找到改进的列时，CG 过程结束。

CG 在处理大规模线性规划问题时特别强大，特别是那些嵌入在分支定价框架中以解决整数规划问题的问题。这一特性使其成为第 4.1 节中概述的问题的理想选择，因为在这种情况下，可行路线集非常大，导致模型具有大量的列，尽管最优解通常只依赖于其中的一小部分。

在车辆路由的背景下，CG 是一种精确方法，其定价问题可以建模为具有资源约束的基本最短路径问题（Elementary Shortest Path Problem with Resource Constraints，ESPPRC）。然而，对于大规模实例，尤其是重新优化设置中，解决 ESPPRC 在计算上是禁止性的，因为计算效率非常重要。为了加速这一过程，我们采用了启发式列生成策略。这种方法的动机有两个关键见解：首先，能够高效地重用之前解决方案中的高质量列（路线）；其次，利用从 RMP 获得的对偶值来有效指导启发式搜索。与可能表现出不受控制的随机性的纯启发式方法不同，这种对偶指导确保了对解决方案空间的有针对性探索，从而生成最有可能改善目标函数的列，从而显著加快收敛速度，而不会大幅牺牲解决方案质量。模型公式化中使用的符号在表 2 中提供，默认配置遵循驾驶员休息时间和工作休息时间的规定。此外，澳大利亚（标准小时 (SH) 和基本疲劳管理 (BFM)）以及新西兰（工作时间要求 (WTR)）的驾驶员休息时间规定在附录 A.1 中概述。

**表 2. 问题公式化中使用的符号。**
| 符号 | 描述 |
|-----------------|-------------------------------------------|
| K | 交通请求集合 |
| N | 所有节点（地点）集合 |
| A | 连接节点对的弧集合 |
| B | 休息点集合 |
| Ω | 所有可行路线集合 |
| V | 可用车辆（车队）集合 |
| λr | 表示路线 r 是否被选中的二进制变量（1 表示选中，0 表示未选中） |
| akr | 表示请求 k 是否由路线 r 服务的二进制参数（1 表示服务，0 表示未服务） |
| xij | 表示弧 (i, j) 是否在路线中使用的二进制变量（1 表示使用，0 表示未使用） |
| ai | 节点 i 的到达时间 |
| lb | 自上次休息时间重置以来在休息点 b 的累计工作时间 |
| lb | 自上次驾驶重置以来在休息点 b 的累计行驶时间 |
| lbreak|work1st | 分配工作休息的第一个阈值之前的总休息时间 |
| lbreak|work2nd | 分配工作休息的第二个阈值之前的总休息时间 |
| Δbreak | 单次连续休息的持续时间 |
| Δ1break | 分段休息的第一部分的持续时间 |
| Δ2break | 分段休息的第二部分的持续时间 |
| cr | 路线 r 的总工作时间，计算为 a7?a0 |
| cij | 弧 (i, j) 之间的工作时间 |
| πk | 来自主问题的对偶值，对应于请求 k |
| ν | 来自主问题的对偶值，对应于车队规模约束 |
| ei | 节点 i 的最早到达时间 |
| li | 节点 i 的最晚到达时间 |
| δij | 节点 i 和 j 之间的行驶时间 |
| lbreak|drive | 不休息的最大行驶时间（默认：270 分钟） |
| dutyBreakRequirement1 | 6-9 小时工作所需的最小休息时间（默认：30 分钟） |
| dutyBreakRequirement2 | 超过 9 小时工作所需的最小休息时间（默认：45 分钟） |
| lbreak|work1st | 分配工作休息的第一个阈值 |
| lbreak|work2nd | 分配工作休息的第二个阈值 |
| lbreak | 休息的最小持续时间（默认设置为 45 分钟） |
| lbreak|1st | 分段休息的第一部分的最小持续时间 |
| lbreak|2nd | 分段休息的第二部分的最小持续时间 |
| qi | 节点 i 的需求量（取货为正，送货为负） |
| Q | 车辆容量 |

该问题的列生成框架由两个相互连接的组件正式定义：主问题和定价子问题。主问题在第 4.1 节中详细说明，它是一个线性松弛问题，从受限池中选择最优路线组合以最低成本满足所有请求。为了改进这个解决方案，解决定价子问题（第 4.2 节描述），以生成新的、具有负减少成本的成本效益路线，然后将其添加到下一次迭代的 RMP 中。这个迭代过程持续进行，直到找不到更多改进的列，表明线性松弛达到最优。

**4.1. 主问题**
假设我们给定了所有可行路线 Ω 的集合，可以使用以下集合划分公式来建模问题：
(1) min∑r∈Ω crλr
(2) s.t. ∑r∈Ω akrλr=1 ?k∈K
(3) ∑r∈Ω λr≤|V|
(4) λr∈{0,1} ?r∈Ω

在这个模型中，二进制决策变量 λr 表示是否选择了可行的路线 r ∈ Ω（λr=1）（λr=0）。目标函数 (1) 最小化所有选定路线的累计持续时间。系数 akr 是二进制参数，表示特定交通请求 k 是否由路线 r 服务（akr=1）（akr=0）。因此，约束 (2) 确保每个请求 k 都被恰好一条路线覆盖。约束 (3) 限制了选定路线的数量，使其不超过可用车辆车队 |V| 的大小。最后，约束 (4) 强制决策变量的二进制性质。

**4.2. 定价子问题**
路线 r 的减少成本由以下公式给出：
c′r = cr?∑k∈K πkakr?ν，其中 cr=∑(i,j)∈rcij 是路线 r 的总成本，akr=1 表示路线 r 服务请求 k，πk 是主问题分区约束对应于请求 k 的对偶值，ν 是与车队规模约束相关的对偶变量。

**5. 提出的解决方案框架**
在解决 RMP 的第一次迭代之前，对偶信息不可用，因此需要一组初始列（路线）来启动程序。在将线性规划松弛（LPR）求解到最优后，利用对偶值来计算定价子问题中路线的减少成本。初步实验表明，解决 RMP 占用了大部分计算工作。为了提高收敛速度，算法被调整为在每次迭代中包含多个具有负减少成本的路线，这种方法与先前的研究（Xue 等人，2021 年）一致。由于定价问题是在列生成框架内迭代解决的，因此采用高效的解决方案策略至关重要。

为了最优地解决定价问题，我们可以采用动态规划方法，将其建模为 ESPPRC，如 Goel 和 Irnich（2017 年）以及 Goel（2018 年）所提出的。这些方法可以在列生成方案内提供可证明的最优解，确保分支定价算法所需的强下界。然而，这种最优性保证会带来显著的计算成本。状态空间和资源约束，特别是对于复杂的服务时间规则，可能会导致标签数量的指数级增长。这限制了其在大规模或实时场景中的适用性。如前所述，本文的主要目标是优先考虑快速重新优化，这需要在最优性和效率之间进行权衡。因此，我们根据我们的具体问题背景修改了 Goel（2018 年）中的 ESPPRC，作为评估其他方法的可靠基准。这个定制的ESPPRC（详见附录中的A.1节）将作为评估我们本文提出方法的基准。鉴于最优性和计算可行性之间的平衡，我们推荐使用Xue等人（2021年）提出的元启发式技术来解决定价问题。这一选择是基于需要在高效的元启发式框架内处理路由和司机休息调度的综合复杂性的需求。列生成过程基于RMP迭代次数的预定义限制而终止，从而在计算效率和解决方案质量之间达到一种有意的平衡，并持续迭代直到满足停止条件。最后，为了得到整数解，在RMP的最终解决过程中重新施加对λr的放宽约束。整个解决方案框架如图4所示，随后提供了逐步解释。

下载：下载高分辨率图像（148KB）
下载：下载全尺寸图像
图4. 提出的列生成过程框架。

5.1. 初始路线集
为了生成这个初始路线集，我们使用了一种直接的路线初始化技术。创建基本路线集的一个基本要求是确保每个取货和送货请求至少被一条路线覆盖。最基本的策略是为每个请求构建一条专用路线，其中一辆未装载的卡车从起点仓库出发，前往取货点，将货物运送到指定的交货地点，最后返回目的地仓库。司机休息时间表是使用Xue等人（2025a）提出的合规调度方法生成的，该方法确保完全遵守驾驶和值班时间规定。然而，这种方法可能会导致在车辆数量限制方面出现不可行的解决方案。为了解决这个问题，我们最初将可用车辆的数量设置为问题实例中的请求数量。随着列生成过程的进行，卡车数量逐渐减少，以与每次RMP迭代中生成的列数量相匹配，从而保持可行性并提高后续解决过程的效率。

5.2. 边缘固定
设Po和So分别表示原始问题实例及其对应的解决方案。对于原始问题Po的一个扰动实例Pm，我们的目标是确定已知解决方案So中的哪些组成部分在未知解决方案Sm中仍然存在，以避免完全重新优化。设E为包含So中使用的所有弧的边集。目标是预测哪些边e∈E有很高的概率成为Sm的一部分。这里，边e被定义为两个请求之间的连接。通过固定这些边，我们旨在显著降低问题的复杂性，从而大大减少所需的计算时间。

我们训练了一个监督二元分类模型，记为MLE，该模型可以预测边在修改后问题实例中保留的概率。第一步是收集足够的训练数据。学习模型MLE的训练过程如图5所示。给定原始实例和修改实例及其解决方案的元组（Po, So, Pm, Sm），构建了一个标记数据集D={{Xe, ye}∣?e∈E(So)}。D中的每个条目代表原始解决方案中的一条边，其中Xe∈Rn对应于边的特征向量，n是特征的数量，ye∈{0, 1}是二进制标签，表示该边是否属于Sm。

由于需要生成大量修改后的实例及其对应的解决方案对，使用精确方法是计算上不可行的。因此，我们采用了Xue等人（2025a）提出的启发式求解器，该求解器基于局部搜索和大邻域搜索方法的组合。由于这是一个监督学习问题，因此需要So和Sm两个解决方案来构建数据集。标签是通过检查So和Sm中的边之间的重叠来分配的，具体如下：
ye={1 if e∈(E(So)∩E(Sm)), 0 otherwise。
特征向量Xe捕捉了每条边的特征。为了识别相关特征，我们参考了Arnold和S?rensen（2019年）以及Morabit等人（2024年）的工作进行了广泛的特征工程过程。我们首先创建了一组潜在特征的全面集合来捕捉边模式的独特特征，然后使用递归特征消除（RFE）方法对选择进行了优化。

本研究优先考虑简洁性和问题对齐性，而不是包含所有特征。有几个潜在相关的特征，如路线长度和边上的车辆负载，因为三个主要原因被省略了。首先，这些特征的重要性较低，在RFE过程中由于对分类器性能的贡献最小而被剔除。其次，重新优化仅涉及需求的变化，而常规客户位置、车队规模和车辆容量保持不变。因此，许多候选特征要么不相关，要么是多余的，因为它们已经被现有的特征（如边成本和空间坐标）所捕获。最后，分类器关注的是边级别的预测，而不是路线级别的属性。这种方法需要避免引入依赖于其他边的特征，从而保持预测任务的简单性和独立性。最终，选择了以下关键特征：
- 交付节点dk∈D（请求k的结束位置）和取货节点pl∈P（请求l的开始位置）的（x, y）坐标，对于请求k, l∈K；
- 边（i, j）∈A的成本cij；
- 节点（pk, dk）和（pl, dl）对于请求k, l∈K的旧需求和新需求；
- 仓库边的二进制指示器（如果i或j是仓库节点，则为1，其中（i, j）∈A）；
- 需求变化的二进制指示器（如果请求k, l的需求或两者都有变化，则为1，其中k, l∈K）；
- 根据邻居距离确定的dk相对于pl的排名（例如，如果pl是dk的最近邻居，则排名为1）；
- 弧线交叉的二进制指示器（如果弧线（pk, dk）与弧线（pl, dl）相交，则为1）。

选定的特征有效地支持了在取货-送货路由重新优化过程中边保留或修改的预测。在这种情况下，取货（pl）和送货（dk）位置保持不变，而需求发生了变化。这些特征关注影响边稳定性和对变化响应性的核心因素。诸如dk和pl的（x, y）坐标以及这些节点之间的邻居距离排名等空间细节，捕捉了固定的地理邻近性。连接地理位置接近的取货点和送货点的边不太容易受到需求变化的影响，因为它们的空间效率保持一致。边成本cij直接反映了路线的最优性，确保了低成本的边被优先保留，这对于最小化总旅行费用至关重要。

pk, dk, pl, 和 dl的旧需求和新需求，加上需求变化的二进制指示器，隔离了问题中的主要动态扰动。这些特征识别出与需求发生变化的请求相关的边，这些边有更高的被移除风险，以及需求稳定的边，这些边更有可能被保留。仓库边的二进制指示器考虑了结构约束，认识到连接到仓库的边本质上更稳定，因为所有路线都必须从仓库开始或结束。此外，弧线交叉的二进制指示器解决了实际的路由挑战。相交的弧线，如（pk, dk）和（pl, dl），可能会引入效率低下，因此这个特征有助于识别即使在空间或需求属性看似稳定时也需要通过重新优化进行调整的边。

5.3. 休息策略固定
应用学习到的启发式来固定休息策略的核心概念是预测在不同路线中可能保持一致的司机休息时间表。通过识别这些稳定组件，可以直接应用休息策略，消除了在整个路线上频繁回溯和更新时间相关变量的需要。这减少了搜索空间并加快了解决过程。这种方法利用了先前解决方案的洞察力，使得稳定休息模式的复用成为可能。固定这些模式显著降低了问题的复杂性，从而显著减少了计算时间。

设B表示已知解决方案So中包含的司机休息集合。我们的目标是预测给定路线r∈Sm的休息策略b∈B。Xue等人（2025a）提出了一种合规的司机休息调度方法，以及两种旨在通过策略性地调整重置驾驶时间来优化路线持续时间的先进策略。这些策略如下所述：
- 策略1：当累积休息时间达到初始阈值lbreak|work1st=30分钟时，如果任何休息序列导致Libreak|work1st<45分钟（无论是通过一个30分钟的休息还是多个15分钟的休息），则必须将dutyBreakRequirement1从30分钟增加到45分钟。
- 策略2：如果累积休息时间达到次要阈值lbreak|work2nd且休息次数满足|B|>1，则必须将dutyBreakRequirement2从45分钟增加到60分钟。

策略1和2对应的休息调度方法在图6中以视觉方式表示。在图中，圆形节点表示客户访问，而方形标记表示计划的司机休息。从初始的合规调度开始，当存在多个休息时，过程会产生新的分支，修改第一个休息并沿路线向后传播时间调整。当合规调度过程产生的解决方案包含超过两个休息（|B|>2）时，算法会自动调用策略2。

算法的详细信息在Xue等人（2025a）中提供；为了本文的完整性，主要逻辑过程如下。该过程首先评估是否需要初始的值班休息，其持续时间为dutyBreakRequirement1，当累积工作时间超过第一个阈值lbreak|work1st时触发。系统还验证调度中是否有足够的时间来容纳这个暂停而不会发生冲突。如果满足这些条件，休息将被正式插入司机的行程中。安排这个休息会导致延迟，随后将整个剩余的工作时间线向后移动休息的持续时间（dutyBreakRequirement1）；这确保所有未来的计算都基于更新后的、现实的调度。之后，对下一个值班休息的持续时间dutyBreakRequirement2进行第二次评估。此评估使用新调整的时间线来检查工作时间是否也超过了第二个阈值lbreak|work2nd，并确认有足够的时间安排这个更长的中断。

为了解决违规问题，程序会插入额外的司机休息。它使用合规调度作为默认值，但根据具体条件可能会分支到策略1或策略2。插入过程从发生扰动的节点开始（例如，时间窗口的变化），即使当前解决方案在该点仍然是可行的。然后从该节点开始重新计算和更新所有后续的时间相关变量，因为调度更新具有向前传播的性质。当结果路线r′的持续时间比路线r短，同时两条路线都满足各自访问的时间窗口约束时，一组休息B′会支配另一组休息B。

如前所述，尽管司机休息优化算法通过选择性评估时间相关变量展示了效率，但由于固有的重复计算，它仍然计算密集。如图6所示，当满足两个条件时，算法将dutyBreakRequirement2从45分钟增加到60分钟：（1）达到次要休息时间阈值；（2）有多个休息（|B|≥2）。这样的调整要求重新计算前面节点的时间变量，从而产生计算效率低下。我们提出的机器学习框架旨在大幅减少这种开销。具体来说，我们采用了一种带有三元分类模型MLE的监督学习方法。准备训练数据的过程与图5中所示的过程相同，遵循第5.2节描述的方法。目标是预测休息策略（合规、策略1或策略2），并据此生成最合适的休息模式，这些模式很可能是路线的一部分，而不是在每个节点更新标签（与值班时间和驾驶时间相关的标签，如Lbdriving, Lbbreak|work1st, 和 Lbbreak|work2nd），并检查是否满足切换到不同休息策略的条件。需要澄清的是，虽然我们将这种方法称为“休息策略修复”，但机器学习预测的重点是休息策略本身，而不是直接的休息模式。这是因为一个休息策略可以产生多种休息模式，正如Xue等人（2025a）所展示的那样。由于有两种休息策略，加上合规的日程安排，总共有三类情况，我们采用了三元分类模型（合规、策略1或策略2）来预测休息策略。为分类器MLB选择的特征旨在通过捕捉控制驾驶员休息的核心时间和监管约束来预测最佳的休息调度策略。与边缘修复场景不同，在边缘修复场景中，训练数据中的类别平衡与解决方案的相似性密切相关（详见第6.2.1节），而休息策略修复的训练数据是经过精心策划的，以确保三种策略标签之间的分布平衡，从而减少潜在的模型偏差并提高学习效率。特征集是根据路线的演变状态构建的，以直接反映法规（EC）561/2006和指令2002/15/EC的规定：

- 总路线时长
- 在第一次休息期间的驾驶/非驾驶时间
- 在第二次休息期间的驾驶/非驾驶时间

这些特征共同根据这两个相互关联的法规来模拟驾驶员的状态。基于驾驶时间的特征直接决定了对驾驶休息规则的遵守情况，而基于工作时间的特征则控制了休息要求。

5.4. 增强机器学习的启发式列生成器
定价子问题原则上可以像ESPPRC一样精确地制定和解决。然而，对于大型实例来说，这种精确方法在计算上是不可行的，这将在第6.1节的实验结果中得到证明。相反，在商业路线规划应用中通常采用启发式方法（Hall和Partyka，2016），因为它们在处理复杂的实际约束（如驾驶员休息调度）时具有可扩展性和灵活性。尽管效率较高，但简单的启发式方法往往无法一致地产生具有负成本减少的高质量列。此外，如第1节所示，即使需求变化高达30%，路线安排之间仍然存在显著相似性，这表明预测和修复在需求波动下仍然稳定的部分解决方案是可行的。

为了克服这些挑战，我们采用了混合的增强机器学习的启发式列生成器。首先，训练机器学习模型进行边缘预测（MLE）和休息策略预测（MLB），识别出在空间上高效、符合监管要求且对需求扰动具有鲁棒性的解决方案结构元素。虽然这些预测的组件并不保证会出现在每个最优解中，但它们通常提供了一个框架，显著减少了搜索空间。然后，在我们方法的后续部分中可以逐步细化这个框架。其次，整合了一个双导向的VNS元启发式算法。使用元启发式算法来寻找具有负成本减少的列在许多研究中已经证明了其有效性，例如Xue等人（2021）。在这项工作中，VNS邻域函数被特别设计为在双值合理的情况下允许偏离机器学习预测。在每次RMP迭代中，双导向的VNS系统地探索邻域，利用当前LP松弛的双值来适应性地细化候选解决方案。这种机制确保算法保持灵活性，适应优化环境，并避免过度依赖可能次优的机器学习预测。

通过结合机器学习预测的结构洞察力和RMP的双值指导，我们的设计在保持列生成的数学严谨性的同时实现了实际的计算可扩展性。这建立了一个自适应的反馈循环，其中机器学习提供解决方案空间中有希望区域的指导，而VNS动态响应不断变化的双值，从而生成尊重所有GPDPTW-DBS约束的高质量列。这种方法在我们工作的主要关注点——重新优化场景中特别有利，这些场景涉及对问题实例的增量修改。

5.4.1. 邻域操作符和机器学习集成
完整的算法过程在算法1中正式呈现，相关符号在表4中详细说明。我们的VNS实现有两种变体：基本VNS（无机器学习预测）和增强机器学习的VNS（集成机器学习预测的固定边缘/驾驶员休息策略）。这两种变体都使用了四种基本的邻域操作符：插入、移动、交换和两次移动，每种操作符都旨在系统地探索解决方案空间的不同维度。我们设计的操作符虽然在实现上是原创的，但建立在用于解决经典VRP和PDPTW的成熟邻域结构之上。它们保持了与这些成熟结构相同的拓扑变化类型（例如，调整路线段），同时也适应了我们问题的独特特性。以下是四种邻域函数的定义（对于增强机器学习的VNS，特别强调了与机器学习相关的行为）：

- 插入：此操作将一个未分配的请求实体插入到一个活跃的车辆路线中。在增强机器学习的VNS中，请求实体被定义为单个未分配的请求或由MLE预测的固定边缘连接的一对未分配请求。在基本VNS中，实体仅限于单个未分配的请求（无机器学习预测的固定边缘）。该实体会在现有路线的所有可行位置进行插入评估。如果找不到可行的插入位置，则创建一条新路线来容纳该实体。
- 移动：此操作符将一个请求从其当前路线中移除，并评估其插入到不同路线中的可能性。在增强机器学习的VNS和基本VNS中，操作符采用首次改进策略：对于随机选择的请求，评估所有其他路线中的可行插入位置，并在第一个能改善解决方案质量的位置停止搜索（即减少总路线时长）。两种变体之间的区别在于位置评估。在增强机器学习的VNS中，目标插入位置受到MLE预测的最高概率固定边缘的限制，意味着它被插入到与其有强预测连接的请求之前或之后。在基本VNS中，插入位置不受MLE预测的约束。在两种变体中，如果请求在移动过程中变得未分配（例如，由于违反约束），则随后由插入操作符重新插入。
- 交换：算法在两条不同的路线中找到两个请求，将每个请求从其当前路线中移除，并将它们插入到另一个路线的原始路线中，同时满足约束条件。
- 两次移动：算法从三条不同的路线中找到三个请求，将每个请求从其当前路线中移除，并将它们按旋转顺序（1→2→3→1）插入到后续路线中，同时满足约束条件。更具体地说，三条路线的旋转操作如下：给定三条不同的路线r1、r2和r3，从r1中选择一个请求k1，从r2中选择一个请求k2。操作符首先从r1中移除k1并尝试将其插入到r2中，然后从r2中移除k2并尝试将其插入到r3中。因此，移动遵循旋转顺序k1→r2、k2→r3、k3→r1。所有插入都需满足所有约束的可行性验证。

下载：下载高分辨率图像（189KB）
下载：下载全尺寸图像

算法1. 列生成主循环（ML/非ML变体）
表3. 主问题和定价问题的约束

问题 / 类别 描述
主问题
车队规模：使用的车辆数量不得超过可用车辆数量。∑r∈Ω λr≤|V|
定价子问题
1. 路线结构
• 基本性：每个节点i∈N最多访问一次。
• 仓库起点/终点：从仓库o开始，在仓库d结束。
2. 拿取和交付
• 先序：对于请求k∈K，在dk之前访问pk（apk≤adk）。
• 配对：同一辆车必须同时服务pk和dk。
3. 时间
• 时间窗口：对于所有节点i∈N，ei≤ai≤li。
4. 容量
• 车辆容量：任何节点i处的0≤Li≤L ≤ Q。
5. 驾驶员调度
设Δbreak为单次连续休息期间的时长。对于分段休息，设Δ1break为第一部分的时长，Δ2break为第二部分的时长。

法规（EC）561/2006（驾驶法规）：
- 最大日驾驶时间：总驾驶时间不得超过9小时。
- 驾驶休息：设Lbdriving为自上次在休息点b∈B重置以来的驾驶时间。
- 如果Lbdriving≤lbreak|drive：可以继续驾驶。
- 如果Lbdriving＞lbreak|drive：在继续驾驶之前必须休息。休息可以是：
1. 持续时长为Δbreak≥lbreak的单次连续休息，
或
2. 由第一部分时长Δ1break≥lbreak|1st和第二部分时长Δ2break≥lbreak|2nd组成的分段休息。满足上述任一条件的休息将重置驾驶计时器：Lb+1driving←0。

指令2002/15/EC（工作法规）：
- 最大无休息工作时间：驾驶员连续工作不得超过lbreak|work1st分钟（即6小时）而不休息。为满足此规则而采取的任何休息必须至少为lbreak|1st分钟。
- 总工作休息要求：一天内累计的工作时间决定了所需的最小总休息时长：
- 如果0 - 如果lbduty＞lbreak|work2nd（工作时间超过9小时）：驾驶员必须至少休息dutybreakrequirement2分钟（即45分钟）。任何所需的休息可以分成至少15分钟的时段。足够总时长（δbreak≥所需时长）的休息将重置工作计时器：lb+1break|work1st←0，lb+1break|work2nd←0。

表4. vns列生成器中的变量符号

符号 描述
scurrent solution set 解决方案中的路线集合sn
nmax 当前邻域结构的索引
ν, πk 来自rmp的对偶变量
cˉr 路线r的减少成本，见方程（5）
cmin 当前vns迭代中找到的最佳（最小）减少成本
cmin′ 新生成的邻域r′中的最小减少成本
max 迭代次数
maxcolumns 列池中的最大路线数量
columnpool rmpp的最佳路线（列）集合
paml预测的组件模式（仅适用于增强机器学习的vns）
useml 布尔标志：true = 增强机器学习的vns，false = 基本vns

为了确保在搜索过程中完全覆盖所有请求，任何未分配的请求都会被分配一个较大的惩罚成本m。这使得任何会使请求保持未分配状态的移动在目标函数中非常不受欢迎，除非找不到可行的插入位置。

在增强机器学习的变体中，搜索由模型的预测指导，同时通过邻域函数的设计允许偏离。移动操作符被限制为仅评估与mle预测的连接概率最高的请求相邻的插入位置。如果这种特定移动不可行或不会改善解决方案，请求可能会变得未分配，随后由插入操作符处理。插入操作符考虑可能是单个请求或机器学习预测的对的请求实体，将每个实体视为一个插入单元。交换操作符有意独立于mle预测操作，提供了一个明确的覆盖机制。因此，这种设计允许偏离机器学习预测，并确保持续适应不断变化的lp解决方案：任何移动的接受，包括那些与机器学习预测不同的移动，最终由使用当前对偶值（πk, ν）计算出的减少成本c￣r来决定。因此，算法在列生成过程中动态调整其搜索方向，以响应对偶值的变化。

作为解决方案过程的一个组成部分，当累积的工作时间或驾驶时间超过监管阈值（lbduty≥lbreak|work1st或lbdriving≥lbreak|drive）时，休息调度模块会在路线构建期间激活。在增强机器学习的vns变体中，当路线需要分配休息时，其特征会被计算并传递给mlb，后者预测休息策略。在基本vns变体中，休息时间表是使用确定性启发式规则生成的（见第5.3节）。两种变体都一致地处理约束违反。如果添加所需的驾驶员休息导致路线超过允许的最大日驾驶时间，则创建一条新路线，并使用插入操作符重新插入被违反路线的最后一个请求。

机器学习预测提供了在空间上高效且在监管上合规的结构指导。mle预测的边缘通常连接地理位置接近的节点，而mlb预测的休息策略不仅满足强制性的驾驶法规，还根据路线特征预测了最佳的休息策略。这些模式提供了一个稳定的基础，减少了初始搜索空间，同时对需求扰动具有鲁棒性。 - 如果lbduty＞lbreak|work2nd（工作时间超过9小时）：驾驶员必须至少休息dutybreakrequirement2分钟（即45分钟）。任何所需的休息可以分成至少15分钟的时段。足够总时长（δbreak≥所需时长）的休息将重置工作计时器：lb+1break|work1st←0，lb+1break|work2nd←0。 表4. vns列生成器中的变量符号 符号 描述 scurrent solution set 解决方案中的路线集合sn nmax 当前邻域结构的索引 ν, πk 来自rmp的对偶变量 cˉr 路线r的减少成本，见方程（5） cmin 当前vns迭代中找到的最佳（最小）减少成本 cmin′ 新生成的邻域r′中的最小减少成本 max 迭代次数 maxcolumns 列池中的最大路线数量 columnpool rmpp的最佳路线（列）集合 paml预测的组件模式（仅适用于增强机器学习的vns） useml 布尔标志：true=增强机器学习的VNS，False = 基本vns 为了确保在搜索过程中完全覆盖所有请求，任何未分配的请求都会被分配一个较大的惩罚成本m。这使得任何会使请求保持未分配状态的移动在目标函数中非常不受欢迎，除非找不到可行的插入位置。 在增强机器学习的变体中，搜索由模型的预测指导，同时通过邻域函数的设计允许偏离。移动操作符被限制为仅评估与mle预测的连接概率最高的请求相邻的插入位置。如果这种特定移动不可行或不会改善解决方案，请求可能会变得未分配，随后由插入操作符处理。插入操作符考虑可能是单个请求或机器学习预测的对的请求实体，将每个实体视为一个插入单元。交换操作符有意独立于mle预测操作，提供了一个明确的覆盖机制。因此，这种设计允许偏离机器学习预测，并确保持续适应不断变化的lp解决方案：任何移动的接受，包括那些与机器学习预测不同的移动，最终由使用当前对偶值（πk, ν）计算出的减少成本c￣r来决定。因此，算法在列生成过程中动态调整其搜索方向，以响应对偶值的变化。 作为解决方案过程的一个组成部分，当累积的工作时间或驾驶时间超过监管阈值（lbduty≥lbreak|work1st或lbdriving≥lbreak|drive）时，休息调度模块会在路线构建期间激活。在增强机器学习的vns变体中，当路线需要分配休息时，其特征会被计算并传递给mlb，后者预测休息策略。在基本vns变体中，休息时间表是使用确定性启发式规则生成的（见第5.3节）。两种变体都一致地处理约束违反。如果添加所需的驾驶员休息导致路线超过允许的最大日驾驶时间，则创建一条新路线，并使用插入操作符重新插入被违反路线的最后一个请求。> - 如果lbduty＞lbreak|work2nd（工作时间超过9小时）：驾驶员必须至少休息dutybreakrequirement2分钟（即45分钟）。任何所需的休息可以分成至少15分钟的时段。足够总时长（δbreak≥所需时长）的休息将重置工作计时器：lb+1break|work1st←0，lb+1break|work2nd←0。

表4. vns列生成器中的变量符号

符号 描述
scurrent solution set 解决方案中的路线集合sn
nmax 当前邻域结构的索引
ν, πk 来自rmp的对偶变量
cˉr 路线r的减少成本，见方程（5）
cmin 当前vns迭代中找到的最佳（最小）减少成本
cmin′ 新生成的邻域r′中的最小减少成本
max 迭代次数
maxcolumns 列池中的最大路线数量
columnpool rmpp的最佳路线（列）集合
paml预测的组件模式（仅适用于增强机器学习的vns）
useml 布尔标志：true = 增强机器学习的vns，false = 基本vns

为了确保在搜索过程中完全覆盖所有请求，任何未分配的请求都会被分配一个较大的惩罚成本m。这使得任何会使请求保持未分配状态的移动在目标函数中非常不受欢迎，除非找不到可行的插入位置。

在增强机器学习的变体中，搜索由模型的预测指导，同时通过邻域函数的设计允许偏离。移动操作符被限制为仅评估与mle预测的连接概率最高的请求相邻的插入位置。如果这种特定移动不可行或不会改善解决方案，请求可能会变得未分配，随后由插入操作符处理。插入操作符考虑可能是单个请求或机器学习预测的对的请求实体，将每个实体视为一个插入单元。交换操作符有意独立于mle预测操作，提供了一个明确的覆盖机制。因此，这种设计允许偏离机器学习预测，并确保持续适应不断变化的lp解决方案：任何移动的接受，包括那些与机器学习预测不同的移动，最终由使用当前对偶值（πk, ν）计算出的减少成本c￣r来决定。因此，算法在列生成过程中动态调整其搜索方向，以响应对偶值的变化。

作为解决方案过程的一个组成部分，当累积的工作时间或驾驶时间超过监管阈值（lbduty≥lbreak|work1st或lbdriving≥lbreak|drive）时，休息调度模块会在路线构建期间激活。在增强机器学习的vns变体中，当路线需要分配休息时，其特征会被计算并传递给mlb，后者预测休息策略。在基本vns变体中，休息时间表是使用确定性启发式规则生成的（见第5.3节）。两种变体都一致地处理约束违反。如果添加所需的驾驶员休息导致路线超过允许的最大日驾驶时间，则创建一条新路线，并使用插入操作符重新插入被违反路线的最后一个请求。

机器学习预测提供了在空间上高效且在监管上合规的结构指导。mle预测的边缘通常连接地理位置接近的节点，而mlb预测的休息策略不仅满足强制性的驾驶法规，还根据路线特征预测了最佳的休息策略。这些模式提供了一个稳定的基础，减少了初始搜索空间，同时对需求扰动具有鲁棒性。>尽管不能保证在每个最优解中都出现，但它们提供了一个高质量的起点，优化框架可以高效地对其进行改进。MLE和MLB都仅基于静态特征进行预测，这些特征与优化状态无关。具体来说，边缘预测特征（第5.2节）仅依赖于实例数据和潜在的需求扰动，而休息策略特征（第5.3节）仅依赖于路线的时间结构和监管参数。这种独立性确保了预测在整个列生成过程中仍然有效，无论双重值如何演变。5.4.2. 使用双重引导的VNS算法进行列生成我们的VNS方法明确利用了LPR中的双重信息来指导启发式搜索过程，这与传统VNS实现有根本的不同，后者通常依赖随机选择机制来探索搜索空间。如算法1所示，我们的VNS算法专门设计用于识别具有负减少成本的可行路线，而不是直接解决整个问题。因此，我们省略了传统的摇动阶段，因为双重引导的减少成本本质上将搜索指向解决方案空间的有希望的区域，使得额外的随机扰动变得不必要，并可能对搜索效率产生不利影响。第6.1节中呈现的实验验证了这种有针对性的搜索策略的有效性。列生成循环首先通过解决RMP来获得请求覆盖约束的双重变量πk和车队规模约束的双重变量ν（算法1，第3行）。布尔标志useML决定了是否将机器学习预测集成到过程中。如果useML设置为True，则模型预测固定组件（算法1，第6行）。这些对被作为Pa传递给VNS子程序（算法2）。如果useML设置为False，则集合Pa保持为空（算法1，第8行）。在这个子程序中，通过应用第n个邻域结构生成的每个候选路线的减少成本都会被计算出来，这量化了其相对于当前LP解决方案的潜在改进。下载：下载高分辨率图像（154KB）下载：下载全尺寸图像算法2. 基于双重引导的VNS进行列生成（ML/非ML变体）。搜索方向由基于双重的接受规则控制。根据它们的减少成本，考虑从R′生成的路线是否被接受。只有当R′中的最小减少成本低于当前VNS调用中找到的最佳值（cmin′0。30%的变化（α=0.3）代表了最大现实的需求波动。我们按照以下方式处理数据：对于每个问题实例和每个α值，生成了100个修改后的实例。其中，95个实例用于ML阶段，包括训练和超参数调整，而剩余的5个实例用于测试（即优化阶段，其中ML模型被集成到CG算法中）。在生成训练集期间，我们记录了用于安排每条路线驾驶员休息的休息策略（合规、策略1或策略2）。为了训练MLB并确保数据集的平衡（同时减轻潜在的模型偏差），我们使用了下采样：我们从三种休息策略类别中各选取了相同数量的数据实例。实验是在所有上述20个实例上进行的，表示为Po1,?,Po20。此外，我们还生成了每个实例的100个修改版本，表示为{(Pmi)α1,?,(Pmi)α100}，其中i∈{1,2,?,20}。对于每个问题实例di，di的值被随机调整了α倍。6.1. 所提出的列生成方法的性能（无ML增强）我们的列生成方法的计算效率受到设置参数maxColumns的关键权衡的影响。由于解决受限主问题（RMP）占计算开销的大部分，我们引入了每次迭代多个列来分摊这一成本。然而，过小的maxColumns值需要更频繁地解决RMP，而过大的值会增加每个RMP的解决时间，在所有可行列都被包括的极限情况下，RMP在计算上等同于解决原始问题。A.6节的实证结果表明，参数值maxColumns=1000和maxIteration=30在解决方案质量和计算努力之间实现了有效的平衡。此外，我们的方法允许在初始探索阶段暂时违反车辆车队规模约束，以便更广泛地覆盖解决方案空间。我们的实现仅在探索阶段保持这种约束放宽，在输出解决方案之前恢复完全合规。对于RMP优化，我们使用了Gurobi 11的默认设置，并在配备16 GB RAM的8核Intel i7-2.99 GHz处理器上运行它。我们在这项研究中的所有实验都使用同一台机器。本文中的所有实验都基于在同一台机器上进行的30次独立运行。所提出的启发式CG方法的性能与Xue等人（2025a）的基准方法进行了评估。为了证明我们启发式定价策略引入的近似性，并提供解决方案质量的下限保证，我们实现了一个通过ESPPRC方法解决的精确定价问题（详见附录）。这种精确定价分析的结果报告在表5的Est. LB列中。为了与文献中建立的基准（Goel, 2018, Kok等人, 2010, Prescott-Gagnon等人, 2010）进行公平和一致的比较，本实验研究中的服务小时规则被简化了。具体来说，驾驶休息被严格定义为至少45分钟的单次非工作时间，或者两次非工作时间，其中第一次至少15分钟，第二次至少30分钟。这种建模选择保证了符合（EC）561/2006的最低要求。然而，它没有利用更广泛的休息模式解释所允许的完全调度灵活性，这可能会产生更高效或更现实的计划。附录A.1中提供了关于这一限制的详细讨论和一个示例。表5. 与估计下限的总结性能比较。本工作（启发式CG）Xue等人（2025）本工作（Est. LB）成本时间（秒）成本时间（秒）成本时间（秒）lc101-DBS90.12 ± 0.11705 ± 4390.33 ± 0.18986 ± 6289.503123lc102-DBS95.38 ± 0.17340 ± 1495.72 ± 0.23474 ± 3894.683176lc103-DBS83.55 ± 0.25218 ± 5385.62 ± 0.25347 ± 3282.953322lc104-DBS64.10 ± 0.14525 ± 2465.94 ± 0.20791 ± 5563.653628lc105-DBS89.50 ± 0.15282 ± 5390.08 ± 0.19465 ± 4088.803434lr203-DBS38.92 ± 0.14528 ± 1240.06 ± 0.11755 ± 5838.684402lr204-DBS34.77 ± 0.05432 ± 2135.77 ± 0.10669 ± 4934.554228lr205-DBS65.08 ± 0.11702 ± 3465.93 ± 0.161146 ± 7564.604534lr206-DBS59.78 ± 0.09978 ± 5159.69 ± 0.121459 ± 9259.354982lr207-DBS55.66 ± 0.21928 ± 4355.86 ± 0.101428 ± 8855.274815ber-n100-3-DBS193.78 ± 0.17932 ± 64194.29 ± 0.381272 ± 95192.204027ber-n100-4-DBS174.12 ± 0.42838 ± 43174.71 ± 0.331167 ± 85172.703903ber-n100-5-DBS310.75 ± 0.531018 ± 62311.15 ± 0.601567 ± 110308.105133ber-n100-6-DBS49.51 ± 0.12328 ± 2149.23 ± 0.08443 ± 3549.153018ber-n100-7-DBS57.17 ± 0.26380 ± 5257.39 ± 0.11556 ± 4256.753192bar-n200-3-DBS520.88 ± 0.67703 ± 13521.18 ± 0.97946 ± 72516.455236bar-n200-5-DBS431.85 ± 0.53592 ± 53432.61 ± 0.80861 ± 65428.054775bar-n200-6-DBS885.70 ± 1.361342 ± 74885.76 ± 1.601872 ± 135877.755258bar-n200-7-DBS374.28 ± 0.43968 ± 81374.77 ± 0.701534 ± 115370.985027ber-n200-6-DBS209.18 ± 0.33765 ± 62210.11 ± 0.401074 ± 82207.484956平均194.20 ± 0.31675.20 ± 44194.81 ± 0.36990.60 ± 73.8192.584208表5中的结果显示了所提出的启发式CG方法的有效性。配对t检验确认我们的方法在解决方案质量上显著优于Xue等人（2025a）的基准方法（p < 0.01），平均成本为194.20，而他们的平均成本为194.81。在计算上，我们的启发式CG也显著更高效，平均完成时间大约减少了1.5倍（675.20秒对比990.60秒）。为了量化这些解决方案的质量，我们通过ESPPRC方法精确解决了定价问题来计算估计的下限（Est. LB）。结果显示，估计的下限平均比我们的解决方案成本低约0.84%（p < 0.05）。这提供了一个质量证明，表明我们的解决方案在最优性的一个小范围内。然而，生成这个界限在计算上非常密集，平均需要4208秒。我们的启发式CG方法的运行时间（675.20秒）与界限计算时间（4208秒）之间的显著差异（p < 0.001）强调了优化中解决方案质量和计算努力之间的基本权衡。6.2. 基于ML增强的列生成方法的性能比较本节基于三轮实验，展示了我们基于ML增强的列生成方法的性能比较。每一轮都在应用不同的机器学习（ML）组件后，使用启发式列生成器来评估它们各自和组合的有效性：（1）第一轮：边缘修复算法评估了边缘修复组件在提高列生成器产生高质量解决方案的能力方面的有效性，与基准（独立的启发式列生成器）相比；（2）第二轮：中断策略修复算法评估了中断策略修复组件对解决方案质量的贡献；（3）第三轮：完整的ML增强算法测试了集成方法，应用了两个ML组件来评估整个算法在提高解决方案质量和计算效率方面的性能，这代表了本工作的主要贡献。如前所述，对于每个实例，生成了100个修改后的实例，总共生成了2000个实例。在获得So和Sm之后，我们根据第5节中介绍的方法提取所需的训练集和测试集、特征和标签。表6和表7分别总结了从修改后的合成基准（Li和Lim，2001年）和现实生活基准（Sartori和Buriol，2020年）中得到的测试实例的结果。每一行代表五个测试实例计算出的平均值。表6. 不同实例的性能指标（Li和Lim，2001年）。实例相似性准确性CG边缘修复+CG中断修复+CG边缘&中断修复+CGMLMB成本时间（秒）成本时间（秒）成本时间（秒）成本时间（秒）lc101-DBS61%77%76%90.12 ± 0.11705 ± 4391.75 ± 0.1927.9 ± 4.891.21 ± 0.1847.2 ± 5.791.84 ± 0.1923.5 ± 3.6lc102-DBS68%80%78%95.38 ± 0.17340 ± 1497.07 ± 0.2415.0 ± 2.996.77 ± 0.2326.4 ± 4.597.18 ± 0.2511.1 ± 2.2lc103-DBS55%81%82%83.55 ± 0.15218 ± 5385.03 ± 0.156.2 ± 1.884.79 ± 0.1915.8 ± 0.165.9 ± 1.3lc104-DBS58%74%80%64.10 ± 0.14525 ± 4265.22 ± 0.1622.3 ± 4.964.93 ± 0.1540.1 ± 6.265.29 ± 0.1717.8 ± 3.9lc105-DBS55%75%78%89.50 ± 0.15282 ± 5391.08 ± 0.198.7 ± 2.390.79 ± 0.1818.4 ± 0.218.5 ± 0.165.9 ± 1.3lc106-DBS68%73%75%38.92 ± 0.14528 ± 4339.59 ± 0.1214.7 ± 3.739.38 ± 0.1138.0 ± 5.839.64 ± 0.1313.4 ± 3.1lr203-DBS64%79%86%34.77 ± 0.05432 ± 3535.37 ± 0.1111.1 ± 3.235.26 ± 0.1031.2 ± 4.835.40 ± 0.1210.6 ± 2.8lr205-DBS72%84%86%65.08 ± 0.11702 ± 5766.20 ± 0.1729.6 ± 5.165.96 ± 0.1654.7 ± 7.366.27 ± 0.1822.7 ± 4.2lr206-DBS81%82%81%59.78 ± 0.10978 ± 8060.88 ± 0.1644.6 ± 0.1570.8 ± 8.960.97 ± 0.1733.2 ± 5.5lr207-DBS73%82%85%55.66 ± 0.09928 ± 7656.62 ± 0.1529.0 ± 5.456.45 ± 0.1466.8 ± 7.656.68 ± 0.1626.9 ± 4.7平均65.5%79.7%80.7%67.68 ± 0.21563.8 ± 49.668.88 ± 0.1620.9 ± 4.168.62 ± 0.1640.94 ± 5.768.96 ± 0.1717.4 ± 3.3表7. 不同实例的性能指标（Sartori和Buriol，2020年）。实例相似性准确性CG边缘修复+CG中断修复+CG边缘&中断修复+CGMLMB成本时间（秒）成本时间（秒）成本时间（秒）ber-n100-3-DBS64%78%78%193.78 ± 0.17932 ± 64197.16 ± 0.3946.4 ± 5.9196.58 ± 0.3867.7 ± 7.4197.34 ± 0.4027.5 ± 3.8ber-n100-4-DBS71%81%80%174.12 ± 0.42838 ± 43177.16 ± 0.3532.3 ± 4.5176.64 ± 0.3461.7 ± 7.2177.34 ± 0.3627.1 ± 4.1ber-n100-5-DBS68%83%81%310.75 ± 0.531018 ± 62316.13 ± 0.6436.0 ± 5.2315.20 ± 0.6274.9 ± 8.9316.44 ± 0.6532.9 ± 4.6ber-n100-6-DBS71%75%80%49.51 ± 0.12328 ± 2150.47 ± 0.1215.1 ± 2.850.22 ± 0.1121.3 ± 3.550.51 ± 0.139.7 ± 1.9ber-n100-7-DBS68%78%79%57.17 ± 0.26380 ± 5258.18 ± 0.1419.3 ± 3.458.01 ± 0.1326.0 ± 4.258.23 ± 0.1511.9 ± 2.3bar-n200-3-DBS71%76%76%520.88 ± 0.67703 ± 13530.19 ± 1.0137.2 ± 5.6528.62 ± 0.9946.4 ± 6.3530.70 ± 1.0221.6 ± 3.5bar-n200-5-DBS72%81%87%431.85 ± 0.53592 ± 53439.28 ± 0.8529.9 ± 4.8437.98 ± 0.8344.0 ± 6.1439.71 ± 0.8619.5 ± 3.2bar-n200-6-DBS75%87%86%885.70 ± 1.361342 ± 74900.90 ± 1.7151.8 ± 7.5898.25 ± 1.6898.2 ± 10.7901.79 ± 1.7241.5 ± 5.9bar-n200-7-DBS74%85%80%374.28 ± 0.43968 ± 81380.75 ± 0.7547.2 ± 6.9379.63 ± 0.7366.8 ± 8.4381.13 ± 0.7628.0 ± 4.5ber-n200-6-DBS76%81%86%209.18 ± 0.33765 ± 62212.85 ± 0.4541.4 ± 6.2212.23 ± 0.4353.9 ± 7.6213.16 ± 0.4622.6 ± 3.8平均71.0%80.5%81.3%320.72 ± 0.48786.6 ± 52.5326.30 ± 0.6435.7 ± 5.3325.34 ± 0.6356.1 ± 7.03326.64 ± 0.6524.2 ± 3.86.2. 边缘修复的So和Sm之间的相似性表6和表7的第一列（结构相同）列出了原始问题实例Po，而第二列使用以下公式量化了它们的解决方案So与修改后的解决方案Sm之间的相似性：相似性(So,Sm)=|So∩Sm||So|该相似性指标对应于被修复的边的百分比（即标记为1的边），来自Morabit等人（2024年）。这个指标在影响解决方案的质量和获得解决方案所需的计算时间方面起着重要作用。当某些边尽管是必要的但没有被修复时（假阴性），计算时间可能会增加，因为列生成器可能仍然需要将这些边纳入最终解决方案。另一方面，被错误分类为0的边（假阳性）可能导致更大的最优性差距，从而可能损害解决方案的质量。请注意，可以根据解决方案质量和计算效率之间的期望权衡来调整边的权重。给标记为0的边分配更高的权重可以减少假阳性，从而减少修复的边数。虽然这种方法可能会提高解决方案的质量，但也可能导致更长的计算时间。相反，给标记为1的边分配更高的权重会增加修复更多边的可能性，这可以减少计算时间，但可能会对解决方案质量产生负面影响。在我们的方法中，我们采用了两种类别之间的平衡权重方案，以在解决方案质量和计算效率之间取得合理的折中。这些结果的更详细分析可以在附录的A.3部分找到。然而，在实际应用中，权重的选择应该由任务的具体目标指导，旨在针对手头的问题找到最佳平衡。6.2.2. 机器学习模型的准确性：MLE与MLB接下来两列与相似性相邻，报告了机器学习模型MLE和MLB的测试准确性（表格中称为准确性）。决策树在各种数据集上的十折交叉验证准确率范围为73%到87%，而MLB的平均准确率范围为75%到87%。然而，对单个实例的仔细检查揭示了准确性和相似性之间的轻微正相关。具体来说，随着需求幅度的减小，相似性增加；这个幅度由参数α控制，它决定了原始实例和修改后实例之间的差异。相似性较高的实例更容易预测，从而导致更高的准确性，这与预期一致。此外，通过修复模型提出的边，我们发现解决方案质量也呈现出类似的趋势。需求的较大变化导致相似性降低，误分类的可能性增加，从而导致解决方案质量下降。因此，相似性较高的实例往往比相似性较低的实例表现出更好的解决方案质量。6.2.3. 解决方案质量和计算效率接下来的两列在准确性列之后，报告了列生成启发式（表示为CG）的成本（以小时为单位的旅行时间）和经过的时间（以秒为单位）。使用边缘修复算法后跟启发式列生成器的结果总结在Edge-fixing+CG列下。同样，使用中断策略修复算法后跟启发式列生成器的结果总结在Break-fixing+CG列下。最后，同时应用边缘修复算法和中断策略修复算法的结果总结在Edge&Break-fixing+CG列下。从表6和表7可以看出，评估的指标是解决方案质量（以旅行时间为单位的成本）和计算效率（以秒为单位的经过时间）。对于Li和Lim（2001）的数据集，基线CG的平均成本为67.68，经过时间为563.8秒。Edge-fixing+CG将平均成本增加到68.88（增加了1.8%），同时将经过时间减少到20.9秒（减少了96.3%）。Break-fixing+CG的平均成本为68.62（增加了1.4%），经过时间为40.9秒（减少了92.7%）。组合方法（Edge&Break-fixing+CG）的平均成本为68.94（增加了1.9%），并将经过时间减少到17.4秒（减少了96.9%）。所有增强方法相对于基线的计算时间改进在统计上都是显著的（p < 0.001），这一点通过配对t检验得到了确认。对于Sartori和Buriol（2020）的数据集，基线CG的平均成本为320.72，经过时间为786.6秒。Edge-fixing+CG将平均成本增加到326.30（增加了1.7%），同时将经过时间减少到35.7秒（减少了95.5%）。Break-fixing+CG的平均成本为325.34（增加了1.4%），经过时间为56.1秒（减少了92.9%）。组合方法的平均成本为326.64（增加了1.9%），并将经过时间减少到24.2秒（减少了96.9%）。观察到的运行时间减少非常显著（p < 0.001）。结果表明，边缘修复和中断策略修复都显著减少了计算时间。组合方法实现了最大的时间节省，平均减少超过96%。这些发现证实，所提出的方法有效地识别了用于解决GPDPTW-DBS的高质量列。所有增强方法相对于基线CG的成本增加都在2%以内，这低于实际意义上的阈值。生成的解决方案平均比Li和Lim数据集的估计下限高出约2.7%，比Sartori和Buriol数据集高出约1.8%。这表明，由ML指导的修复策略在产生非常接近最优解的解决方案的同时实现了显著的计算加速。边缘修复和中断修复从不同的角度加速了解决过程。边缘修复减少了问题的规模，而中断修复减少了节点处的时间相关变量更新。这种效率提升归因于与Regulation (EC)561/2006和Directive 2002/15/EC一致的问题描述特征。边缘修复的有效性仍然来自于大量的修改训练实例，这在更高相似性实例的更强准确性和质量中得到了体现。当前的路线初始化使用简单的启发式方法，但实际部署可以通过利用历史数据中频繁观察到的路线和中断模式来进一步提高计算性能。6.2.4. 运行时分布和在线推理解决过程结合了两种不同的机器学习模型：MLE用于边缘预测，MLB用于中断策略预测。这两种模型都是使用scikit-learn库中的决策树算法（Pedregosa等人，2011年）进行训练的。训练阶段效率很高，MLE在Intel i7 2.40 GHz处理器和4 GB RAM上大约需要290秒（训练了319,826个边缘实例），MLB需要50秒（训练了47,683个路线实例）。在在线ML增强CG阶段，训练好的模型仅用于推理。然而，由于它们预测的性质不同，它们在算法中的集成方式也不同。对于MLE，边缘预测在VNS开始之前作为预处理步骤计算一次。模型为每个可能的请求连接提供一个概率分数。由于一个请求在有效路线中不能有多个直接的后继者，我们实施了一个互斥规则，只选择预测概率最高的连接。这导致了一个字典，其中每个请求最多与一个后继者配对，形成了一组固定的请求对。这组静态的预测对在整个列生成过程中使用，无需进一步修改。对于MLB，必须在路线构建过程中动态地进行预测，因为诸如路线持续时间之类的特征取决于路线的演变状态。为了最小化开销，学习到的决策树直接作为一系列硬编码的if-else条件集成到列生成逻辑中。这些ML组件在在线阶段的计算成本在所有测试实例中都是最小的。如表8所示，该表详细列出了30次独立运行中所有20个实例的运行时间分布，MLE和MLB推理的总时间仅占总时间的0.9%到2.2%，标准差为0.1-0.4%。大部分计算工作都花在了核心优化组件上：解决RMP和VNS内的邻域搜索。在不同大小和特征的实例中，分布保持稳定：RMP解决消耗了69.1-78.9%的时间，VNS消耗了19.4-29.3%的时间，标准差分别为0.4-1.4%。表8. 所有实例中算法组件的运行时间分布（百分比）（平均值 ± 标准差，共30次运行）。实例MLE (%)MLB (%)VNS (%)RMP (%)lc101-DBS0.7 ± 0.10.5 ± 0.124.6 ± 0.874.2 ± 0.9lc102-DBS0.8 ± 0.10.6 ± 0.126.3 ± 1.072.3 ± 1.1lc103-DBS0.9 ± 0.20.7 ± 0.128.5 ± 1.269.9 ± 1.3lc104-DBS0.6 ± 0.10.5 ± 0.123.8 ± 0.775.1 ± 0.8lc105-DBS0.8 ± 0.10.6 ± 0.125.4 ± 0.973.2 ± 1.0lr203-DBS1.0 ± 0.20.5 ± 0.120.8 ± 0.677.7 ± 0.7lr204-DBS1.1 ± 0.20.6 ± 0.119.4 ± 0.578.9 ± 0.6lr205-DBS1.3 ± 0.20.7 ± 0.122.1 ± 0.775.9 ± 0.8lr206-DBS1.5 ± 0.30.6 ± 0.121.6 ± 0.776.3 ± 0.8lr207-DBS1.2 ± 0.20.6 ± 0.121.6 ± 0.776.6 ± 0.8ber-n100-3-DBS0.6 ± 0.10.5 ± 0.127.8 ± 1.271.1 ± 1.1ber-n100-4-DBS0.7 ± 0.10.6 ± 0.126.9 ± 1.171.8 ± 1.2ber-n100-5-DBS0.9 ± 0.20.7 ± 0.129.3 ± 1.369.1 ± 1.4ber-n100-6-DBS0.5 ± 0.10.4 ± 0.124.2 ± 0.874.9 ± 0.9ber-n100-7-DBS0.6 ± 0.10.5 ± 0.125.7 ± 0.973.2 ± 1.0bar-n200-3-DBS1.1 ± 0.20.5 ± 0.120.2 ± 0.678.2 ± 0.7bar-n200-5-DBS1.2 ± 0.20.6 ± 0.121.5 ± 0.776.7 ± 0.8bar-n200-6-DBS1.4 ± 0.30.6 ± 0.122.8 ± 0.875.2 ± 0.9bar-n200-7-DBS1.3 ± 0.20.5 ± 0.121.9 ± 0.776.3 ± 0.8ber-n200-6-DBS1.3 ± 0.20.6 ± 0.120.5 ± 0.776.6 ± 0.8平均0.98 ± 0.170.58 ± 0.0723.74 ± 2.4574.73 ± 2.616.2.5. 敏感性分析我们进行了敏感性分析，以评估需求变化幅度（α）对我们基于ML的列生成框架性能的影响，具体比较了边缘修复（MLE）和中断策略修复（MLB）策略。关键观察结果是，边缘修复方法的有效性对α的值非常敏感：较高的干扰水平会导致解决方案的相似性降低、预测准确性下降，从而增加计算时间和解决方案成本。相比之下，中断策略预测模型表现出显著的鲁棒性，在所有α值下都能保持稳定的准确性和解决方案质量，因为它独立于底层的路由结构运行。这种差异突显了两种策略的不同机制作用：边缘修复直接限制了解决器的搜索空间，因此容易受到问题不稳定性的影响，而中断策略修复则作为一个高效的辅助过程，无论需求如何变化都能保持可靠性。我们还对算法的关键参数maxColumns和maxIterations进行了敏感性分析。有关更详细的结果和讨论，请参阅附录7中的A.3节。

**结论**
本文提出了一种快速重新优化方法，该方法整合了路由和司机休息调度。该方法在生成最短路线的同时，明确考虑了强制性的司机休息要求。我们的启发式列生成框架通过机器学习得到了增强，适用于各种持续时间相关成本至关重要的问题变体。该框架排除了基于里程或劳动力的支付方式，使其适用于超市、便利店和电子商务配送等应用。这种基于机器学习的方法确保了休息要求的遵守，同时实现了显著的计算效率提升：运行时间减少了96%以上，仅剩几秒钟；路由成本增加了不到2%，解决方案与估计的下限之间的差距仅为2.7%。该框架的优势在于能够有效管理同时进行路由和休息调度的复杂性。

在实践中，许多GPDPTW-DBS实例会在目标不变的情况下反复求解，但数据会更新。通过训练用于边缘修复和中断策略修复的机器学习模型，我们的方法能够识别出不变的解决方案组成部分并缩小搜索空间。这在合成和真实世界的基准测试中都证明了显著的计算时间节省。从先前的研究中得出的三种中断策略标签是可以泛化的，只要这些策略能够被分类器训练所枚举即可。用于边缘修复的分类器对这些标签赋予相同的权重。实际上，给标记为1的边缘赋予更高的权重会增加修复更多边缘的可能性。虽然这可以减少计算时间，但也可能对解决方案质量产生负面影响，这需要在实际应用中进一步探索。理想情况下，机器学习模型应该基于最优解进行训练。然而，由于解决GPDPTW-DBS问题的复杂性，无法为这项研究生成足够数量的最优训练数据。因此，我们使用了接近最优的解决方案。尽管机器学习预测只是我们解决方案框架的一个组成部分，并随后通过启发式列生成过程进行细化，但我们认为如果使用最优解来训练机器学习模型，最终解决方案的质量和过程的计算效率可能会进一步提高。

**未来研究方向**
包括通过扩展特征工程来增强边缘修复功能，以提高预测准确性和解决方案质量。此外，通过利用实例相似性，我们建议为各个列定义特征。这些列代表了具有休息计划的路线，可以通过过滤和优先处理来识别受限主问题的有希望的解决方案。这种方法可以进一步提高效率和可扩展性，同时为更广泛的应用提供有价值的见解。

**致谢**
本项目得到了宁波市科学技术局（宁波市公益计划，项目编号2024S057、2025S114；宁波市青年科技创新领军人才计划，项目编号2025QL055）的支持。

**作者声明**
本研究不存在利益冲突。

**作者贡献声明**
薛宁：撰写——原始草稿、可视化、验证、方法论、调查、形式分析、数据管理、概念化。崔天翔：撰写——审阅与编辑、验证、监督、资源管理、项目行政、方法论、调查、资金获取、形式分析、概念化。程实：撰写——审阅与编辑、资源管理。