Robustness as a Third Dimension for Evaluating Public Transport Plans

Authors Markus Friedrich, Matthias Müller-Hannemann , Ralf Rückert, Alexander Schiewe, Anita Schöbel



PDF
Thumbnail PDF

File

OASIcs.ATMOS.2018.4.pdf
  • Filesize: 1.38 MB
  • 17 pages

Document Identifiers

Author Details

Markus Friedrich
  • Institut für Straßen- und Verkehrswesen, Universität Stuttgart, Pfaffenwaldring 7, D 70569 Stuttgart, Germany
Matthias Müller-Hannemann
  • Institut für Informatik, Martin-Luther-Universität Halle-Wittenberg, Von-Seckendorff-Platz 1, D 06120 Halle (Saale), Germany
Ralf Rückert
  • Institut für Informatik, Martin-Luther-Universität Halle-Wittenberg, Von-Seckendorff-Platz 1, D 06120 Halle (Saale), Germany
Alexander Schiewe
  • Institut für Numerische und Angewandte Mathematik, Universität Göttingen, Lotzestr. 16-18, D 37083 Göttingen, Germany
Anita Schöbel
  • Institut für Numerische und Angewandte Mathematik, Universität Göttingen, Lotzestr. 16-18, D 37083 Göttingen, Germany

Cite AsGet BibTex

Markus Friedrich, Matthias Müller-Hannemann, Ralf Rückert, Alexander Schiewe, and Anita Schöbel. Robustness as a Third Dimension for Evaluating Public Transport Plans. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/OASIcs.ATMOS.2018.4

Abstract

Providing attractive and efficient public transport services is of crucial importance due to higher demands for mobility and the need to reduce air pollution and to save energy. The classical planning process in public transport tries to achieve a reasonable compromise between service quality for passengers and operating costs. Service quality mostly considers quantities like average travel time and number of transfers. Since daily public transport inevitably suffers from delays caused by random disturbances and disruptions, robustness also plays a crucial role. While there are recent attempts to achieve delay-resistant timetables, comparably little work has been done to systematically assess and to compare the robustness of transport plans from a passenger point of view. We here provide a general and flexible framework for evaluating public transport plans (lines, timetables, and vehicle schedules) in various ways. It enables planners to explore several trade-offs between operating costs, service quality (average perceived travel time of passengers), and robustness against delays. For such an assessment we develop several passenger-oriented robustness tests which can be instantiated with parameterized delay scenarios. Important features of our framework include detailed passenger flow models, delay propagation schemes and disposition strategies, rerouting strategies as well as vehicle capacities. To demonstrate possible use cases, our framework has been applied to a variety of public transport plans which have been created for the same given demand for an artificial urban grid network and to instances for long-distance train networks. As one application we study the impact of different strategies to improve the robustness of timetables by insertion of supplement times. We also show that the framework can be used to optimize waiting strategies in delay management.

Subject Classification

ACM Subject Classification
  • Applied computing → Transportation
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Network optimization
Keywords
  • robustness
  • timetabling
  • vehicle schedules
  • delays

Metrics

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

