Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks

Authors Ben Strasser, Dorothea Wagner, Tim Zeitz



PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.81.pdf
  • Filesize: 434 kB
  • 14 pages

Document Identifiers

Author Details

Ben Strasser
  • Karlsruhe Institute of Technology, Germany
Dorothea Wagner
  • Karlsruhe Institute of Technology, Germany
Tim Zeitz
  • Karlsruhe Institute of Technology, Germany

Acknowledgements

We thank Lars Gottesbüren and Michael Hamann for fruitful discussions and feedback. We also thank Marcel Radermacher for his input on approximation algorithms.

Cite AsGet BibTex

Ben Strasser, Dorothea Wagner, and Tim Zeitz. Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 81:1-81:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ESA.2020.81

Abstract

We study the problem of computing shortest paths in massive road networks with traffic predictions. Incorporating traffic predictions into routing allows, for example, to avoid commuter traffic congestions. Existing techniques follow a two-phase approach: In a preprocessing step, an index is built. The index depends on the road network and the traffic patterns but not on the path start and end. The latter are the input of the query phase, in which shortest paths are computed. All existing techniques have either large index size, slow query running times, or may compute suboptimal paths. In this work, we introduce CATCHUp (Customizable Approximated Time-dependent Contraction Hierarchies through Unpacking), the first algorithm that simultaneously achieves all three objectives. The core idea of CATCHUp is to store paths instead of travel times at shortcuts. Shortcut travel times are derived lazily from the stored paths. We perform an experimental study on a set of real world instances and compare our approach with state-of-the-art techniques. Our approach achieves the fastest preprocessing, competitive query running times and up to 30 times smaller indexes than competing approaches.

Subject Classification

ACM Subject Classification
  • Theory of computation → Shortest paths
  • Mathematics of computing → Graph algorithms
  • Applied computing → Transportation
Keywords
  • realistic road networks
  • time-dependent route planning
  • shortest paths

Metrics

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

