随机旅行时间背景下的定时派送：三索引模型与 Benders 分解求解随机旅行推销问题

论文题目：Models and algorithms for the Time Window Assignment Traveling Salesperson Problem with stochastic travel times

第一作者：Francesco Cavaliere 帕多瓦大学博士（University of Padova），专注于车辆路径问题、排程优化以及相关的精确算法和启发式算法的设计（如分支定界、局部搜索等）。 E-mail：francesco.cavaliere@unipd.it。

通讯作者：Roberto Roberti 帕多瓦大学（University of Padova）副教授，聚焦于组合优化与混合整数线性规划。核心研究领域集中于车辆路径、列生成算法、动态规划以及物流与交通运输优化。

E-mail：roberto.roberti@unipd.it。

随机旅行时间背景下的定时派送：三索引模型与 Benders 分解求解随机旅行推销问题

论文摘要

本文研究随机旅行时间下的时间窗口指派旅行推销问题（Time Window Assignment Traveling Salesperson Problem with Stochastic Travel Times，TWATSP‑ST）。该问题源于城市配送场景，决策者需在服务质量与运营成本间权衡。在第一阶段，需要同时确定拜访客户的路径顺序和各客户的服务时间窗口，随后在第二阶段根据实际的行程时间（随机变量）对发车时间进行调整。目标函数由四部分组成：①路径成本；②所分配时间窗口的宽度；③司机在规定班次外的加班时间；④提前或延迟服务所产生的罚款，这些罚项按场景概率加权。四种权重的选择体现了服务质量与成本之间的多目标权衡。

一、研究背景与问题定义

1.1 物流背景与挑战

随着电子商务和 O2O 服务的发展，物流服务提供商（LSP）每天都要在城市中向众多客户配送货物。过去的优化主要关注运营成本最小化，但城市交通拥堵、天气和道路状况使得旅行时间具有较强的不确定性。此外，客户期望提前获知准确的送达时间，而 LSP 则偏好较宽的时间窗口以获得调度灵活性，两者的偏好存在冲突。因此，既要降低成本，又要提高服务质量就成为新的优化目标。

1.2 问题建模

TWATSP‑ST 在一张有向完全图  上建模，其中 ，0 号节点为仓库，其余为待服务客户。车辆从仓库出发，形成一个哈密顿回路（即旅行推销员路线），旅行时间依赖于随机场景。在第一阶段，需确定：

• 访问顺序：决定服务客户的排列；
• 时间窗口  ：为每个客户选择服务开始和结束时间。

随机旅行时间通过场景集  表示，每个场景有概率  和旅行时间矩阵 。在第二阶段，车辆根据已定路径和时间窗口调整出发时间，计算提前服务和延误产生的罚款等。目标函数包含四部分：

1. 路径成本：；
2. 时间窗口宽度惩罚：；
3. 司机加班惩罚：（超出班次时间  的罚款）；
4. 提前/延迟惩罚：。

权重  可调，用以权衡成本与服务质量，使问题具有多目标特性。

二、模型与算法设计

2.1 Big-M 模型及其局限

文献中已有基于经典旅行推销员问题（ATSP）改造的 Big-M 模型，其使用二元变量  表示弧  是否在路径中、连续变量  表示时间窗口边界、 表示场景  下离开客户  的时间等。利用大常数  将这些变量连接起来。该模型的目标函数可简写为：

约束中包含传统的 DFJ 子圈消除约束和一系列与时间相关的大 M 约束。虽然 Big-M 模型能刻画问题，但大常数导致线性放松极为松弛，求解效率低。实验表明，即便添加常用的子圈消除（SEC）约束或采用 Claus 的 ATSP 加强模型，Big-M 模型仍然难以解决中等规模实例。

2.2 三指标（3-Index）模型

为改善松弛质量，作者提出了三索引二元变量  来表示弧  在巡回中的第  个位置：

其中 。位置  表示从仓库出发的弧，位置  为最后回仓的弧。由于每个弧只能出现在唯一位置，约束易于表达，且可以由位置推导出节点的服务顺序。关键优势包括：

• 避免使用 Big-M 常数：时间递推关系可通过位置索引直接建模；

• 线性松弛更紧：显著提升 LP 下界质量；

• 时间相关变量按位置建模：自然刻画服务顺序与随机旅行时间的影响；

• 易与 ATSP 多面体加强方法结合：可配合 DFJ-SEC 或 Claus 流模型进一步强化。

• 消除大常数：时间相关变量（时间窗口、提前/延误）以节点位置为索引，不再需要 Big‑M。

• 更紧的线性松弛：实验表明新模型对 LP 界有显著提升，后文有详细比较。

2.3 专门的 Benders 分解算法

由于 TWATSP‑ST 是典型的两阶段随机混合整数规划，作者在三指标模型基础上开发了专门的 Benders 分解。总体策略是将整数变量置于主问题，将场景相关连续变量放入子问题。核心设计包括：

1. 变量划分：主问题保留 2‑index 与 3‑index 的二元变量以及一个对各场景成本进行估计的连续变量 ，所有时间相关变量和场景变量进入子问题。这一划分既避免在主问题中处理时间窗口，又避免在子问题中出现整数变量。

2. 分解布局选择：传统方法倾向按场景分解，但那样必须将时间窗口变量放入主问题，作者通过预实验发现该布局非常不稳定，甚至小规模实例也难以求解。因此选择不按场景分解，而是在子问题中处理全部场景。

