Document Open Access Logo

An Efficient Solution for One-To-Many Multi-Modal Journey Planning

Authors Jonas Sauer, Dorothea Wagner, Tobias Zündorf

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2020.1.pdf
  • Filesize: 439 kB
  • 15 pages

Document Identifiers

Author Details

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

Funding

This research was funded by the DFG under grant number WA 654123-2.

Cite AsGet BibTex

Jonas Sauer, Dorothea Wagner, and Tobias Zündorf. An Efficient Solution for One-To-Many Multi-Modal Journey Planning. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/OASIcs.ATMOS.2020.1

Abstract

We study the one-to-many journey planning problem in multi-modal transportation networks consisting of a public transit network and an additional, non-schedule-based mode of transport. Given a departure time and a single source vertex, we aim to compute optimal journeys to all vertices in a set of targets, optimizing both travel time and the number of transfers used. Solving this problem yields a crucial component in many other problems, such as efficient point-of-interest queries, computation of isochrones, or multi-modal traffic assignments. While many algorithms for multi-modal journey planning exist, none of them are applicable to one-to-many scenarios. Our solution is based on the combination of two state-of-the-art approaches: ULTRA, which enables efficient journey planning in multi-modal networks, but only for one-to-one queries, and (R)PHAST, which enables efficient one-to-many queries, but only in time-independent networks. Similarly to ULTRA, our new approach can be combined with any existing public transit algorithm that allows a search to all stops, which we demonstrate for CSA and RAPTOR. For small to moderately sized target sets, the resulting algorithms are nearly as fast as the pure public transit algorithms they are based on. For large target sets, we achieve a speedup of up to 7 compared to a naive one-to-many extension of a state-of-the-art multi-modal approach.

Subject Classification

ACM Subject Classification
  • Theory of computation → Shortest paths
  • Mathematics of computing → Graph algorithms
  • Applied computing → Transportation
Keywords
  • Algorithm Engineering
  • Route Planning
  • Public Transit
  • One-to-Many

Metrics

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

