UnLimited TRAnsfers for Multi-Modal Route Planning: An Efficient Solution

Authors Moritz Baum, Valentin Buchhold, Jonas Sauer, Dorothea Wagner, Tobias Zündorf



PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.14.pdf
  • Filesize: 480 kB
  • 16 pages

Document Identifiers

Author Details

Moritz Baum
  • Karlsruhe Institute of Technology (KIT), Karlsruhe, Germany
Valentin Buchhold
  • Karlsruhe Institute of Technology (KIT), Karlsruhe, Germany
Jonas Sauer
  • Karlsruhe Institute of Technology (KIT), Karlsruhe, Germany
Dorothea Wagner
  • Karlsruhe Institute of Technology (KIT), Karlsruhe, Germany
Tobias Zündorf
  • Karlsruhe Institute of Technology (KIT), Karlsruhe, Germany

Cite AsGet BibTex

Moritz Baum, Valentin Buchhold, Jonas Sauer, Dorothea Wagner, and Tobias Zündorf. UnLimited TRAnsfers for Multi-Modal Route Planning: An Efficient Solution. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ESA.2019.14

Abstract

We study a multi-modal route planning scenario consisting of a public transit network and a transfer graph representing a secondary transportation mode (e.g., walking or taxis). The objective is to compute all journeys that are Pareto-optimal with respect to arrival time and the number of required transfers. While various existing algorithms can efficiently compute optimal journeys in either a pure public transit network or a pure transfer graph, combining the two increases running times significantly. As a result, even walking between stops is typically limited by a maximal duration or distance, or by requiring the transfer graph to be transitively closed. To overcome these shortcomings, we propose a novel preprocessing technique called ULTRA (UnLimited TRAnsfers): Given a complete transfer graph (without any limitations, representing an arbitrary non-schedule-based mode of transportation), we compute a small number of transfer shortcuts that are provably sufficient for computing all Pareto-optimal journeys. We demonstrate the practicality of our approach by showing that these transfer shortcuts can be integrated into a variety of state-of-the-art public transit algorithms, establishing the ULTRA-Query algorithm family. Our extensive experimental evaluation shows that ULTRA is able to improve these algorithms from limited to unlimited transfers without sacrificing query speed, yielding the fastest known algorithms for multi-modal routing. This is true not just for walking, but also for other transfer modes such as cycling or driving.

Subject Classification

ACM Subject Classification
  • Theory of computation → Shortest paths
  • Mathematics of computing → Graph algorithms
  • Applied computing → Transportation
Keywords
  • Algorithms
  • Optimization
  • Route Planning
  • Public Transportation

Metrics

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

