Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
L. Kletzander, N. Musliu, P. Van Hentenryck:
"Branch and Price for Bus Driver Scheduling with Complex Break Constraints";
Vortrag: 35th AAAI 2021,
virtual event;
02.02.2021
- 09.02.2021; in: "Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, {IAAI} 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, {EAAI} 2021, Virtual Event, February 2-9, 2021",
(2021),
S. 11853
- 11861.
Kurzfassung englisch:
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.
Schlagworte:
Scheduling, Transportation, Constraint Optimization, Applications
Zugeordnete Projekte:
Projektleitung Nysret Musliu:
ARTIOS
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.