🤖 AI

Integrating Column Generation and Large Neighborhood Search for Bus Driver Scheduling with Complex Break Constraints

本文提出并评估了一种结合分支定价（B&P）与大邻域搜索（LNS）的混合算法，通过将 LNS 子问题生成的列存储并复用，有效解决了具有复杂休息约束的公交司机排班问题，并在不同规模实例上取得了优于现有方法的最新成果。

原作者： Lucas Kletzander, Tommaso Mannelli Mazzoli, Nysret Musliu, Pascal Van Hentenryck

发布于 2026-04-23

📖 1 分钟阅读☕ 轻松阅读

原作者： Lucas Kletzander, Tommaso Mannelli Mazzoli, Nysret Musliu, Pascal Van Hentenryck

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇文章讲述了一个关于如何给公交车司机排班的复杂数学问题，以及作者们如何发明了一套“超级排班系统”来解决它。

想象一下，你是一家大型公交公司的“排班经理”。你的任务非常艰巨：

任务：要把几十甚至几百条公交路线（就像一个个拼图块）分配给司机。
规则：法律和公司规定非常严格。司机不能连续开太久，中间必须休息，休息多久算“带薪”还是“ unpaid"（ unpaid 休息）都有讲究，甚至休息的时间点不同，算的钱也不一样。
目标：既要让公司省钱（少用司机、少换车），又要让司机开心（少加班、少换车、休息合理）。

这就好比你要用乐高积木搭出一座完美的城堡，但每一块积木都有奇怪的形状，而且你必须遵守“不能把红色积木放在蓝色积木上面”这种复杂的规则。

这篇论文就是作者们如何设计了两套“魔法工具”，并把它们完美结合起来，搭出了最完美的城堡。

1. 两个核心工具：精算师 vs. 装修大师

作者用了两种主要方法来解决问题：

工具 A：分支定价法 (Branch and Price) —— 像“精算师”

它是怎么工作的：这就好比一个极其严谨的精算师。他会把所有可能的排班方案（哪怕是一亿种）都列出来，然后像剥洋葱一样，一层一层地排除掉不可能的方案，直到找到那个绝对最优的解。
优点：对于小公司（比如只有 10 条路线），他能算出完美无缺的方案，告诉你“这就是全世界最好的排班，没有之一”。
缺点：如果路线太多（比如 200 条），这个精算师就会算到电脑冒烟，时间太长，根本算不完。

工具 B：大邻域搜索 (LNS) —— 像“装修大师”

它是怎么工作的：这就像一位装修大师。他先随便搭一个大概的城堡（初始方案），然后说：“哎呀，这几块积木搭得不好，拆掉！”（破坏阶段）。拆掉后，他再重新找最好的积木填进去（修复阶段）。
修复阶段：这里有个绝招，他请来了刚才那位“精算师”来帮忙填积木。因为拆掉的一小部分（比如 10 条路线）对精算师来说很简单，精算师能瞬间算出这部分的最优解。
优点：对于大公司（几百条路线），装修大师跑得非常快，而且能不断把城堡修得越来越好。
缺点：他不能保证找到“绝对完美”的解，只能保证“非常接近完美”。

2. 最大的创新：让“精算师”和“装修大师”握手言和

以前的做法是：装修大师拆完，把问题扔给精算师，精算师算完给个答案，然后把精算师脑子里记住的所有经验都清空，下次再拆另一部分时，精算师又要从头开始算。

这篇论文的突破在于：他们让精算师“记住”了经验！

作者设计了一种**“记忆共享”**机制：

积累宝藏：当精算师在修复某一部分时，他算出了很多种不错的排班方案（这些方案被称为“列”）。以前这些方案算完就扔了。现在，作者把这些方案存进一个公共宝库里。
** reuse（复用）**：下次装修大师再拆另一部分时，他不需要让精算师从头算，而是直接问：“宝库里有现成的好方案吗？”如果有，直接拿来用！这大大加快了速度。
后台助手：作者还安排了一个**“后台助手”**（后台线程）。当装修大师在前面忙得热火朝天时，后台助手就拿着宝库里的所有方案，在后台不停地尝试拼凑出更好的整体方案。一旦后台拼出了更好的，就立刻替换掉前面的方案。

3. 结果如何？