References

  1. Ittai Abraham, Daniel Delling, Andrew V Goldberg, and Renato F Werneck. A Hub-Based Labeling Algorithm for Shortest Paths in Road Networks. In International Symposium on Experimental Algorithms, pages 230-241. Springer, 2011. Google Scholar
  2. Hannah Bast, Erik Carlsson, Arno Eigenwillig, Robert Geisberger, Chris Harrelson, Veselin Raychev, and Fabien Viger. Fast Routing in Very Large Public Transportation Networks using Transfer Patterns. In European Symposium on Algorithms, pages 290-301. Springer, 2010. Google Scholar
  3. 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, pages 19-80. Springer, 2016. Google Scholar
  4. Hannah Bast, Matthias Hertel, and Sabine Storandt. Scalable Transfer Patterns. In 2016 Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX), pages 15-29, 2016. Google Scholar
  5. Hannah Bast and Sabine Storandt. Frequency-Based Search for Public Transit. In Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 13-22. ACM Press, November 2014. Google Scholar
  6. Reinhard Bauer, Daniel Delling, Peter Sanders, Dennis Schieferdecker, Dominik Schultes, and Dorothea Wagner. Combining Hierarchical and Goal-directed Speed-up Techniques for Dijkstra’s Algorithm. ACM Journal of Experimental Algorithmics, 15:2.3:2.1-2.3:2.31, March 2010. Google Scholar
  7. Moritz Baum, Valentin Buchhold, Julian Dibbelt, and Dorothea Wagner. Fast Exact Computation of Isochrones in Road Networks. In International Symposium on Experimental Algorithms, pages 17-32. Springer, 2016. Google Scholar
  8. Moritz Baum, Julian Dibbelt, Andreas Gemsa, Dorothea Wagner, and Tobias Zündorf. Shortest Feasible Paths with Charging Stops for Battery Electric Vehicles. In Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL '15, pages 44:1-44:10, New York, NY, USA, 2015. ACM. Google Scholar
  9. Annabell Berger, Martin Grimmer, and Matthias Müller-Hannemann. Fully Dynamic Speed-Up Techniques for Multi-criteria Shortest Path Searches in Time-Dependent Networks. In Proceedings of the 9th International Symposium on Experimental Algorithms (SEA'10), volume 6049 of Lecture Notes in Computer Science, pages 35-46. Springer, May 2010. Google Scholar
  10. Daniel Delling, Julian Dibbelt, Thomas Pajor, Dorothea Wagner, and Renato Werneck. Computing Multimodal Journeys in Practice. In International Symposium on Experimental Algorithms, pages 260-271. Springer, 2013. Google Scholar
  11. Daniel Delling, Julian Dibbelt, Thomas Pajor, and Renato Werneck. Public Transit Labeling. In Proceedings of the 14th International Symposium on Experimental Algorithms (SEA'15), Lecture Notes in Computer Science, pages 273-285. Springer, 2015. Google Scholar
  12. Daniel Delling, Julian Dibbelt, Thomas Pajor, and Tobias Zuendorf. Faster Transit Routing by Hyper Partitioning. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017), volume 59 of OpenAccess Series in Informatics (OASIcs), pages 8:1-8:14, Dagstuhl, Germany, 2017. Google Scholar
  13. Daniel Delling, Thomas Pajor, and Renato F Werneck. Round-based Public Transit Routing. Transportation Science, 49(3):591-604, 2014. Google Scholar
  14. Julian Dibbelt, Thomas Pajor, Ben Strasser, and Dorothea Wagner. Intriguingly Simple and Fast Transit Routing. In International Symposium on Experimental Algorithms, pages 43-54. Springer, 2013. Google Scholar
  15. Julian Dibbelt, Thomas Pajor, Ben Strasser, and Dorothea Wagner. Connection Scan Algorithm. ACM Journal of Experimental Algorithmics, 23:1.7:1-1.7:56, October 2018. Google Scholar
  16. Julian Dibbelt, Thomas Pajor, and Dorothea Wagner. User-Constrained Multimodal Route Planning. ACM Journal of Experimental Algorithmics, 19:3.2:1-3.2:19, April 2015. Google Scholar
  17. Edsger W Dijkstra. A Note on Two Problems in Connexion with Graphs. Numerische mathematik, 1(1):269-271, 1959. Google Scholar
  18. Yann Disser, Matthias Müller-Hannemann, and Mathias Schnee. Multi-Criteria Shortest Paths in Time-Dependent Train Networks. In Proceedings of the 7th Workshop on Experimental Algorithms (WEA'08), volume 5038 of Lecture Notes in Computer Science, pages 347-361. Springer, June 2008. Google Scholar
  19. Robert Geisberger, Peter Sanders, Dominik Schultes, and Daniel Delling. Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks. In Proceedings of the 7th Workshop on Experimental Algorithms (WEA'08), volume 5038 of Lecture Notes in Computer Science, pages 319-333. Springer, June 2008. Google Scholar
  20. Robert Geisberger, Peter Sanders, Dominik Schultes, and Christian Vetter. Exact Routing in Large Road Networks Using Contraction Hierarchies. Transportation Science, 46(3):388-404, August 2012. Google Scholar
  21. 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. SIAM, 2007. Google Scholar
  22. Duc-Minh Phan and Laurent Viennot. Fast Public Transit Routing with Unrestricted Walking through Hub Labeling. In Proceedings of the Special Event on Analysis of Experimental Algorithms (SEA²), Lecture Notes in Computer Science. Springer, 2019. Google Scholar
  23. Evangelia Pyrga, Frank Schulz, Dorothea Wagner, and Christos Zaroliagis. Efficient Models for Timetable Information in Public Transportation Systems. ACM Journal of Experimental Algorithmics, 12(2.4):1-39, 2008. Google Scholar
  24. Jonas Sauer. Faster Public Transit Routing with Unrestricted Walking. Master’s thesis, Karlsruhe Institute of Technology, April 2018. Google Scholar
  25. Ben Strasser and Dorothea Wagner. Connection Scan Accelerated. In 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX), pages 125-137. SIAM, 2014. Google Scholar
  26. Dorothea Wagner and Tobias Zündorf. Public Transit Routing with Unrestricted Walking. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2017. Google Scholar
  27. Sascha Witt. Trip-Based Public Transit Routing. In Algorithms-ESA 2015, pages 1025-1036. Springer, 2015. 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