融合列生成与大邻域搜索，解决带复杂休息规则的公交司机排班问题。
Integrating Column Generation and Large Neighborhood Search for Bus Driver Scheduling with Complex Break Constraints
- 用列生成和大邻域搜索结合，动态重用生成的列提升求解效率。
- 对小规模实例可得最优解，中等规模实例差距低于1%。
- 适合交通调度、物流排班等复杂约束优化场景使用。
公交司机排班问题（BDSP）是组合优化问题，目标是设计覆盖预设公交线路的班次，兼顾运营成本与司机满意度。该问题受严格法律条款和集体协议的强约束。本文提出先进精确与混合求解方法，适用于不同规模实例。研究包括分支定价法（B&P）与基于大邻域搜索（LNS）的框架，后者在修复阶段使用B&P或列生成（CG）。进一步提出一种深度集成方案：将LNS子问题中生成的列存储并复用于其他子问题，或寻找更优全局解。文章详细分析了方法各组件的影响，包括改进的高维资源受限最短路径问题（RCSPP）子问题求解及LNS结构。实验表明，本方法在所有规模实例上均达到新最优结果，小规模实例可获得精确解，中等规模实例与已知下界差距小于1%。结论显示，小规模问题以B&P为佳；大规模问题中，深度集成的LNS与CG能显著优于仅将CG作为黑箱使用的传统LNS。所提方法具通用性，可推广至其他规则集及相关优化问题。
原文摘要 · Abstract (English)
The Bus Driver Scheduling Problem (BDSP) is a combinatorial optimization problem with the goal to design shifts to cover prearranged bus tours. The objective takes into account the operational cost as well as the satisfaction of drivers. This problem is heavily constrained due to strict legal rules and collective agreements. The objective of this article is to provide state-of-the-art exact and hybrid solution methods that can provide high-quality solutions for instances of different sizes. This work presents a comprehensive study of both an exact method, Branch and Price (B&P), as well as a Large Neighborhood Search (LNS) framework which uses B&P or Column Generation (CG) for the repair phase to solve the BDSP. It further proposes and evaluates a novel deeper integration of B&P and LNS, storing the generated columns from the LNS subproblems and reusing them for other subproblems, or to find better global solutions. The article presents a detailed analysis of several components of the solution methods and their impact, including general improvements for the B&P subproblem, which is a high-dimensional Resource Constrained Shortest Path Problem (RCSPP), and the components of the LNS. The evaluation shows that our approach provides new state-of-the-art results for instances of all sizes, including exact solutions for small instances, and low gaps to a known lower bound for mid-sized instances. Conclusions: We observe that B&P provides the best results for small instances, while the tight integration of LNS and CG can provide high-quality solutions for larger instances, further improving over LNS which just uses CG as a black box. The proposed methods are general and can also be applied to other rule sets and related optimization problems
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。