小公司：直接用“精算师”（分支定价法），几秒钟就能算出完美答案。
中等规模公司：用“装修大师 + 记忆共享 + 后台助手”的组合拳，效果最好。他们发现，把精算师算出的所有经验都存下来，并让后台助手在拼命拼凑，能产生惊人的效果。
大公司：这种组合拳依然能给出非常高质量的方案，比以前的任何方法都要好。

4. 总结：这不仅仅是排班

这就好比你在玩一个超级复杂的拼图游戏：

以前，大家要么死磕到底（算太慢），要么随便拼拼（质量差）。
现在，作者发明了一种**“智能拼图法”**：
- 遇到小块，用超级大脑（精算师）直接算出完美解。
- 遇到大块，用灵活的双手（装修大师）不断尝试。
- 最关键的是，他们建立了一个**“共享知识库”，让每一次尝试的经验都能被下一次尝试利用，并且有个“幕后推手”**在不停地把所有碎片拼得更好。

最终结论：这套方法不仅解决了公交车司机的排班难题，让公司省钱、司机开心，而且这种“精算 + 搜索 + 记忆共享”的思路，可以用来解决任何复杂的排班问题（比如医院护士排班、工厂工人调度等）。这就是为什么这篇文章被称为该领域的“新标杆”（State-of-the-art）。

这是一篇关于**公交司机调度问题（Bus Driver Scheduling Problem, BDSP）**的学术论文，标题为《将列生成（Column Generation）与大邻域搜索（Large Neighborhood Search）集成以解决具有复杂休息约束的公交司机调度问题》。

以下是对该论文的详细技术总结：

1. 问题背景与定义 (Problem Definition)

核心问题：BDSP 旨在为预先安排好的公交路线设计司机班次（Shifts），以覆盖所有行程（Bus Legs）。
目标函数：这是一个多目标优化问题，旨在最小化运营成本并最大化司机满意度。具体包括：
- 最小化总工作时间（含付费和未付费时间）。
- 最小化总时间跨度（Span）。
- 最小化空驶时间（Passive ride time）。
- 最小化车辆/路线变更次数（Changes）。
- 最小化班次拆分次数（Shift splits，即长休息导致的班次中断，司机通常不喜欢）。
复杂约束：
- 法律与集体协议：遵循奥地利私人巴士运营商的集体协议。
- 驾驶时间限制：最大驾驶时间 9 小时，每驾驶 4 小时必须休息。
- 休息规则：休息可拆分为多个部分（如 30 分钟、20 分钟或 15 分钟），且根据休息在班次中的位置（前 2 小时、后 2 小时或中间），休息可能是付费或免费的。
- 班次拆分：超过 3 小时的休息被视为班次拆分（Shift split），不计入工作时间，但会增加成本。
- 工作时长：最大 14 小时，付费工作时间通常有软性下限（6.5 小时）。

2. 方法论 (Methodology)

论文提出并评估了三种主要方法：精确算法（Branch and Price）、启发式算法（LNS）以及两者的紧密集成。

2.1 分支定价法 (Branch and Price, B&P) - 精确解法

框架：将问题分解为主问题（集合划分问题，Set Partitioning）和子问题（资源约束最短路径问题，RCSPP）。
子问题挑战：由于复杂的休息和驾驶约束，RCSPP 的标签（Label）具有高维性（11 个资源维度），导致非支配标签数量爆炸，计算缓慢。
关键优化技术：
1. 子问题划分：根据是否存在 30 分钟休息及其位置，将 RCSPP 拆分为三个独立的图（无 30 分钟休息、非居中 30 分钟休息、居中 30 分钟休息），简化支配规则。
2. 指数级弧节流（Exponential Arc Throttling）：在早期迭代中限制弧的成本，仅保留可能产生优质解的弧，加速收敛。
3. 改进的非支配标签消除：使用**k-d 树（k-d trees）和边界框（bounding boxes）**的两阶段算法替代传统的两两比较，显著降低了高维标签支配检查的时间复杂度。
4. 拉格朗日界：用于在列生成未完全收敛时提供下界。

2.2 大邻域搜索 (Large Neighborhood Search, LNS) - 启发式解法

