Benders Decomposition for the Periodic Event Scheduling Problem
- The Periodic Event Scheduling Problem (PESP) is the central mathematical model behind the optimization of periodic timetables in public transport. We apply Benders decomposition to the incidence-based MIP formulation of PESP. The resulting formulation exhibits particularly nice features: The subproblem is a minimum cost network flow problem, and feasibility cuts are equivalent to the well-known cycle inequalities by Odijk. We integrate the Benders approach into a branch-and-cut framework, and assess the performance of this method on instances derived from the benchmarking library PESPlib.
Additional Services
| Author: | Niels LindnerORCiD, Rolf van LieshoutORCiD |
|---|---|
| Document Type: | In Proceedings |
| Parent Title (English): | Operations Research Proceedings 2021 |
| First Page: | 289 |
| Last Page: | 294 |
| Publisher: | Springer International Publishing |
| Place of publication: | Cham |
| Year of first publication: | 2022 |
| Preprint: | urn:nbn:de:0297-zib-83338 |
| DOI: | https://doi.org/10.1007/978-3-031-08623-6_43 |
