带多时间窗的多隔间车辆路径问题的滚动空间分支定价算法

论文信息

标题: A Rolling-Space Branch-and-Price Algorithm for the Multi-Compartment Vehicle Routing Problem with Multiple Time Windows

作者: El Mehdi Er Raqabi, Kevin Dalmeijer, Pascal Van Hentenryck

发布日期: 2026-01-22

arXiv ID: 2601.16194v1

PDF 链接: 下载 PDF

3 分钟速览

• 研究问题：这篇论文要解决带多时间窗的多隔间车辆路径问题（MCVRPMTW），同时考虑车厢隔间灵活性、物品与隔间兼容性、物品间兼容性以及司机休息等实际约束。
• 核心方法：作者设计了一种精确的分支定价（Branch-and-Price）算法，其中定价子问题用标签算法求解，并提出滚动空间分支定价算法结合聚类技术处理大规模实例。
• 关键结果：滚动空间分支定价算法在仅用平均 187.54 秒的情况下，达到了与精确算法仅 2.55% 的平均差距，而后者平均耗时 14,892 秒（见论文第 5.2 节，表 5.1）。
• 主要局限：精确分支定价算法在 35 个客户以上的实例中无法在限时内找到最优解；滚动空间算法属于启发式框架，无法保证解的最优性（见论文第 5.1 节实例分类和第 5.2 节计算时间）。
• 适合读者：运筹优化、物流调度、车辆路径问题领域的研究者与工程师，尤其是关注大规模实际应用场景的从业者。

论文背景和研究动机

现代物流面临两大挑战：一是需要同时配送互不兼容的多种产品（如冷冻、冷藏和常温品），这催生了多隔间车辆的应用；二是电商带来的末端配送需求要求精准的时间窗口控制，许多公司为客户提供多个可选交付时段。这两个方向独立看都已被学术界研究，但将它们联合起来考虑的工作几乎是空白。

本文由一项来自美国某大型企业的真实案例驱动。该企业每周需要将各类订单装载到具有多个隔间的车辆中，在城市客户之间进行为期一周的配送，同时满足每个客户在不同日子上的时间窗口偏好，以及驾驶员每天的工作时长和行驶距离限制。在实际操作中，路线规划高度依赖一位有二十年经验的调度员的手工编排，不仅效率有限，而且难以推广到其他工厂（见论文第 5.5 节）。

这种同时融合空间（隔间装载）、时间（多时间窗）和人员（驾驶员休息）约束的路由问题，在计算上极为复杂。作者指出，这是首个形式化定义并系统研究 MCVRPMTW 的工作，致力于提供一个既可用于实践，又具有方法论扩展性的通用算法框架。

核心方法和技术细节

问题建模

MCVRPMTW 被建模为一个集合划分问题，目标是最小化总路径成本，约束是每个客户恰好被一条路径访问一次。路径的定义隐式地包含了所有复杂约束，包括时间窗、隔间容量、物品兼容性以及驾驶员每日工作时长和行驶距离的上限。这种建模方式使得分支定价算法可以自然地继承列生成框架的优势。

分支定价算法

整个求解方法由精确的分支定价算法和面向大规模实例的滚动空间分支定价算法两部分构成。

在精确算法中，主问题是集合划分模型的线性松弛。定价子问题等价于一种带资源约束的最短路径问题（ESPPRC），增加了多时间窗选择、多隔间容量和兼容性约束。作者设计了一种标签算法来解决该子问题。每个标签存储当前节点、累加时间、累加成本、当天工作时长和行驶距离、各隔间负载和客户集合等信息。在标签沿弧扩展时，要对时间窗选择、隔间分配以及是否插入过夜休息做出决策，并通过资源扩展函数生成新标签。

标签数量会随着问题规模的增加而爆炸。为此，作者提出了两种支配规则来剪枝。同日支配规则只在同一天内比较标签，而跨日支配规则允许较早日期的标签以更宽松的条件支配较晚日期的标签，只要前者在插入一个强制休息后能在时间上 “追上” 后者（见论文第 4.1.4 节的命题 2 证明）。此外，算法还采用了弧过滤、激进支配规则（在迭代早期允许一定松弛度）、列选择策略和深度搜索启发式等加速手段。

