LIPIcs.ESA.2016.21.pdf
- Filesize: 485 kB
- 13 pages
Document
Separation of Cycle Inequalities for the Periodic Timetabling Problem
Authors
-
Part of:
Volume:
24th Annual European Symposium on Algorithms (ESA 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: European Symposium on Algorithms (ESA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-08-18
Cite As Get BibTex
Ralf Borndörfer, Heide Hoppmann, and Marika Karbstein. Separation of Cycle Inequalities for the Periodic Timetabling Problem. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ESA.2016.21
Abstract
Cycle inequalities play an important role in the polyhedral study of the periodic timetabling problem. We give the first pseudo-polynomial time separation algorithm for cycle inequalities, and we give a rigorous proof for the pseudo-polynomial time separability of the change-cycle inequalities. The efficiency of these cutting planes is demonstrated on real-world instances of the periodic timetabling problem.
Subject Classification
Keywords
- periodic timetabling
- cycle inequalities
- separation algorithm
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Michael Bussieck. Gams - lop.gms: Line optimization. URL: http://www.gams.com/modlib/libhtml/lop.htm.
- M. Kümmling, P. Großmann, K. Nachtigall, J. Opitz, and R. Weiß. A state-of-the-art realization of cyclic railway timetable computation. Public Transport, 7(3):281-293, 2015. URL: http://dx.doi.org/10.1007/s12469-015-0108-5.
-
Christian Liebchen. Periodic timetable optimization in public transport. PhD thesis, Technische Universtität Berlin, 2006.
-
Christian Liebchen and Rolf H. Möhring. The modeling power of the periodic event scheduling problem: Railway timetables - and beyond. In Frank Geraets, Leo Kroon, Anita Schoebel, Dorothea Wagner, and Christos D. Zaroliagis, editors, Algorithmic Methods for Railway Optimization, volume 4359 of Lecture Notes in Computer Science, pages 3-40. Springer Berlin Heidelberg, 2007.
-
Christian Liebchen and Leon Peeters. Integral cycle bases for cyclic timetabling. Discrete Optimization, 6:98-109, 2009.
-
Christian Liebchen and Elmar Swarat. The Second Chvatal Closure Can Yield Better Railway Timetables. In Matteo Fischetti and Peter Widmayer, editors, 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08), volume 9 of OpenAccess Series in Informatics (OASIcs), Dagstuhl, Germany, 2008. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.
-
Thomas Lindner. Train Schedule Optimization in Public Rail Transport. PhD thesis, Technische Universtität Braunschweig, 2000.
-
K. Nachtigall and J. Opitz. Solving periodic timetable optimisation problems by modulo simplex calculations. In Matteo Fischetti and Peter Widmayer, editors, ATMOS'08, volume 9, 2008.
-
Karl Nachtigall. Periodic Network Optimization and Fixed Interval Timetables. Habilitation thesis, Universtität Hildesheim, 1998.
-
Michiel A. Odijk. Construction of periodic timetables, part 1: A cutting plane algorithm. Technical Report 94-61, TU Delft, 1994.
-
Leon W. P. Peeters. Cyclic Railway and Timetable Optimization. PhD thesis, Erasmus Universiteit Rotterdam, 2003.
-
Alexander Schrijver. Routing and timetabling by topological search. Documenta Mathematica, Extra Volume ICM 1998:1-9, 1998.
- P. Sels, T. Dewilde, D. Cattrysse, and P. Vansteenwegen. Reducing the passenger travel time in practice by the automated construction of a robust railway timetable. Transportation Research Part B: Methodological, 84:124-156, 2016. URL: http://dx.doi.org/10.1016/j.trb.2015.12.007.
-
Paolo Serafini and Walter Ukovich. A mathematical model for periodic scheduling problems. SIAM Journal on Discrete Mathematics, 2(4):550-581, 1989.