Document Open Access Logo

Integrating Line Planning for Construction Sites into Periodic Timetabling via Track Choice

Authors Berenike Masing , Niels Lindner , Christian Liebchen

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2023.5.pdf
  • Filesize: 0.75 MB
  • 15 pages

Document Identifiers

Author Details

Berenike Masing
  • Zuse Institute Berlin, Germany
Niels Lindner
  • Freie Universität Berlin, Germany
Christian Liebchen
  • Technical University of Applied Sciences Wildau, Germany

Acknowledgements

We would like to thank DB Netz AG for providing us with data and sharing their experience and insights.

Cite As Get BibTex

Berenike Masing, Niels Lindner, and Christian Liebchen. Integrating Line Planning for Construction Sites into Periodic Timetabling via Track Choice. In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/OASIcs.ATMOS.2023.5

Abstract

We consider maintenance sites for urban rail systems, where unavailable tracks typically require changes to the regular timetable, and often even to the line plan. In this paper, we present an integrated mixed-integer linear optimization model to compute an optimal line plan that makes best use of the available tracks, together with a periodic timetable, including its detailed routing on the tracks within the stations. The key component is a flexible, turn-sensitive event-activity network that allows to integrate line planning and train routing using a track choice extension of the Periodic Event Scheduling Problem (PESP). Major goals are to maintain as much of the regular service as possible, and to keep the necessary changes rather local. Moreover, we present computational results on real construction site scenarios on the S-Bahn Berlin network. We demonstrate that this integrated problem is indeed solvable on practically relevant instances.

Subject Classification

ACM Subject Classification
  • Applied computing → Transportation
  • Mathematics of computing → Combinatorial optimization
Keywords
  • Periodic Timetabling
  • Line Planning
  • Track Choice
  • Mixed-Integer Programming
  • Construction Sites
  • Railway Rescheduling

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:100175, 2020. Best Papers of RailNorrköping 2019. URL: https://doi.org/10.1016/j.jrtpm.2019.100175.
  2. Enrico Bortoletto, Niels Lindner, and Berenike Masing. Tropical Neighbourhood Search: A New Heuristic for Periodic Timetabling. In DROPS-IDN/17107. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/OASIcs.ATMOS.2022.3.
  3. Gabrio Caimi, Martin Fuchsberger, Marco Laumanns, and Kaspar Schüpbach. Periodic railway timetabling with event flexibility. Networks, 57(1):3-18, 2011. URL: https://doi.org/10.1002/net.20379.
  4. Florian Fuchs, Alessio Trivella, and Francesco Corman. Enhancing the interaction of railway timetabling and line planning with infrastructure awareness. Transportation Research Part C: Emerging Technologies, 142:103805, September 2022. URL: https://doi.org/10.1016/j.trc.2022.103805.
  5. Marc Goerigk. Exact and heuristic approaches to the robust periodic event scheduling problem. Public Transport, 7(1):101-119, March 2015. URL: https://doi.org/10.1007/s12469-014-0100-5.
  6. Marc Goerigk and Christian Liebchen. An Improved Algorithm for the Periodic Timetabling Problem. In Gianlorenzo D'Angelo and Twan Dollevoet, editors, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017), volume 59 of OpenAccess Series in Informatics (OASIcs), pages 12:1-12:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. ISSN: 2190-6807. URL: https://doi.org/10.4230/OASIcs.ATMOS.2017.12.
  7. Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2022. URL: https://www.gurobi.com.
  8. Christian Liebchen. Periodic timetable optimization in public transport. PhD thesis, Dissertation.de, Berlin, 2006. Google Scholar
  9. 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, pages 3-40, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg. Google Scholar
  10. Thomas Lindner. Train Scheduling in Public Rail Transport. PhD thesis, Technische Universität Braunschweig, June 2000. URL: https://publikationsserver.tu-braunschweig.de/receive/dbbs_mods_00001135.
  11. Berenike Masing, Niels Lindner, and Patricia Ebert. Forward and Line-Based Cycle Bases for Periodic Timetabling. Operations Research Forum, 4(3):53, June 2023. URL: https://doi.org/10.1007/s43069-023-00229-0.
  12. Berenike Masing, Niels Lindner, and Christian Liebchen. Periodic Timetabling with Integrated Track Choice for Railway Construction Sites, 2022. URL: https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/8862.
  13. Gonçalo P. Matos, Luís M. Albino, Ricardo L. Saldanha, and Ernesto M. Morgado. Solving periodic timetabling problems with SAT and machine learning. Public Transport, 13(3):625-648, October 2021. URL: https://doi.org/10.1007/s12469-020-00244-y.
  14. Karl Nachtigall. Periodic Network Optimization and Fixed Interval Timetables. Habilitation thesis, Universität Hildesheim, 1998. Google Scholar
  15. Leon Peeters. Cyclic Railway Timetable Optimization. PhD thesis, Erasmus Universiteit Rotterdam, January 2003. Google Scholar
  16. Julius Pätzold, Alexander Schiewe, Philine Schiewe, and Anita Schöbel. Look-Ahead Approaches for Integrated Planning in Public Transportation. In Gianlorenzo D'Angelo and Twan Dollevoet, editors, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017), volume 59 of OpenAccess Series in Informatics (OASIcs), pages 17:1-17:16, Dagstuhl, Germany, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. ISSN: 2190-6807. URL: https://doi.org/10.4230/OASIcs.ATMOS.2017.17.
  17. Philine Schiewe. Integrated Optimization in Public Transport Planning, volume 160 of Springer Optimization and Its Applications. Springer International Publishing, Cham, 2020. URL: https://doi.org/10.1007/978-3-030-46270-3.
  18. Anita Schöbel. Line planning in public transportation: models and methods. OR Spectrum, 34(3):491-510, July 2012. URL: https://doi.org/10.1007/s00291-011-0251-6.
  19. Anita Schöbel. An eigenmodel for iterative line planning, timetabling and vehicle scheduling in public transportation. Transportation Research Part C: Emerging Technologies, 74:348-365, January 2017. URL: https://doi.org/10.1016/j.trc.2016.11.018.
  20. Anita Schöbel and Susanne Scholl. Line Planning with Minimal Traveling Time. In Leo G. Kroon and Rolf H. Möhring, editors, 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05), volume 2 of OpenAccess Series in Informatics (OASIcs), Dagstuhl, Germany, 2006. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. ISSN: 2190-6807. URL: https://doi.org/10.4230/OASIcs.ATMOS.2005.660.
  21. Paolo Serafini and Walter Ukovich. A Mathematical Model for Periodic Scheduling Problems. SIAM Journal on Discrete Mathematics, 2(4):550-581, November 1989. URL: https://doi.org/10.1137/0402049.
  22. Sander Van Aken, Nikola Bešinović, and Rob M. P. Goverde. Designing alternative railway timetables under infrastructure maintenance possessions. Transportation Research Part B: Methodological, 98:224-238, April 2017. URL: https://doi.org/10.1016/j.trb.2016.12.019.
  23. Raimond Wüst, Stephan Bütikofer, Severin Ess, Claudio Gomez, Albert Steiner, Marco Laumanns, and Jacint Szabo. Improvement of maintenance timetable stability based on iteratively assigning event flexibility in FPESP. In Anders Peterson, Martin Joborn, and Markus Bohlin, editors, RailNorrköping 2019, Linköping Electronic Conference Proceedings ; 69, pages 1160-1177, Linköping, September 2019. Linköping University Electronic Press. URL: https://doi.org/10.21256/zhaw-18282.
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