框架：迭代地“破坏”当前解的一部分，然后“修复”该子问题。
破坏算子（Destroy Operators）：
- 均匀选择司机。
- 基于成本加权选择司机。
- 路线移除器（Tour Remover, $\omega_{tr}$ ）：这是论文提出的创新点。随机选择一个路线，移除所有驾驶该路线部分的司机。这利用了司机之间的结构共性，更容易找到有意义的重组。
修复算子（Repair Operators）：
- 使用列生成（CG）或完整的分支定价（B&P）来求解被移除司机构成的子问题。
- 实验表明，对于 LNS 中的子问题，仅使用列生成（CG）（在根节点求解）比完整的 B&P 更快且效果相当。

2.3 紧密集成 (Tight Integration of LNS and CG)

这是论文的核心创新，旨在打破 LNS 子问题之间的信息孤岛：

列存储与重用（Column Storage & Reuse, +r）：
- 将 LNS 子问题中生成的列（班次）存储在全局集合 $\hat{S}$ 中。
- 在后续的子问题求解中，直接初始化包含这些列，避免重复搜索。
- 策略：存储“最佳列”（best）或“全量列”（full）。
全局后台求解器（Global Background Solver, +b）：
- 启动一个后台线程，持续利用累积的全局列集合 $\hat{S}$ 求解整数主问题（MIP）。
- 如果后台求解器找到比当前 LNS 最佳解更好的解，则更新全局最佳解。
- 这使得 LNS 在局部搜索的同时，后台也在进行全局优化。

3. 关键贡献 (Key Contributions)

高维 RCSPP 的高效求解：提出了一套针对高维资源约束最短路径问题的优化方案（子问题划分、k-d 树支配检查、弧节流），解决了标签爆炸问题。
创新的破坏算子：提出了基于“路线（Tour）”的破坏算子 $\omega_{tr}$ ，显著提升了 LNS 在复杂约束下的搜索效率。
LNS 与 CG 的紧密集成：
- 提出了列重用机制，加速子问题求解。
- 提出了后台 MIP 求解机制，利用多核优势并行优化全局解。
- 证明了这种集成方法（特别是 lns+rb(f) 变体）在中等到大规模实例上优于单独使用 B&P 或 LNS。
新的最先进（SOTA）结果：在奥地利公交司机调度的公开基准测试集上，该方法在所有规模实例上均取得了最佳结果。

4. 实验结果 (Results)

测试环境：13 种规模（10 到 250 条路线）的 65 个实例。
B&P 表现：
- 在小规模实例（<30 条路线）上表现最佳，能证明最优解或提供极小的间隙（<0.4%）。
- 在大规模实例上计算时间过长，难以在限定时间内找到高质量解。
LNS 表现：
- 在中大规模实例上表现优异。
- 使用 lns+rb(f)（列重用 + 后台求解 + 存储全量列）的变体效果最好。
- 列重用（+r）：存储全量列（full）比仅存储最佳列（best）更能减少后台线程的内存压力并提高性能，因为避免了子问题生成大量次优列。
- 后台求解（+b）：显著提升了中等规模实例的解质量，且具有良好的“随时可用”（Any-time）特性。
对比分析：
- 与之前的 SOTA 方法（如 CMSA、模拟退火、禁忌搜索）相比，本文提出的集成方法在所有规模上均取得了更低的成本（GAP 更小）。
- 统计显著性检验（Friedman 检验和 Shaffer 事后检验）证实，lns+rb(f) 与其他所有方法存在显著差异，性能最优。

5. 意义与结论 (Significance & Conclusion)

实际应用价值：该方法能够处理现实世界中极其复杂的法律和行业约束（如奥地利集体协议），为公交公司提供了成本更低、司机满意度更高的排班方案。
通用性：虽然针对特定规则集，但解决高维 RCSPP 的技术（k-d 树、子问题划分）以及 LNS 与 CG 的集成策略（列重用、后台求解）具有通用性，可应用于其他人员调度或组合优化问题。
未来工作：计划将方法应用于不同规则集的 BDSP 以及其他类型的优化问题，并进一步优化后台线程中次优列的剔除机制。

总结：这篇论文通过结合精确算法（B&P）的严谨性和启发式算法（LNS）的扩展性，并创新性地引入了列重用和后台并行求解机制，成功解决了具有复杂休息约束的公交司机调度问题，确立了该领域新的最先进水平。