3. 子圈消除与约束分离：在主问题中需分离子圈消除约束（SEC）。作者采用 Concorde TSP solver 的开源代码在 2‑index 变量中进行 SEC 分离；如没有发现违反的子圈，才生成 Benders 最优性切割。

4. 减少分离开销：预实验发现黑盒 Benders 实现大部分时间花在根节点改进 LP 界，进展缓慢。因此作者决定只对整数可行解执行 Benders 分离，在根节点对分数解仅分离 SEC。由于 SEC 分离开销较小，仍对分数解执行。

5. 初始启发式：为提供暖启动，首先求解路径成本为唯一目标的 ATSP 获得初始巡回并积累 SEC。随后计算略微放松但保留场景相关加班惩罚的模型，得到更优启发式解。

这些技巧共同构成了定制的 Benders 算法，使得三指标模型可高效求解中等规模实例。

三、实验设计与结果分析

3.1 实例构造与参数配置

作者制作了多个实例集用于比较不同模型与算法。基本实例由 18 个基图结合若干随机场景组成；客户数量分别为 10、20 与 30 个，旅行时间通过局部或全局扰动生成。时间窗口宽度、加班惩罚系数  设为若干组合，以考察成本与服务质量的权衡。文中还进行了大规模实验和敏感性分析，但总体思想是在不同权重配置下评估模型性能。

3.2 三指标模型对比 Big‑M 模型

实验首先比较 Big‑M 与三指标模型在 IBM CPLEX 中的直接求解效果。表 1（文中提及）给出了三指标模型以及其添加 SEC 或 Claus ATSP 加强后的结果，与 Big‑M 添加相同增强后的结果的几何平均求解时间。整体趋势是：

• 三指标模型明显更快：在 10 个客户时，三指标模型平均几秒即能求解，而 Big‑M 模型即便加上 Claus 加强仍需 128 秒以上；在 20 个客户时 Big‑M 模型基本不能在一小时内求得最优解。
• 大规模实例失败：当客户数为 30 时，三指标模型仍能解决多数实例，而 Big‑M 模型全部超时。

下图展示了不同布局在 30 个客户实例上的性能剖面（横轴为用时比，纵轴为累计解出比例）。可以看到，Big‑M 布局（红线）整体偏右，表示用时远高于其他布局；而三指标模型各布局的性能相对集中，且加入 SEC 或 Claus 加强可以进一步提升效率。

3.3 Benders 分解布局比较

作者尝试了八种主/子问题布局组合，并在 CPLEX 的黑盒 Benders 实现中进行了预实验。性能最好的布局是三指标(C) ：主问题仅包含 2‑index 与 3‑index 二元变量，时间窗口和场景相关变量全部放在子问题，且对 ATSP 部分适当加强。这一布局不仅避免了场景分解的不稳定性，还使 Benders 切割在整数解上有效执行。表 3 显示该布局在 30 节点实例上可解决 15 个以上的实例，而 Big‑M 布局几乎无法求解。

3.4 LP 界比较与敏感性分析

作者绘制了不同模型线性松弛的下界对比，横轴为 LP 松弛界与整数最优解的比率（即 ），纵轴为累计实例比例。如下图所示，三指标模型的曲线明显靠左，说明其线性放松较紧；Big‑M 模型松弛最差；在三指标模型中加入 Claus 加强可以进一步提升松弛质量。

此外，作者对权重  进行敏感性分析，观察时间窗口宽度、提前/延迟及加班时间的变化。结果表明，当时间窗口宽度的罚价很小（ 较小）时，模型倾向于将时间窗口缩至最小，导致 earliness 和 lateness 平均值均较高；而在  较大时，时间窗口较宽，提前/延迟现象显著减少，总成本增加有限。实验还指出，局部扰动场景比全局扰动场景更难求解，这与随机场景的集中性有关。

四、结论与展望

4.1 主要结论与贡献

本文针对城市配送场景下的随机旅行时间与时间窗口共决策问题，提出了一系列新模型与算法，核心贡献包括：

• 问题重新建模：将时间窗口指派与随机旅行时间融合为两阶段随机优化问题，四种成本权重体现多目标权衡。
• 三指标模型：通过三指标二元变量消除大常数，时间相关变量以位置索引，大幅提升线性松弛质量。
• 专门的 Benders 分解：提出变量划分策略、SEC 分离、场景聚合与暖启动启发式，使算法在整数解处高效生成切割，避免按场景分解的失败。
• 系统性对比与敏感性分析：通过大量实验比较 Big‑M 与三指标模型、多种 Benders 布局，并对参数进行敏感性分析，表明新方法在 30–40 个客户的实例上能够求得最优解，而传统方法仅能处理约 15–20 个客户。

4.2 未来研究方向

作者指出，TWATSP‑ST 仍然是配送优化中的核心问题，未来工作可从以下方面扩展：

• 多车辆或车队调度：现实中常有多车配送，需考虑车队协同。
• 离散时间窗口或顾客选择时间窗：将时间窗口设置为离散选项，允许客户选择或竞争。
• 更复杂的随机过程：引入空间相关或时间相关的随机旅行时间、需求等。
• 与实时调度结合：结合动态信息更新路径和时间窗口，实现滚动优化。

原文链接见文末，或扫下方交流群二维码。群内实时更新推文及原文 pdf，方便专家学者随时获取（若二维码失效，请翻阅扫描最新文章的二维码）。