Benders Decomposition for the Periodic Event Scheduling Problem

Niels Lindner () and Rolf Lieshout ()
Additional contact information
Niels Lindner: Zuse Institute Berlin
Rolf Lieshout: Eindhoven University of Technology

A chapter in Operations Research Proceedings 2021, 2022, pp 289-294 from Springer

Abstract: Abstract 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.

Keywords: Periodic timetabling; Periodic event scheduling problem; Benders decomposition; Mixed integer programming (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:lnopch:978-3-031-08623-6_43

Ordering information: This item can be ordered from
http://www.springer.com/9783031086236

DOI: 10.1007/978-3-031-08623-6_43

Access Statistics for this chapter

More chapters in Lecture Notes in Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().