Integrating Column Generation and Large Neighborhood Search for Bus Driver Scheduling with Complex Break Constraints
Lucas Kletzander, Tommaso Mannelli Mazzoli, Nysret Musliu, Pascal Van Hentenryck · 2025
Read Integrating Column Generation and Large Neighborhood Search for Bus Driver Scheduling with Complex Break Constraints by Lucas Kletzander, Tommaso Mannelli Mazzoli, Nysret Musliu, Pascal Van Hentenryck (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-02485.txt.
Description
Bus companies must build driver shifts that cover every planned tour while obeying strict legal break rules and labor deals. Lucas Kletzander, Tommaso Mannelli Mazzoli, Nysret Musliu, and Pascal Van Hentenryck present new solution methods for that puzzle in this 2025 paper. The cost of the shifts and the drivers' satisfaction both count in the goal.
The team studies an exact method that builds shifts column by column, and a repair-based search that breaks and fixes parts of a plan. Their new step links the two: columns built while fixing one part of a plan are stored and reused for other parts or for better whole plans. Tests on varied sizes gave the best known results, with exact answers for small cases and small gaps for large ones. The study also weighs which parts of each method matter most.
Catalog record
| CREATOR | Lucas Kletzander, Tommaso Mannelli Mazzoli, Nysret Musliu, Pascal Van Hentenryck |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 93 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-02485