Document Open Access Logo

Recoverable Robust Periodic Timetabling

Authors Vera Grafe , Anita Schöbel

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2023.9.pdf
  • Filesize: 0.73 MB
  • 16 pages

Document Identifiers

Author Details

Vera Grafe
  • RPTU Kaiserslautern-Landau, Kaiserslautern, Germany
Anita Schöbel
  • RPTU Kaiserslautern-Landau, Kaiserslautern, Germany
  • Fraunhofer-Institute for Industrial Mathematics ITWM, Kaiserslautern, Germany

Cite As Get BibTex

Vera Grafe and Anita Schöbel. Recoverable Robust Periodic Timetabling. In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/OASIcs.ATMOS.2023.9

Abstract

We apply the concept of recoverable robustness to periodic timetabling, resulting in the Recoverable Robust Periodic Timetabling Problem (RRPT), which integrates periodic timetabling and delay management. Although the computed timetable is periodic, the model is able to take the aperiodicity of the delays into account. This is an important step in finding a good trade-off between short travel times and delay resistance. We present three equivalent formulations for this problem, differing in the way the timetabling subproblem is handled, and compare them in a first experimental study. We also show that our model yields solutions of high quality.

Subject Classification

ACM Subject Classification
  • Applied computing → Transportation
  • Mathematics of computing → Discrete mathematics
Keywords
  • Public Transport
  • Recoverable Robustness
  • Periodic Timetabling
  • Delay Management
  • Mixed Integer Programming

Metrics

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

References

  1. 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.
  2. Valentina Cacchiani and Paolo Toth. Nominal and robust train timetabling problems. European Journal of Operational Research, 219(3):727-737, 2012. URL: https://doi.org/10.1016/j.ejor.2011.11.003.
  3. 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.
  4. Matteo Fischetti and Michele Monaci. Light Robustness, pages 61-84. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009. URL: https://doi.org/10.1007/978-3-642-05465-5_3.
  5. Michael Gatto, Riko Jacob, Leon Peeters, and Anita Schöbel. The computational complexity of delay management. In Dieter Kratsch, editor, Graph-Theoretic Concepts in Computer Science, pages 227-238, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. Google Scholar
  6. Marc Goerigk. Exact and heuristic approaches to the robust periodic event scheduling problem. Public Transport, 7(1):101-119, 2015. URL: https://doi.org/10.1007/s12469-014-0100-5.
  7. Marc Goerigk and Anita Schöbel. An Empirical Analysis of Robustness Concepts for Timetabling. In Thomas Erlebach and Marco Lübbecke, editors, 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10), volume 14 of OpenAccess Series in Informatics (OASIcs), pages 100-113, Dagstuhl, Germany, 2010. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/OASIcs.ATMOS.2010.100.
  8. Vera Grafe and Anita Schöbel. Robust periodic timetables. Working paper. Google Scholar
  9. Vera Grafe and Anita Schöbel. Solving the Periodic Scheduling Problem: An Assignment Approach in Non-Periodic Networks. In Matthias Müller-Hannemann and Federico Perea, editors, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021), volume 96 of Open Access Series in Informatics (OASIcs), pages 9:1-9:16, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/OASIcs.ATMOS.2021.9.
  10. Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023. URL: https://www.gurobi.com.
  11. Eva König. A review on railway delay management. Public Transport, 12(2):335-361, 2020. Google Scholar
  12. Leo Kroon, Rommert Dekker, and Michiel Vromans. Cyclic railway timetabling: A stochastic optimization approach. In Lecture Notes in Computer Science, volume 4359 LNCS, pages 41-68, 2007. URL: https://doi.org/10.1007/978-3-540-74247-0_2.
  13. Leo Kroon, Gabor Maroti, Mathijn Retel Helmrich, Michiel Vromans, and Rommert Dekker. Stochastic improvement of cyclic railway timetables. Transportation Research. Part B, Methodological, 42(6):553-570, 2008. URL: https://doi.org/10.1016/j.trb.2007.11.002.
  14. 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.
  15. Christian Liebchen, Marco Lübbecke, Rolf Möhring, and Sebastian Stiller. Recoverable Robustness. Technical report, Technische Universität Berlin, 2007. Google Scholar
  16. 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.
  17. 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
  18. Karl Nachtigall. A branch and cut approach for periodic network programming. Technical report, University of Hildesheim, 1994. Google Scholar
  19. Karl Nachtigall. Periodic network optimization and fixed interval timetables. PhD thesis, University of Hildesheim, 1998. Google Scholar
  20. Michiel A. Odijk. A constraint generation algorithm for the construction of periodic railway timetables. Transportation Research Part B: Methodological, 30(6):455-464, 1996. URL: https://doi.org/10.1016/0191-2615(96)00005-7.
  21. Julius Pätzold. Finding robust periodic timetables by integrating delay management. Public Transport, 13(2):349-374, 2021. URL: https://doi.org/10.1007/s12469-020-00260-y.
  22. Leon Peeters. Cyclic Railway Timetable Optimization. PhD thesis, Erasmus Universiteit Rotterdam, 2003. Google Scholar
  23. Gert-Jaap Polinder, Thomas Breugem, Twan Dollevoet, and Gábor Maróti. An adjustable robust optimization approach for periodic timetabling. Transportation Research Part B: Methodological, 128:50-68, 2019. URL: https://doi.org/10.1016/j.trb.2019.07.011.
  24. Michael Schachtebeck. Delay Management in Public Transportation: Capacities, Robustness, and Integration. PhD thesis, University of Göttingen, 2009. Google Scholar
  25. Alexander Schiewe, Sebastian Albert, Vera Grafe, Philine Schiewe, Anita Schöbel, and Felix Spühler. LinTim - Integrated Optimization in Public Transportation. URL: https://www.lintim.net.
  26. Anita Schöbel. Integer programming approaches for solving the delay management problem. Lecture Notes in Computer Science, 4359 LNCS:145-170, 2007. URL: https://doi.org/10.1007/978-3-540-74247-0_7.
  27. Anita Schöbel. Capacity constraints in delay management. Public Transport, 1(2):135-154, 2009. Google Scholar
  28. 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.
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