Document Open Access Logo

An Improved Algorithm for the Periodic Timetabling Problem

Authors Marc Goerigk, Christian Liebchen

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2017.12.pdf
  • Filesize: 0.85 MB
  • 14 pages

Document Identifiers

Author Details

Marc Goerigk
Christian Liebchen

Cite As Get 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

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.

Subject Classification

Keywords
  • periodic timetabling
  • railway optimisation
  • modulo network simplex
  • periodic event scheduling problem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Valentina Cacchiani and Paolo Toth. Nominal and robust train timetabling problems. European Journal of Operational Research, 219(3):727-737, 2012. Google Scholar
  2. 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. Google Scholar
  3. Marc Goerigk, Michael Schachtebeck, and Anita Schöbel. Evaluating line concepts using travel times and robustness. Public Transport, 5(3):267-284, 2013. Google Scholar
  4. Marc Goerigk and Anita Schöbel. Improving the modulo simplex algorithm for large-scale periodic timetabling. Computers &Operations Research, 40(5):1363-1370, 2013. Google Scholar
  5. 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. Google Scholar
  6. 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. Google Scholar
  7. Christian Liebchen. Optimierungsverfahren zur Erstellung von Taktfahrplänen. Master’s thesis, Technical University Berlin, Germany, 1998. In German. Google Scholar
  8. Christian Liebchen. Periodic Timetable Optimization in Public Transport. Dissertation.de - Verlag im Internet, 2006. Google Scholar
  9. Christian Liebchen. The first optimized railway timetable in practice. Transportation Science, 42(4):420-435, 2008. Google Scholar
  10. 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. Google Scholar
  11. 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.
  12. Michiel A Odijk. A constraint generation algorithm for the construction of periodic railway timetables. Transportation Research Part B: Methodological, 30(6):455-464, 1996. Google Scholar
  13. 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.
  14. Paolo Serafini and Walter Ukovich. A mathematical model for periodic scheduling problems. SIAM Journal on Discrete Mathematics, 2(4):550-581, 1989. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact