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

CREATORLucas Kletzander, Tommaso Mannelli Mazzoli, Nysret Musliu, Pascal Van Hentenryck
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE93 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-02485

Browse the full library · About the Tower of Babel