Investigating Large Neighbourhood Search for Bus Driver Scheduling

Authors

  • Tommaso Mannelli Mazzoli DBAI, TU Wien, Vienna, Austria
  • Lucas Kletzander Christian Doppler Laboratory for Artificial Intelligence and Optimization for Planning and Scheduling, DBAI, Vienna, Austria
  • Pascal Van Hentenryck Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, USA
  • Nysret Musliu Christian Doppler Laboratory for Artificial Intelligence and Optimization for Planning and Scheduling, DBAI, Vienna, Austria

DOI:

https://doi.org/10.1609/icaps.v34i1.31495

Abstract

The Bus Driver Scheduling Problem (BDSP) is a combinatorial optimisation problem with high practical relevance. The aim is to assign bus drivers to predetermined routes while minimising a specified objective function that considers operating costs as well as employee satisfaction. Since we must satisfy several rules from a collective agreement and European regulations, the BDSP is highly constrained. Hence, using exact methods to solve large real-life-based instances is computationally too expensive, while heuristic methods still have a considerable gap to the optimum. Our paper presents a Large Neighbourhood Search (LNS) approach to solve the BDSP. We propose several novel destroy operators and an approach using column generation to repair the sub-problem. We analyse the impact of the destroy and repair operators and investigate various possibilities to select them, including adaptivity. The proposed approach improves all the upper bounds for larger instances that exact methods cannot solve, as well as for some mid-sized instances, and outperforms existing heuristic approaches for this problem on all benchmark instances.

Downloads

Published

2024-05-30

How to Cite

Mazzoli, T. M., Kletzander, L., Hentenryck, P. V., & Musliu, N. (2024). Investigating Large Neighbourhood Search for Bus Driver Scheduling. Proceedings of the International Conference on Automated Planning and Scheduling, 34(1), 360-368. https://doi.org/10.1609/icaps.v34i1.31495