References

  1. Hannah Bast, Daniel Delling, Andrew V. Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. Route Planning in Transportation Networks. In Lasse Kliemann and Peter Sanders, editors, Algorithm Engineering - Selected Results and Surveys, volume 9220 of Lecture Notes in Computer Science, pages 19-80. Springer, 2016. URL: http://www.springer.com/gp/book/9783319494869.
  2. Gernot Veit Batz, Robert Geisberger, Peter Sanders, and Christian Vetter. Minimum Time-Dependent Travel Times with Contraction Hierarchies. ACM Journal of Experimental Algorithmics, 18(1.4):1-43, April 2013. Google Scholar
  3. Reinhard Bauer, Tobias Columbus, Ignaz Rutter, and Dorothea Wagner. Search-space size in contraction hierarchies. Theoretical Computer Science, 645:112-127, 2016. Google Scholar
  4. Reinhard Bauer and Daniel Delling. SHARC: Fast and Robust Unidirectional Routing. ACM Journal of Experimental Algorithmics, 14(2.4):1-29, August 2009. Special Section on Selected Papers from ALENEX 2008. URL: https://doi.org/10.1145/1498698.1537599.
  5. Moritz Baum, Julian Dibbelt, Thomas Pajor, and Dorothea Wagner. Dynamic Time-Dependent Route Planning in Road Networks with User Preferences. In Proceedings of the 15th International Symposium on Experimental Algorithms (SEA'16), volume 9685 of Lecture Notes in Computer Science, pages 33-49. Springer, 2016. URL: http://link.springer.com/chapter/10.1007/978-3-319-38851-9_3.
  6. Valentin Buchhold, Peter Sanders, and Dorothea Wagner. Real-time Traffic Assignment Using Engineered Customizable Contraction Hierarchies. ACM Journal of Experimental Algorithmics, 24(2):2.4:1-2.4:28, 2019. URL: https://dl.acm.org/citation.cfm?id=3362693.
  7. Daniel Delling. Time-Dependent SHARC-Routing. Algorithmica, 60(1):60-94, May 2011. URL: https://doi.org/10.1007/s00453-009-9341-0.
  8. Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck. Customizable Route Planning in Road Networks. Transportation Science, 51(2):566-591, 2017. URL: https://doi.org/10.1287/trsc.2014.0579.
  9. Daniel Delling and Giacomo Nannicini. Core Routing on Dynamic Time-Dependent Road Networks. Informs Journal on Computing, 24(2):187-201, 2012. Google Scholar
  10. Julian Dibbelt. Engineering Algorithms for Route Planning in Multimodal Transportation Networks. PhD thesis, Karlsruhe Institute of Technology, February 2016. URL: http://nbn-resolving.de/urn:nbn:de:swb:90-530503.
  11. Julian Dibbelt, Ben Strasser, and Dorothea Wagner. Customizable Contraction Hierarchies. ACM Journal of Experimental Algorithmics, 21(1):1.5:1-1.5:49, April 2016. URL: https://doi.org/10.1145/2886843.
  12. Edsger W. Dijkstra. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1(1):269-271, 1959. Google Scholar
  13. David H. Douglas and Thomas K. Peucker. Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or its Caricature. Cartographica: The International Journal for Geographic Information and Geovisualization, 10:112-122, 1973. Google Scholar
  14. Stuart E. Dreyfus. An Appraisal of Some Shortest-Path Algorithms. Operations Research, 17(3):395-412, 1969. Google Scholar
  15. 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
  16. Alan George. Nested Dissection of a Regular Finite Element Mesh. SIAM Journal on Numerical Analysis, 10(2):345-363, 1973. Google Scholar
  17. Andrew V. Goldberg and Chris Harrelson. Computing the Shortest Path: A* Search Meets Graph Theory. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'05), pages 156-165. SIAM, 2005. Google Scholar
  18. Lars Gottesbüren, Michael Hamann, Tim Niklas Uhl, and Dorothea Wagner. Faster and Better Nested Dissection Orders for Customizable Contraction Hierarchies. Algorithms, 12(9):196, 2019. URL: https://doi.org/10.3390/a12090196.
  19. Peter E. Hart, Nils Nilsson, and Bertram Raphael. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4:100-107, 1968. Google Scholar
  20. Martin Holzer, Frank Schulz, and Dorothea Wagner. Engineering Multilevel Overlay Graphs for Shortest-Path Queries. ACM Journal of Experimental Algorithmics, 13(2.5):1-26, December 2008. Google Scholar
  21. Spyros Kontogiannis, George Michalopoulos, Georgia Papastavrou, Andreas Paraskevopoulos, Dorothea Wagner, and Christos Zaroliagis. Engineering Oracles for Time-Dependent Road Networks. In Proceedings of the 18th Meeting on Algorithm Engineering and Experiments (ALENEX'16), pages 1-14. SIAM, 2016. URL: http://epubs.siam.org/doi/abs/10.1137/1.9781611974317.1.
  22. Spyros Kontogiannis, Georgia Papastavrou, Andreas Paraskevopoulos, Dorothea Wagner, and Christos Zaroliagis. Improved Oracles for Time-Dependent Road Networks. In Proceedings of the 17th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'17), volume 59 of OpenAccess Series in Informatics (OASIcs), pages 4:1-4:17, 2017. URL: https://doi.org/10.4230/OASIcs.ATMOS.2017.4.
  23. Ulrich Lauther. An Extremely Fast, Exact Algorithm for Finding Shortest Paths in Static Networks with Geographical Background. In Geoinformation und Mobilität - von der Forschung zur praktischen Anwendung, volume 22, pages 219-230. IfGI prints, 2004. Google Scholar
  24. Giacomo Nannicini, Daniel Delling, Leo Liberti, and Dominik Schultes. Bidirectional A* Search on Time-Dependent Road Networks. Networks, 59:240-251, 2012. Best Paper Award. Google Scholar
  25. Ariel Orda and Raphael Rom. Traveling without waiting in time-dependent networks is NP-hard. Technical report, Dept. Electrical Engineering, Technion-Israel Institute of Technology, 1989. Google Scholar
  26. Ben Strasser. Dynamic Time-Dependent Routing in Road Networks Through Sampling. In Proceedings of the 17th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'17), volume 59 of OpenAccess Series in Informatics (OASIcs), pages 3:1-3:17, 2017. URL: https://doi.org/10.4230/OASIcs.ATMOS.2017.3.
  27. Michael Zündorf. Customizable Contraction Hierarchies with Turn Costs. Bachelor thesis, Karlsruhe Institute of Technology, 2019. 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