Document Open Access Logo

A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable

Authors Ralf Borndörfer, Marika Karbstein, Christian Liebchen, Niels Lindner

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2018.16.pdf
  • Filesize: 466 kB
  • 15 pages

Document Identifiers

Author Details

Ralf Borndörfer
  • Zuse Institute Berlin (ZIB), Takustr. 7, 14195 Berlin, Germany
Marika Karbstein
  • Zuse Institute Berlin (ZIB), Takustr. 7, 14195 Berlin, Germany
Christian Liebchen
  • Technical University of Applied Sciences Wildau, Hochschulring 1, 15745 Wildau, Germany
Niels Lindner
  • Zuse Institute Berlin (ZIB), Takustr. 7, 14195 Berlin, Germany

Cite AsGet BibTex

Ralf Borndörfer, Marika Karbstein, Christian Liebchen, and Niels Lindner. A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/OASIcs.ATMOS.2018.16

Abstract

We consider the following planning problem in public transportation: Given a periodic timetable, how many vehicles are required to operate it? In [Julius Paetzold et al., 2017], for this sequential approach, it is proposed to first expand the periodic timetable over time, and then answer the above question by solving a flow-based aperiodic optimization problem. In this contribution we propose to keep the compact periodic representation of the timetable and simply solve a particular perfect matching problem. For practical networks, it is very much likely that the matching problem decomposes into several connected components. Our key observation is that there is no need to change any turnaround decision for the vehicles of a line during the day, as long as the timetable stays exactly the same.

Subject Classification

ACM Subject Classification
  • Applied computing → Transportation
  • Mathematics of computing → Matchings and factors
  • Mathematics of computing → Network flows
Keywords
  • Vehicle Scheduling
  • Periodic Timetabling
  • Bipartite Matching

Metrics

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

References

  1. Ralf Borndörfer, Martin Grötschel, and Ulrich Jäger. Planning problems in public transit. Production Factor Mathematics, pages 95-122, 2010. URL: http://dx.doi.org/10.1007/978-3-642-11248-5.
  2. Ralf Borndörfer, Heide Hoppmann, and Marika Karbstein. Separation of cycle inequalities for the periodic timetabling problem. In ESA, volume 57 of LIPIcs, pages 21:1-21:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. Google Scholar
  3. Stefan Bunte and Natalia Kliewer. An overview on vehicle scheduling models. Public Transport, 1(4):299-317, 2009. Google Scholar
  4. Soumya Dutta, Narayan Rangaraj, Madhu Belur, Shashank Dangayach, and Karuna Singh. Construction of periodic timetables on a suburban rail network-case study from Mumbai. In RailLille 2017 — 7th International Conference on Railway Operations Modelling and Analysis, 2017. Google Scholar
  5. 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. URL: http://dx.doi.org/10.4230/OASIcs.ATMOS.2017.12.
  6. Christian Liebchen. The first optimized railway timetable in practice. Transportation Science, 42(4):420-435, 2008. Google Scholar
  7. Christian Liebchen and Leon Peeters. Integral cycle bases for cyclic timetabling. Discrete Optimization, 6(1):98-109, 2009. Google Scholar
  8. Morten N. Nielsen, Bjørn Hove, and Jens Clausen. Constructing periodic timetables using MIP - a case study from DSB S-train. International Journal of Operational Research, 1(3):213-227, 2006. Google Scholar
  9. 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. URL: http://dx.doi.org/10.4230/OASIcs.ATMOS.2017.17.
  10. 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:1-1:15, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/OASIcs.ATMOS.2016.1.
  11. Alexander Schrijver. Combinatorial Optimization - Polyhedra and Efficiency. Springer, 2003. Google Scholar
  12. 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 Imprint Privacy Contact