Branch and Price for Bus Driver Scheduling with Complex Break Constraints
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.
Cite
Text
Kletzander et al. "Branch and Price for Bus Driver Scheduling with Complex Break Constraints." AAAI Conference on Artificial Intelligence, 2021. doi:10.1609/AAAI.V35I13.17408Markdown
[Kletzander et al. "Branch and Price for Bus Driver Scheduling with Complex Break Constraints." AAAI Conference on Artificial Intelligence, 2021.](https://mlanthology.org/aaai/2021/kletzander2021aaai-branch/) doi:10.1609/AAAI.V35I13.17408BibTeX
@inproceedings{kletzander2021aaai-branch,
title = {{Branch and Price for Bus Driver Scheduling with Complex Break Constraints}},
author = {Kletzander, Lucas and Musliu, Nysret and Van Hentenryck, Pascal},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2021},
pages = {11853-11861},
doi = {10.1609/AAAI.V35I13.17408},
url = {https://mlanthology.org/aaai/2021/kletzander2021aaai-branch/}
}