Document Open Access Logo

Towards Improved Robustness of Public Transport by a Machine-Learned Oracle

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

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2021.3.pdf
  • Filesize: 3.62 MB
  • 20 pages

Document Identifiers

Author Details

Matthias Müller-Hannemann
  • Martin-Luther-Universität Halle-Wittenberg, Germany
Ralf Rückert
  • Martin-Luther-Universität Halle-Wittenberg, Germany
Alexander Schiewe
  • TU Kaiserslautern, Germany
Anita Schöbel
  • Fraunhofer-Institut für Techno- und Wirtschaftsmathematik ITWM, Kaiserslautern, Germany
  • TU Kaiserslautern, Germany

Funding

This work has been partially supported by DFG under grants SCHO 1140/8-2 and MU 1482/7-2.

Cite AsGet BibTex

Matthias Müller-Hannemann, Ralf Rückert, Alexander Schiewe, and Anita Schöbel. Towards Improved Robustness of Public Transport by a Machine-Learned Oracle. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 3:1-3:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/OASIcs.ATMOS.2021.3

Abstract

The design and optimization of public transport systems is a highly complex and challenging process. Here, we focus on the trade-off between two criteria which shall make the transport system attractive for passengers: their travel time and the robustness of the system. The latter is time-consuming to evaluate. A passenger-based evaluation of robustness requires a performance simulation with respect to a large number of possible delay scenarios, making this step computationally very expensive. For optimizing the robustness, we hence apply a machine-learned oracle from previous work which approximates the robustness of a public transport system. We apply this oracle to bi-criteria optimization of integrated public transport planning (timetabling and vehicle scheduling) in two ways: First, we explore a local search based framework studying several variants of neighborhoods. Second, we evaluate a genetic algorithm. Computational experiments with artificial and close to real-word benchmark datasets yield promising results. In all cases, an existing pool of solutions (i.e., public transport plans) can be significantly improved by finding a number of new non-dominated solutions, providing better and different trade-offs between robustness and travel time.

Subject Classification

ACM Subject Classification
  • Applied computing → Transportation
Keywords
  • Public Transportation
  • Timetabling
  • Machine Learning
  • Robustness

Metrics

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

