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