Benders Decomposition for the Periodic Event Scheduling Problem
Please always quote using this URN: urn:nbn:de:0297-zib-83338
- 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.
Download full text files
Additional Services
| Author: | Niels LindnerORCiD, Rolf van LieshoutORCiD |
|---|---|
| Document Type: | ZIB-Report |
| Tag: | Benders Decomposition; Mixed-Integer Programming; Periodic Event Scheduling Problem; Periodic Timetabling |
| MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING |
| CCS-Classification: | J. Computer Applications |
| Date of first Publication: | 2021/09/01 |
| Series (Serial Number): | ZIB-Report (21-29) |
| ISSN: | 1438-0064 |
| Published in: | appeared in Operations Research Proceedings 2021 |
| DOI: | https://doi.org/10.1007/978-3-031-08623-6_43 |
