Document Open Access Logo

Solving the Periodic Scheduling Problem: An Assignment Approach in Non-Periodic Networks

Authors Vera Grafe, Anita Schöbel

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2021.9.pdf
  • Filesize: 0.64 MB
  • 16 pages

Document Identifiers

Author Details

Vera Grafe
  • Technische Universität Kaiserslautern, Germany
Anita Schöbel
  • Technische Universität Kaiserslautern, Germany
  • Fraunhofer-Institut für Techno- und Wirtschaftsmathematik ITWM, Kaiserslautern, Germany

Cite AsGet BibTex

Vera Grafe and Anita Schöbel. Solving the Periodic Scheduling Problem: An Assignment Approach in Non-Periodic Networks. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/OASIcs.ATMOS.2021.9

Abstract

The periodic event scheduling problem (PESP) is a well researched problem used for finding good periodic timetables in public transport. While it is based on a periodic network consisting of events and activities which are repeated every period, we propose a new periodic timetabling model using a non-periodic network. This is a first step towards the goal of integrating periodic timetabling with other planning steps taking place in the aperiodic network, e.g. passenger assignment or delay management. In this paper, we develop the new model, show how we can reduce its size and prove its equivalence to PESP. We also conduct computational experiments on close-to real-world data from Lower Saxony, a region in northern Germany, and see that the model can be solved in a reasonable amount of time.

Subject Classification

ACM Subject Classification
  • Applied computing → Transportation
Keywords
  • Public Transport
  • Periodic Timetabling
  • PESP
  • Integer Programming

Metrics

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

References

  1. Ralf Borndörfer and Christian Liebchen. When Periodic Timetables Are Suboptimal. In Operations Research Proceedings 2007, pages 449-454. Springer Berlin Heidelberg, 2008. URL: https://doi.org/10.1007/978-3-540-77903-2_69.
  2. Ralf Borndörfer, Niels Lindner, and Sarah Roth. A concurrent approach to the periodic event scheduling problem. Journal of Rail Transport Planning & Management, 15, 2020. URL: https://doi.org/10.1016/j.jrtpm.2019.100175.
  3. Valentina Cacchiani and Paolo Toth. Robust train timetabling. In Handbook of Optimization in the Railway Industry, pages 93-115. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-72153-8_5.
  4. Carla Conte and Anita Schöbel. Identifying dependencies among delays. In proceedings of IAROR 2007, 2007. ISBN 978-90-78271-02-4. Google Scholar
  5. Twan Dollevoet, Dennis Huisman, Marie Schmidt, and Anita Schöbel. Delay propagation and delay management in transportation networks. In Handbook of Optimization in the Railway Industry, pages 285-317. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-72153-8_13.
  6. Laura Galli and Sebastian Stiller. Modern challenges in timetabling. In Handbook of Optimization in the Railway Industry, pages 117-140. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-72153-8_6.
  7. Marc Goerigk and Anita Schöbel. Improving the modulo simplex algorithm for large-scale periodic timetabling. Computers and Operations Research, 40(5):1363-1370, 2013. URL: https://doi.org/10.1016/j.cor.2012.08.018.
  8. Marc Goerigk and Anita Schöbel. Recovery-to-optimality: A new two-stage approach to robustness with an application to aperiodic timetabling. Computers and Operations Research, 52:1-15, 2014. Google Scholar
  9. Rob M. P. Goverde. Improving Punctuality and Transfer Reliability by Railway Timetable Optimization. Proceedings of the 5th TRAIL Annual Congress, 1999. Google Scholar
  10. Gurobi Optimization, LLC. Gurobi optimizer reference manual, 2021. Google Scholar
  11. Eva König. A review on railway delay management. Public Transport, 12(2):335-361, 2020. Google Scholar
  12. Christian Liebchen. Periodic timetable optimization in public transport. PhD thesis, TU Berlin, 2006. URL: https://doi.org/10.1007/978-3-540-69995-8_5.
  13. Christian Liebchen, Marco E. Lübbecke, Rolf H. Möhring, and Sebastian Stiller. The concept of recoverable robustness, linear programming recovery, and railway applications. Lecture Notes in Computer Science, 5868:1-27, 2009. URL: https://doi.org/10.1007/978-3-642-05465-5_1.
  14. Christian Liebchen, Michael Schachtebeck, Anita Schöbel, Sebastian Stiller, and André Prigge. Computing delay resistant railway timetables. Computers & Operations Research, 37:857-868, 2010. URL: https://doi.org/10.1016/j.cor.2009.03.022.
  15. Richard M. Lusby, Jesper Larsen, and Simon Bull. A survey on robustness in railway planning. European Journal of Operational Research, 266:1-15, 2018. Google Scholar
  16. Karl Nachtigall. Periodic network optimization with different arc frequencies. Discrete applied mathematics, 69:1-17, 1996. Google Scholar
  17. Karl Nachtigall. Periodic network optimization and fixed interval timetables. PhD thesis, University of Hildesheim, 1998. Google Scholar
  18. Karl Nachtigall and Jens Opitz. Solving periodic timetable optimisation problems by modulo simplex calculations. In OpenAccess Series in Informatics, volume 9, 2008. URL: https://doi.org/10.4230/OASIcs.ATMOS.2008.1588.
  19. Karl Nachtigall and Stefan Voget. A genetic algorithm approach to periodic railway synchronization. Computers and Operations Research, 23(5):453-463, 1996. URL: https://doi.org/10.1016/0305-0548(95)00032-1.
  20. Julius Pätzold and Anita Schöbel. A Matching Approach for Periodic Timetabling. In Marc Goerigk and Renato Werneck, editors, 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016), volume 54 of OpenAccess Series in Informatics (OASIcs), pages 1-15, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/OASIcs.ATMOS.2016.1.
  21. Leon Peeters. Cyclic Railway Timetable Optimization. PhD thesis, Erasmus Universiteit Rotterdam, 2003. Google Scholar
  22. Tomáš Robenek, Yousef Maknoon, Shadi Sharif Azadeh, Jianghang Chen, and Michel Bierlaire. Passenger centric train timetabling problem. Transportation Research Part B: Methodological, 89:107-126, 2016. URL: https://doi.org/10.1016/j.trb.2016.04.003.
  23. Alexander Schiewe, Sebastian Albert, Philine Schiewe, Anita Schöbel, and Felix Spühler. LinTim - Integrated Optimization in Public Transportation. URL: https://www.lintim.net.
  24. Alexander Schiewe, Sebastian Albert, Philine Schiewe, Anita Schöbel, and Felix Spühler. LinTim: An integrated environment for mathematical public transport optimization. Documentation for version 2020.12, 2020. URL: https://nbn-resolving.org/urn:nbn:de:hbz:386-kluedo-62025.
  25. Philine Schiewe and Anita Schöbel. Periodic timetabling with integrated routing: Towards applicable approaches. Transportation Science, 54(6):1714-1731, 2020. URL: https://doi.org/10.1287/trsc.2019.0965.
  26. Anita Schöbel. Capacity constraints in delay management. Public Transport, 1(2):135-154, 2009. Google Scholar
  27. Paolo Serafini and Walter Ukovich. A Mathematical Model for Periodic Scheduling Problems. SIAM Journal on Discrete Mathematics, 2:550-581, 1989. URL: https://doi.org/10.1137/0402049.
  28. Pieter Vansteenwegen and Dirk Van Oudheusden. Developing railway timetables which guarantee a better service. European Journal of Operational Research, 173(1):337-350, 2006. URL: https://doi.org/10.1016/j.ejor.2004.12.013.
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 Imprint Privacy Contact