Branch and Price for Bus Driver Scheduling with Complex Break Constraints

Authors

  • Lucas Kletzander TU Wien
  • Nysret Musliu TU Wien
  • Pascal Van Hentenryck Georgia Institute of Technology

Keywords:

Scheduling, Transportation, Constraint Optimization, Applications

Abstract

This paper presents a Branch and Price approach for a real-life Bus Driver Scheduling problem with a complex set of break constraints. The column generation uses a set partitioning model as master problem and a resource constrained shortest path problem as subproblem. Due to the complex constraints, the branch and price algorithm adopts several novel ideas to improve the column generation in the presence of a high-dimensional subproblem, including exponential arc throttling and a dedicated two-stage dominance algorithm. Evaluation on a publicly available set of benchmark instances shows that the approach provides the first provably optimal solutions for small instances, improving best-known solutions or proving them optimal for 48 out of 50 instances, and yielding an optimality gap of less than 1% for more than half the instances.

Downloads

Published

2021-05-18

How to Cite

Kletzander, L., Musliu, N., & Van Hentenryck, P. (2021). Branch and Price for Bus Driver Scheduling with Complex Break Constraints. Proceedings of the AAAI Conference on Artificial Intelligence, 35(13), 11853-11861. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17408

Issue

Section

AAAI Technical Track on Planning, Routing, and Scheduling