滚动空间算法

为了处理最多 400 个客户的大规模实例，作者将聚类技术与分支定价相结合。客户首先被划分成若干重叠的空间簇，在每个簇内部独立运行精确分支定价生成候选路径，再通过一个多隔间可行性检验模型过滤掉违反装载约束的路径（见论文第 4.2 节）。只有通过检验的路径才被加入到全局主问题中。这一设计避免了让定价问题直接面对全部客户而导致的计算灾难，同时通过重叠聚类保证了路径在空间上的良好覆盖。

创新点和贡献

论文的核心贡献可以归纳为四个方面。第一，它首次形式化地提出了 MCVRPMTW 问题，同时融合多车厢和多时间窗两大现实约束，并纳入驾驶员休息等操作细节。第二，在分支定价框架内提出了同日和跨日两种严格的标签支配规则，后者特别针对多天运营场景，能有效抑制因休息插入引起的标签膨胀（见论文第 4.1.4 节命题 1 和 2）。第三，设计了滚动空间分支定价算法，将聚类与列生成有机结合，使精确算法思想可以延展到大规模实例。第四，基于来自工业界的真实数据构建了一套基准实例，并通过详尽的实验展示了算法性能和不同参数对结果的影响，为管理者提供了具体可量化的决策依据。例如，实际案例中优化方案比人工方案减少约 20% 的车辆使用量和约 7,000 公里的总行驶距离，仅单工厂每年就可节省约 $250,000（见论文第 5.5 节）。

实验结果分析

作者生成了两类实例：中等规模（10–40 个客户，M1–M7）和大规模（50–400 个客户，L1–L7）。精确分支定价算法能在 M1–M5 上证明最优性，平均耗时约 14,892 秒；在 M6 和 M7 上则达到 36,000 秒的时间上限而未证明最优（见论文第 5.2 节，表 5.1）。滚动空间分支定价算法在中等实例上以平均 187.54 秒获得与最优解仅 2.55% 的平均差距，在大规模实例上相比一种简单的标签启发式算法平均可节省约 5% 的总成本，并始终使用更少的车辆（见表 5.2）。

关于隔间数量的灵敏度分析表明，将隔间数从 2 增加到 6，中等实例的平均车辆数从 4 下降到 2，目标值从 3,386 下降到约 3,078（见表 5.4）。但隔间数从 6 增加到 8 时，改进趋于饱和。在时间窗口维度，多时间窗配置相比单时间窗使平均目标值和车辆数进一步下降，但同时拉长了计算时间（见表 5.5）。

从加速策略的消融实验来看，去掉任何一种加速手段都会增加计算时间或降低解质量，尤其是移除深度搜索启发式或弧过滤策略后，计算时间几乎翻倍，甚至在大实例上使得求解器在时间上限内无法给出更优解（见第 5.3 节，表 5.3）。

实践建议

对于面临类似多产品、多时间窗配送场景的物流企业，本文提供了明确的路径优化思路。首先，如果客户数量控制在 30 个左右且对最优性要求高，可以直接使用精确分支定价算法。其次，当问题规模超过 50 个客户时，建议采用滚动空间分支定价框架，将客户按空间聚类后分别求解再整合，能在分钟到小时级别获得高质量近似解。在车辆配置层面，适度增加隔间数量（如从 2 个增加到 4–6 个）可以显著降低所需车辆数和行驶里程，但应结合车辆购置与改造成本综合权衡。在时间窗口层面，为客户提供多个时间选项虽然会增加调度复杂度，但能在不增加车辆前提下吸收更多需求波动，提升服务效率。论文中来自工业伙伴的反馈还表明，将优化算法嵌入日常运营后，企业不仅可以节省直接物流成本，还能减少对人工经验的过度依赖，提高在面对需求变化时的场景分析和应变能力。