References

  1. D. Arenas, R. Chevrier, S. Hanafi, and J. Rodriguez. Solving the train timetabling problem, a mathematical model and a genetic algorithm solution approach. In 6th international conference on railway operations modelling and analysis (RailTokyo2015), 2015. Google Scholar
  2. R. Bauer and A. Schöbel. Rules of thumb - practical online strategies for delay management. Public Transport, 6(1):85-105, 2014. Google Scholar
  3. S. Bunte and N. Kliewer. An overview on vehicle scheduling models. Public Transport, 1(4):299-317, 2009. Google Scholar
  4. O. Cats. The robustness value of public transport development plans. Journal of Transport Geography, 51:236-246, 2016. Google Scholar
  5. A. De-Los-Santos, G. Laporte, J. A. Mesa, and F. Perea. Evaluating passenger robustness in a rail transit network. Transportation Research Part C: Emerging Technologies, 20(1):34-46, 2012. Special issue on Optimization in Public Transport+ISTT2011. URL: https://doi.org/10.1016/j.trc.2010.09.002.
  6. T. Dollevoet, D. Huisman, M. Schmidt, and A. Schöbel. Delay propagation and delay management in transportation networks. In Handbook of Optimization in the Railway Industry, pages 285-317. Springer, 2018. Google Scholar
  7. Collection of open source public transport networks by DFG Research Unit "FOR 2083: Integrated Planning For Public Transportation", 2018. URL: https://github.com/FOR2083/PublicTransportNetworks.
  8. M. Friedrich, M. Müller-Hannemann, R. Rückert, A. Schiewe, and A. Schöbel. Robustness Tests for Public Transport Planning. In G. D'Angelo and T. 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. URL: https://doi.org/10.4230/OASIcs.ATMOS.2017.6.
  9. M. Friedrich, M. Müller-Hannemann, R. Rückert, A. Schiewe, and A. Schöbel. Robustness as a Third Dimension for Evaluating Public Transport Plans. In R. Borndörfer and S. Storandt, editors, 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018), volume 65 of OpenAccess Series in Informatics (OASIcs), pages 4:1-4:17. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/OASIcs.ATMOS.2018.4.
  10. M. Goerigk. Exact and heuristic approaches to the robust periodic event scheduling problem. Public Transport, 7(1):101-119, 2015. Google Scholar
  11. M. Goerigk and A. Schöbel. Improving the modulo simplex algorithm for large-scale periodic timetabling. Computers & Operations Research, 40(5):1363-1370, 2013. Google Scholar
  12. M. Goerigk and A. Schöbel. Algorithm engineering in robust optimization. In L. Kliemann and P. Sanders, editors, Algorithm Engineering: Selected Results and Surveys, volume 9220 of LNCS State of the Art, pages 245-279. Springer, 2016. Google Scholar
  13. O. Ibarra-Rojas, F. López-Irarragorri, and Y. Rios-Solis. Multiperiod bus timetabling. Transportation Science, 50(3):805-822, 2016. Google Scholar
  14. E. König. A review on railway delay management. Public Transport, 12(2):335-361, 2020. Google Scholar
  15. Q.-C. Lu. Modeling network resilience of rail transit under operational incidents. Transportation Research Part A: Policy and Practice, 117:227-237, 2018. URL: https://doi.org/10.1016/j.tra.2018.08.015.
  16. R. Lusby, J. Larsen, and S. Bull. A survey on robustness in railway planning. European Journal of Operational Research, 266(1):1-15, 2018. Google Scholar
  17. R. Lusby, J. Larsen, M. Ehrgott, and D. Ryan. Railway track allocation: models and methods. OR spectrum, 33(4):843-883, 2011. Google Scholar
  18. G. Matos, L. Albino, R. Saldanha, and E. Morgado. Solving periodic timetabling problems with SAT and machine learning. Public Transport, 2020. URL: https://doi.org/10.1007/s12469-020-00244-y.
  19. M. Müller-Hannemann, R. Rückert, A. Schiewe, and A. Schöbel. Estimating the robustness of public transport systems using machine learning, 2021. URL: http://arxiv.org/abs/2106.08967.
  20. K. Nachtigall and S. Voget. A genetic algorithm approach to periodic railway synchronization. Computers & Operations Research, 23(5):453-463, 1996. Google Scholar
  21. J. Parbo, O. Nielsen, and C. Prato. Passenger perspectives in railway timetabling: a literature review. Transport Reviews, 36(4):500-526, 2016. Google Scholar
  22. J. Pätzold. Finding robust periodic timetables by integrating delay management. Public Transport, 2021. URL: https://doi.org/10.1007/s12469-020-00260-y.
  23. G. Polinder, V. Cacchiani, M. Schmidt, and D. Huisman. An iterative heuristic for passenger-centric train timetabling with integrated adaption times. ERIM Report Series Research in Management ERS-2020-006-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam, 2020. URL: https://ideas.repec.org/p/ems/eureri/127816.html.
  24. A. Schiewe, S. Albert, P. Schiewe, A. Schöbel, and F. Spühler. LinTim - Integrated Optimization in Public Transportation. Homepage. https://lintim.net, 2020.
  25. A. Schiewe, S. Albert, P. Schiewe, A. Schöbel, and F. 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.
  26. A. Schöbel. Line planning in public transportation: models and methods. OR spectrum, 34(3):491-510, 2012. Google Scholar
  27. P. Tormos, A. Lova, F. Barber, L. Ingolotti, M. Abril, and M. Salido. A genetic algorithm for railway scheduling problems. In Metaheuristics for scheduling in industrial and manufacturing applications, pages 255-276. Springer, 2008. Google Scholar
  28. A. van den Heuvel, J. van den Akker, and M. van Kooten. Integrating timetabling and vehicle scheduling in public bus transportation. Technical report, Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands, 2008. 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