Document Open Access Logo

Efficient Algorithms for Fully Multimodal Journey Planning

Authors Moritz Potthoff, Jonas Sauer

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2022.14.pdf
  • Filesize: 0.57 MB
  • 15 pages

Document Identifiers

Author Details

Moritz Potthoff
  • Karlsruhe Institute of Technology (KIT), Germany
Jonas Sauer
  • Karlsruhe Institute of Technology (KIT), Germany

Funding

This research was funded by Deutsche Forschungsgemeinschaft under grant number WA 654/23-2.

Cite AsGet BibTex

Moritz Potthoff and Jonas Sauer. Efficient Algorithms for Fully Multimodal Journey Planning. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/OASIcs.ATMOS.2022.14

Abstract

We study the journey planning problem for fully multimodal networks consisting of public transit and an arbitrary number of non-schedule-based transfer modes (e.g., walking, e-scooter, bicycle). Obtaining reasonable results in this setting requires multicriteria optimization, making the problem highly complex. Previous approaches were either limited to a single transfer mode or suffered from prohibitively slow running times. We establish a fully multimodal journey planning model that excludes undesirable solutions and can be solved efficiently. We extend existing efficient bimodal algorithms to our model and propose a new algorithm, HydRA, which enables even faster queries. On metropolitan and mid-sized country networks with walking and e-scooter as transfer modes, HydRA achieves query times of around 30 ms, which is fast enough for interactive applications.

Subject Classification

ACM Subject Classification
  • Theory of computation → Shortest paths
  • Mathematics of computing → Graph algorithms
  • Applied computing → Transportation
Keywords
  • Algorithms
  • Journey Planning
  • Multimodal
  • Multicriteria
  • Public Transit

Metrics

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

Supplementary Materials

References

  1. Hannah Bast, Mirko Brodesser, and Sabine Storandt. Result Diversity for Multi-Modal Route Planning. In Proceedings of the 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'13), volume 33 of OpenAccess Series in Informatics (OASIcs), pages 123-136. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013. URL: https://doi.org/10.4230/OASIcs.ATMOS.2013.123.
  2. Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. Route Planning in Transportation Networks. In Algorithm Engineering: Selected Results and Surveys, volume 9220 of Lecture Notes in Computer Science (LNCS), pages 19-80. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-49487-6_2.
  3. Moritz Baum, Valentin Buchhold, Jonas Sauer, Dorothea Wagner, and Tobias Zündorf. UnLimited TRAnsfers for Multi-Modal Route Planning: An Efficient Solution. In Proceedings of the 27th Annual European Symposium on Algorithms (ESA'19), volume 144 of Leibniz International Proceedings in Informatics (LIPIcs), pages 14:1-14:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.14.
  4. Daniel Delling, Julian Dibbelt, and Thomas Pajor. Fast and Exact Public Transit Routing with Restricted Pareto Sets. In Proceedings of the 21st Workshop on Algorithm Engineering and Experiments (ALENEX'19), pages 54-65. Society for Industrial and Applied Mathematics (SIAM), 2019. URL: https://doi.org/10.1137/1.9781611975499.5.
  5. Daniel Delling, Julian Dibbelt, Thomas Pajor, Dorothea Wagner, and Renato F. Werneck. Computing Multimodal Journeys in Practice. In Proceedings of the 12th International Symposium on Experimental Algorithms (SEA'13), volume 7933 of Lecture Notes in Computer Science (LNCS), pages 260-271. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-38527-8_24.
  6. Daniel Delling, Thomas Pajor, and Renato F. Werneck. Round-Based Public Transit Routing. Transportation Science, 49:591-604, 2015. URL: https://doi.org/10.1287/trsc.2014.0534.
  7. Julian Dibbelt, Thomas Pajor, Ben Strasser, and Dorothea Wagner. Connection Scan Algorithm. Journal of Experimental Algorithmics (JEA), 23:1.7:1-1.7:56, 2018. URL: https://doi.org/10.1145/3274661.
  8. Edsger W. Dijkstra. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1:269-271, 1959. URL: https://doi.org/10.1007/BF01386390.
  9. Robert Geisberger, Peter Sanders, Dominik Schultes, and Christian Vetter. Exact Routing in Large Road Networks Using Contraction Hierarchies. Transportation Science, 46:388-404, 2012. URL: https://doi.org/10.1287/trsc.1110.0401.
  10. Sebastian Knopp, Peter Sanders, Dominik Schultes, Frank Schulz, and Dorothea Wagner. Computing Many-to-Many Shortest Paths Using Highway Hierarchies. In Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX'07), pages 36-45. Society for Industrial and Applied Mathematics (SIAM), 2007. URL: https://doi.org/10.5555/2791188.2791192.
  11. Moritz Potthoff and Jonas Sauer. Fast Multimodal Journey Planning for Three Criteria. In Proceedings of the 24th Workshop on Algorithm Engineering and Experiments (ALENEX'22), pages 145-157. Society for Industrial and Applied Mathematics (SIAM), 2022. URL: https://doi.org/10.1137/1.9781611977042.12.
  12. Jonas Sauer, Dorothea Wagner, and Tobias Zündorf. Faster Multi-Modal Route Planning with Bike Sharing using ULTRA. In Proceedings of the 18th International Symposium on Experimental Algorithms (SEA'20), volume 160 of Leibniz International Proceedings in Informatics (LIPIcs), pages 16:1-16:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.SEA.2020.16.
  13. Jonas Sauer, Dorothea Wagner, and Tobias Zündorf. Integrating ULTRA and Trip-Based Routing. In Proceedings of the 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'20), volume 85 of OpenAccess Series in Informatics (OASIcs), pages 4:1-4:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/OASIcs.ATMOS.2020.4.
  14. Johannes Schlaich, Udo Heidl, and Regine Pohlner. Verkehrsmodellierung für die Region Stuttgart - Schlussbericht. Unpublished manuscript, 2011. Google Scholar
  15. Dorothea Wagner and Tobias Zündorf. Public Transit Routing with Unrestricted Walking. In Proceedings of the 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'17), volume 59 of OpenAccess Series in Informatics (OASIcs), pages 7:1-7:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/OASIcs.ATMOS.2017.7.
  16. Sascha Witt. Trip-Based Public Transit Routing. In Proceedings of the 23rd Annual European Symposium on Algorithms (ESA'15), volume 9294 of Lecture Notes in Computer Science (LNCS), pages 1025-1036. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48350-3_85.
  17. Tobias Zündorf. Multimodal Journey Planning and Assignment in Public Transportation Networks. PhD thesis, Karlsruhe Institute of Technology, 2020. URL: https://doi.org/10.5445/IR/1000145076.
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