Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

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

Export metadata

Metadaten
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
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.