References

  1. Rodrigo Acuna-Agost, Philippe Michelon, Dominique Feillet, and Serigne Gueye. A MIP-based local search method for the railway rescheduling problem. Networks, 57(1):69-86, 2011. Google Scholar
  2. Bastian Amberg, Boris Amberg, and Natalia Kliewer. Increasing delay-tolerance of vehicle and crew schedules in public transport by sequential, partial-integrated and integrated approaches. Procedia - Social and Behavioral Sciences, 20:292-301, 2011. Google Scholar
  3. Bastian Amberg, Boris Amberg, and Natalia Kliewer. Robust efficiency in urban public transportation: Minimizing delay propagation in cost-efficient bus and driver schedules. Transportation Science, 2018. URL: http://dx.doi.org/10.1287/trsc.2017.0757.
  4. Hannah Bast, Daniel Delling, Andrew V. Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. Route planning in transportation networks. In Lasse Kliemann and Peter Sanders, editors, Algorithm Engineering - Selected Results and Surveys, volume 9220 of Lecture Notes in Computer Science, pages 19-80. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-319-49487-6_2.
  5. Nikola Bešinović, Rob M.P. Goverde, Egidio Quaglietta, and Roberto Roberti. An integrated micro-macro approach to robust railway timetabling. Transportation Research Part B: Methodological, 87:14-32, 2016. Google Scholar
  6. Stefan Bunte and Natalia Kliewer. An overview on vehicle scheduling models. Public Transport, 1(4):299-317, 2009. Google Scholar
  7. Serafino Cicerone, Gianlorenzo D'Angelo, Gabriele Di Stefano, Daniele Frigioni, and Alfredo Navarra. Recoverable robust timetabling for single delay: Complexity and polynomial algorithms for special cases. Journal of Combinatorial Optimization, 18(3):229, Aug 2009. Google Scholar
  8. Twan Dollevoet and Dennis Huisman. Fast heuristics for delay management with passenger rerouting. Public Transport, 6(1-2):67-84, 2014. Google Scholar
  9. Twan Dollevoet, Dennis Huisman, Marie Schmidt, and Anita Schöbel. Delay management with rerouting of passengers. Transportation Science, 46(1):74-89, 2012. Google Scholar
  10. Twan Dollevoet, Dennis Huisman, Marie Schmidt, and Anita Schöbel. Delay propagation and delay management in transportation networks. In Ralf Borndörfer, Torsten Klug, Leonardo Lamorgese, Carlo Mannino, Markus Reuther, and Thomas Schlechte, editors, Handbook of Optimization in the Railway Industry, pages 285-317. Springer International Publishing, 2018. Google Scholar
  11. Markus Friedrich, Maximilian Hartl, Alexander Schiewe, and Anita Schöbel. Angebotsplanung im öffentlichen Verkehr - planerische und algorithmische Lösungen. In Heureka'17, 2017. Google Scholar
  12. Markus Friedrich, Matthias Müller-Hannemann, Ralf Rückert, Alexander Schiewe, and Anita Schöbel. Robustness Tests for Public Transport Planning. 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 6:1-6:16, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  13. Marc Goerigk, Michael Schachtebeck, and Anita Schöbel. Evaluating line concepts using travel times and robustness: Simulations with the LinTim toolbox. Public Transport, 5:267-284, 2013. Google Scholar
  14. 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: http://dx.doi.org/10.4230/OASIcs.ATMOS.2010.100.
  15. Géraldine Heilporn, Luigi De Giovanni, and Martine Labbé. Optimization models for the single delay management problem in public transportation. European Journal of Operational Research, 189(3):762-774, 2008. Google Scholar
  16. Sai Prashanth Josyula and Johanna Törnquist Krasemann. Passenger-oriented railway traffic re-scheduling: A review of alternative strategies utilizing passenger flow data. In 7th International Conference on Railway Operations Modelling and Analysis, Lille, 2017. Google Scholar
  17. Leo Kroon, Gábor Maróti, Mathijn Retel Helmrich, Michiel Vromans, and Rommert Dekker. Stochastic improvement of cyclic railway timetables. Transportation Research Part B: Methodological, 42(6):553-570, 2008. Google Scholar
  18. Richard M. Lusby, Jesper Larsen, and Simon Bull. A survey on robustness in railway planning. European Journal of Operational Research, 266(1):1-15, 2018. Google Scholar
  19. Matthias Müller-Hannemann and Mathias Schnee. Efficient timetable information in the presence of delays. In R. Ahuja, R.-H. Möhring, and C. Zaroliagis, editors, Robust and Online Large-Scale Optimization, volume 5868 of Lecture Notes in Computer Science, pages 249-272. Springer, 2009. Google Scholar
  20. Jens Parbo, Otto Anker Nielsen, and Carlo Giacomo Prato. Passenger perspectives in railway timetabling: A literature review. Transport Reviews, 36:500-526, 2016. Google Scholar
  21. 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. Google Scholar
  22. Ralf Rückert, Martin Lemnian, Christoph Blendinger, Steffen Rechner, and Matthias Müller-Hannemann. PANDA: a software tool for improved train dispatching with focus on passenger flows. Public Transport, 9(1):307-324, 2017. Google Scholar
  23. Alexander Schiewe, Sebastian Albert, Julius Pätzold, Philine Schiewe, Anita Schöbel, and Jochen Schulz. Lintim: An integrated environment for mathematical public transport optimization. documentation. Technical Report 2018-08, Preprint-Reihe, Institut für Numerische und Angewandte Mathematik, Georg-August Universität Göttingen, 2018. homepage: http://lintim.math.uni-goettingen.de/. Google Scholar
  24. Anita Schöbel. A model for the delay management problem based on mixed-integer programming. Electronic Notes in Theoretical Computer Science, 50(1), 2001. Google Scholar
  25. Anita Schöbel. Line planning in public transportation: models and methods. OR Spectrum, 34(3):491-510, Jul 2012. Google Scholar
  26. 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, 2017. Google Scholar
  27. Anita Schöbel and Silvia Schwarze. Finding delay-resistant line concepts using a game-theoretic approach. Netnomics, 14:95-117, 2013. Google Scholar
  28. Peter Sels, Thijs Dewilde, Dirk Cattrysse, and Pieter Vansteenwegen. Reducing the passenger travel time in practice by the automated construction of a robust railway timetable. Transportation Research Part B: Methodological, 84:124-156, 2016. 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