Supplementary Materials

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. Moritz Baum, Thomas Bläsius, Andreas Gemsa, Ignaz Rutter, and Franziska Wegner. Scalable Exact Visualization of Isocontours in Road Networks via Minimum-Link Paths. In Proceedings of the 24th Annual European Symposium on Algorithms (ESA'16), pages 7:1-7:18, 2016. Google Scholar
  6. 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
  7. Moritz Baum, Valentin Buchhold, Julian Dibbelt, and Dorothea Wagner. Fast Exact Computation of Isocontours in Road Networks. ACM Journal of Experimental Algorithmics, 24(1), 2019. Google Scholar
  8. 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), pages 14:1-14:16, 2019. Google Scholar
  9. Annabell Berger, Daniel Delling, Andreas Gebhardt, and Matthias Müller-Hannemann. Accelerating Time-Dependent Multi-Criteria Timetable Information is Harder Than Expected. In 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09), 2009. Google Scholar
  10. Lars Briem, H. Sebastian Buck, Holger Ebhart, Nicolai Mallig, Ben Strasser, Peter Vortisch, Dorothea Wagner, and Tobias Zündorf. Efficient Traffic Assignment for Public Transit Networks. In 16th Symposium on Experimental Algorithms (SEA 2017), 2017. Google Scholar
  11. 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
  12. Daniel Delling, Andrew Goldberg, Thomas Pajor, and Renato Werneck. Customizable Route Planning. In Proceedings of the 10th International Symposium on Experimental Algorithms (SEA'11). Springer, 2011. Google Scholar
  13. Daniel Delling, Andrew V Goldberg, Andreas Nowatzyk, and Renato F Werneck. PHAST: Hardware-Accelerated Shortest Path Trees. Journal of Parallel and Distributed Computing, 73(7):940-952, 2013. Google Scholar
  14. Daniel Delling, Andrew V Goldberg, and Renato F Werneck. Faster Batched Shortest Paths in Road Networks. In 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2011), pages 52-63, 2011. Google Scholar
  15. Daniel Delling, Thomas Pajor, and Dorothea Wagner. Accelerating Multi-modal Route Planning by Access-Nodes. In Algorithms - ESA 2009, pages 587-598, 2009. Google Scholar
  16. Daniel Delling, Thomas Pajor, and Renato F Werneck. Round-based Public Transit Routing. Transportation Science, 49(3):591-604, 2014. Google Scholar
  17. Daniel Delling and Renato Werneck. Customizable Point-of-Interest Queries in Road Networks. In IEEE Transactions on Knowledge and Data Engineering, pages 500-503, 2013. Google Scholar
  18. 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
  19. Julian Dibbelt, Thomas Pajor, Ben Strasser, and Dorothea Wagner. Connection Scan Algorithm. ACM Journal of Experimental Algorithmics, pages 1.7:1-1.7:56, 2018. Google Scholar
  20. Julian Dibbelt, Thomas Pajor, and Dorothea Wagner. User-Constrained Multimodal Route Planning. ACM Journal of Experimental Algorithmics, pages 3.2:1-3.2:19, 2015. Google Scholar
  21. Edsger W Dijkstra. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1(1):269-271, 1959. Google Scholar
  22. 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), pages 347-361. Springer, 2008. Google Scholar
  23. Alexandros Efentakis and Dieter Pfoser. GRASP. Extending Graph Separators for the Single-Source Shortest-Path Problem. In Algorithms - ESA 2014, pages 358-370. Springer, 2014. Google Scholar
  24. Johann Gamper, Michael Böhlen, Willi Cometti, and Markus Innerebner. Defining Isochrones in Multimodal Spatial Networks. In Proceedings of the 20th ACM International Conference on Information and Knowledge Management, pages 2381-2384, 2011. Google Scholar
  25. Johann Gamper, Michael Böhlen, and Markus Innerebner. Scalable Computation of Isochrones with Network Expiration. In Scientific and Statistical Database Management, pages 526-543. Springer, 2012. Google Scholar
  26. 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), pages 319-333. Springer, 2008. Google Scholar
  27. Robert Geisberger, Peter Sanders, Dominik Schultes, and Christian Vetter. Exact Routing in Large Road Networks Using Contraction Hierarchies. Transportation Science, 46(3):388-404, 2012. Google Scholar
  28. Kalliopi Giannakopoulou, Andreas Paraskevopoulos, and Christos Zaroliagis. Multimodal Dynamic Journey-Planning. Algorithms, 12(10):213, 2019. Google Scholar
  29. Moritz Hilger, Ekkehard Köhler, Rolf Möhring, and Heiko Schilling. Fast Point-to-Point Shortest Path Computations with Arc-Flags, pages 41-72. American Mathematical Society, 2009. Google Scholar
  30. Jan Hrnčíř and Michal Jakob. Generalised Time-Dependent Graphs for Fully Multimodal Journey Planning. In 16th International IEEE Conference on Intelligent Transportation Systems (ITSC 2013), pages 2138-2145. IEEE, 2013. Google Scholar
  31. Dominik Kirchler. Efficient Routing on Multi-Modal Transportation Networks. PhD thesis, Ecole Polytechnique X, 2013. Google Scholar
  32. 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
  33. Nikolaus Krismer, Doris Silbernagl, Günther Specht, and Johann Gamper. Computing Isochrones in Multimodal Spatial Networks Using Tile Regions. In Proceedings of the 29th International Conference on Scientific and Statistical Database Management, 2017. Google Scholar
  34. 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²). Springer, 2019. Google Scholar
  35. 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
  36. Peter Sanders, Dominik Schultes, and Christian Vetter. Mobile Route Planning. In Algorithms - ESA 2008, pages 732-743. Springer, 2008. Google Scholar
  37. Jonas Sauer. Faster Public Transit Routing with Unrestricted Walking. Master’s thesis, Karlsruhe Institute of Technology, 2018. Google Scholar
  38. Jonas Sauer, Dorothea Wagner, and Tobias Zündorf. Efficient Computation of Multi-Modal Public Transit Traffic Assignments Using ULTRA. In Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, page 524–527, 2019. Google Scholar
  39. 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), 2017. Google Scholar
  40. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact