Document Open Access Logo

Integrating ULTRA and Trip-Based Routing

Authors Jonas Sauer, Dorothea Wagner, Tobias Zündorf

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2020.4.pdf
  • Filesize: 476 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.

Acknowledgements

We thank Sascha Witt for many fruitful discussions about Trip-Based Routing.

Cite AsGet BibTex

Jonas Sauer, Dorothea Wagner, and Tobias Zündorf. Integrating ULTRA and Trip-Based Routing. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/OASIcs.ATMOS.2020.4

Abstract

We study a bi-modal journey planning scenario consisting of a public transit network and a transfer graph representing a secondary transportation mode (e.g., walking or cycling). Given a pair of source and target locations, the objective is to find a Pareto set of journeys optimizing arrival time and the number of required transfers. For public transit networks with a restricted, transitively closed transfer graph, one of the fastest known algorithms solving this bi-criteria problem is Trip-Based Routing [Witt, 2015]. However, this algorithm cannot be trivially extended to unrestricted transfer graphs. In this work, we combine Trip-Based Routing with ULTRA [Baum et al., 2019], a preprocessing technique that allows any public transit algorithm that requires transitive transfers to handle an unrestricted transfer graph. Since both ULTRA and Trip-Based Routing precompute transfer shortcuts in a preprocessing phase, a naive combination of the two leads to a three-phase algorithm that performs redundant work and produces superfluous shortcuts. We therefore propose a new, integrated preprocessing phase that combines the advantages of both and reduces the number of computed shortcuts by up to a factor of 9 compared to a naive combination. The resulting query algorithm, ULTRA-Trip-Based is the fastest known algorithm for the considered problem setting, achieving a speedup of up to 4 compared to the fastest previously known approach, ULTRA-RAPTOR.

Subject Classification

ACM Subject Classification
  • Theory of computation → Shortest paths
  • Mathematics of computing → Graph algorithms
  • Applied computing → Transportation
Keywords
  • Algorithms
  • Journey Planning
  • Multi-Modal
  • Public Transportation

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, Jonas Sternisko, and Sabine Storandt. Delay-robustness of Transfer Patterns in Public Transportation Route Planning. In ATMOS-13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems-2013, volume 33, pages 42-54. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2013. Google Scholar
  5. 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), volume 144 of Leibniz International Proceedings in Informatics (LIPIcs), pages 14:1-14:16, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  6. Lars Briem, Sebastian Buck, Holger Ebhart, Nicolai Mallig, Ben Strasser, Peter Vortisch, Dorothea Wagner, and Tobias Zündorf. Efficient Traffic Assignment for Public Transit Networks. In LIPIcs-Leibniz International Proceedings in Informatics, volume 75. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  7. 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, pages 260-271. Springer, 2013. Google Scholar
  8. Daniel Delling, Julian Dibbelt, Thomas Pajor, and Tobias Zündorf. 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
  9. Daniel Delling, Thomas Pajor, and Renato F. Werneck. Round-Based Public Transit Routing. In Proceedings of the 14th Workshop on Algorithm Engineering and Experiments (ALENEX'12), pages 130-140. SIAM, 2012. Google Scholar
  10. Daniel Delling, Thomas Pajor, and Renato F Werneck. Round-based Public Transit Routing. Transportation Science, 49(3):591-604, 2014. Google Scholar
  11. 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
  12. 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
  13. Edsger W Dijkstra. A Note on Two Problems in Connexion with Graphs. Numerische mathematik, 1(1):269-271, 1959. Google Scholar
  14. 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
  15. 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
  16. 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
  17. Kalliopi Giannakopoulou, Andreas Paraskevopoulos, and Christos Zaroliagis. Multimodal Dynamic Journey-Planning. Algorithms, 12(10):213, 2019. Google Scholar
  18. 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
  19. Dominik Kirchler. Efficient Routing on Multi-Modal Transportation Networks. PhD thesis, Ecole Polytechnique X, 2013. Google Scholar
  20. 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
  21. 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
  22. 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
  23. Jonas Sauer. Faster Public Transit Routing with Unrestricted Walking. Master’s thesis, Karlsruhe Institute of Technology, April 2018. Google Scholar
  24. 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
  25. 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
  26. Sascha Witt. Trip-Based Public Transit Routing. In 23th Annual European Symposium on Algorithms (ESA 2015), pages 1025-1036. Springer, 2015. Google Scholar
  27. Sascha Witt. Trip-Based Public Transit Routing Using Condensed Search Trees. In 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016), volume 54 of OpenAccess Series in Informatics (OASIcs), pages 10:1-10:12, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. 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