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

Separation of cycle inequalities in periodic timetabling

  • Cycle inequalities play an important role in the polyhedral study of the periodic timetabling problem in public transport. We give the first pseudo-polynomial time separation algorithm for cycle inequalities, and we contribute a rigorous proof for the pseudo-polynomial time separability of the change-cycle inequalities. Moreover, we provide several NP-completeness results, indicating that pseudo-polynomial time is best possible. The efficiency of these cutting planes is demonstrated on real-world instances of the periodic timetabling problem.
Author:Ralf BorndörferORCiD, Heide Hoppmann, Marika Karbstein, Niels LindnerORCiD
Document Type:Article
Parent Title (English):Discrete Optimization
First Page:100552
Year of first publication:2020
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.