OASIcs.ATMOS.2017.12.pdf
- Filesize: 0.85 MB
- 14 pages
Document
An Improved Algorithm for the Periodic Timetabling Problem
Authors
-
Part of:
Volume:
17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)
Series: Open Access Series in Informatics (OASIcs)
Conference: Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-09-04
Cite AsGet BibTex
Marc Goerigk and Christian Liebchen. An Improved Algorithm for the Periodic Timetabling Problem. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/OASIcs.ATMOS.2017.12
https://doi.org/10.4230/OASIcs.ATMOS.2017.12
Abstract
We consider the computation of periodic timetables, which is a key task in the service design process of public transportation companies. We propose a new approach for solving the periodic timetable optimisation problem. It consists of a (partially) heuristic network aggregation to reduce the problem size and make it accessible to standard mixed-integer programming (MIP) solvers. We alternate the invocation of a MIP solver with the well-known problem specific modulo network simplex heuristic (ModSim). This iterative approach helps the ModSim-method to overcome local minima efficiently, and provides the MIP solver with better initial solutions.
Our computational experiments are based on the 16 railway instances of the PESPlib, which is the only currently available collection of periodic event scheduling problem instances. For each of these instances, we are able to reduce the objective values of previously best known solutions by at least 10.0%, and up to 22.8% with our iterative combined method.
Keywords
- periodic timetabling
- railway optimisation
- modulo network simplex
- periodic event scheduling problem
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Valentina Cacchiani and Paolo Toth. Nominal and robust train timetabling problems. European Journal of Operational Research, 219(3):727-737, 2012.
-
Gabrio Caimi, Leo Kroon, and Christian Liebchen. Models for railway timetable optimization: Applicability and applications in practice. Journal of Rail Transport Planning &Management, 6:285-312, 2017.
-
Marc Goerigk, Michael Schachtebeck, and Anita Schöbel. Evaluating line concepts using travel times and robustness. Public Transport, 5(3):267-284, 2013.
-
Marc Goerigk and Anita Schöbel. Improving the modulo simplex algorithm for large-scale periodic timetabling. Computers &Operations Research, 40(5):1363-1370, 2013.
-
Marc Goerigk and Stephan Westphal. A combined local search and integer programming approach to the traveling tournament problem. Annals of Operations Research, 239(1):343-354, 2016.
-
Leo Kroon, Dennis Huisman, Erwin Abbink, Pieter-Jan Fioole, Matteo Fischetti, Gábor Maróti, Alexander Schrijver, Adri Steenbeek, and Roelof Ybema. The new Dutch timetable: The OR revolution. Interfaces, 39(1):6-17, 2009.
-
Christian Liebchen. Optimierungsverfahren zur Erstellung von Taktfahrplänen. Master’s thesis, Technical University Berlin, Germany, 1998. In German.
-
Christian Liebchen. Periodic Timetable Optimization in Public Transport. Dissertation.de - Verlag im Internet, 2006.
-
Christian Liebchen. The first optimized railway timetable in practice. Transportation Science, 42(4):420-435, 2008.
-
Christian Liebchen and Rolf H Möhring. The modeling power of the periodic event scheduling problem: railway timetables—and beyond. In Algorithmic methods for railway optimization, pages 3-40. Springer, 2007.
- Karl Nachtigall and Jens Opitz. Solving Periodic Timetable Optimisation Problems by Modulo Simplex Calculations. In 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08), volume 9 of OpenAccess Series in Informatics (OASIcs). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2008. URL: http://dx.doi.org/10.4230/OASIcs.ATMOS.2008.1588.
-
Michiel A Odijk. A constraint generation algorithm for the construction of periodic railway timetables. Transportation Research Part B: Methodological, 30(6):455-464, 1996.
- Julius Pätzold and Anita Schöbel. A Matching Approach for Periodic Timetabling. In 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016), volume 54 of OpenAccess Series in Informatics (OASIcs), pages 1-15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: http://dx.doi.org/10.4230/OASIcs.ATMOS.2016.1.
-
Paolo Serafini and Walter Ukovich. A mathematical model for periodic scheduling problems. SIAM Journal on Discrete Mathematics, 2(4):550-581, 1989.