Document Open Access Logo

More Hierarchy in Route Planning Using Edge Hierarchies

Authors Demian Hespe, Peter Sanders

PDF

File

Thumbnail PDF
PDF
OASIcs.ATMOS.2019.10.pdf
  • Filesize: 0.58 MB
  • 14 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Shortest paths
  • Mathematics of computing → Paths and connectivity problems
  • Mathematics of computing → Graph algorithms
Keywords
  • shortest path
  • hierarchy
  • road networks
  • preprocessing

Metrics

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

Abstract

A highly successful approach to route planning in networks (particularly road networks) is to identify a hierarchy in the network that allows faster queries after some preprocessing that basically inserts additional "shortcut"-edges into a graph. In the past there has been a succession of techniques that infer a more and more fine grained hierarchy enabling increasingly more efficient queries. This appeared to culminate in contraction hierarchies that assign one hierarchy level to each vertex.
In this paper we show how to identify an even more fine grained hierarchy that assigns one level to each edge of the network. Our findings indicate that this can lead to considerably smaller search spaces in terms of visited edges. Currently, this rarely implies improved query times so that it remains an open question whether edge hierarchies can lead to consistently improved performance. However, we believe that the technique as such is a noteworthy enrichment of the portfolio of available techniques that might prove useful in the future.

Cite As Get BibTex

Demian Hespe and Peter Sanders. More Hierarchy in Route Planning Using Edge Hierarchies. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/OASIcs.ATMOS.2019.10

Author Details

Demian Hespe
  • Karlsruhe Institute of Technology, Germany
  • www.kit.edu
Peter Sanders
  • Karlsruhe Institute of Technology, Germany
  • www.kit.edu

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 10th Symposium on Experimental Algorithms (SEA), volume 6630 of LNCS, pages 230-241, 2011. URL: https://doi.org/10.1007/978-3-642-20662-7_20.
  2. Julian Arz, Dennis Luxen, and Peter Sanders. Transit node routing reconsidered. In 12th International Symposium on Experimental Algorithms (SEA), volume 7933 of LNCS, pages 55-66. Springer, 2013. 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. Holger Bast, Stefan Funke, Peter Sanders, and Dominik Schultes. Fast routing in road networks with transit nodes. Science, 316(5824):566, 2007. Google Scholar
  5. Gernot Veit Batz, Robert Geisberger, Peter Sanders, and Christian Vetter. Minimum time-dependent travel times with contraction hierarchies. ACM Journal of Experimental Algorithmics, 18, 2013. URL: https://doi.org/10.1145/2444016.2444020.
  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, 2010. URL: https://doi.org/10.1145/1671970.1671976.
  7. Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck. Customizable route planning in road networks. Transportation Science, 51(2):566-591, 2015. Google Scholar
  8. Camil Demetrescu, Andrew V. Goldberg, and David S. Johnson. The Shortest Path Problem: Ninth DIMACS Implementation Challenge, volume 74. American Mathematical Soc., 2009. Google Scholar
  9. Julian Dibbelt, Ben Strasser, and Dorothea Wagner. Customizable contraction hierarchies. ACM Journal of Experimental Algorithmics, 21:1-5, 2016. Google Scholar
  10. Edsger W Dijkstra. A note on two problems in connexion with graphs. Numerische mathematik, 1(1):269-271, 1959. Google Scholar
  11. Robert Geisberger, Peter Sanders, Dominik Schultes, and Daniel Delling. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In 7th Workshop on Experimental Algorithms (WEA), volume 5038 of LNCS, pages 319-333. Springer, 2008. Google Scholar
  12. 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
  13. Andrew V. Goldberg, Haim Kaplan, and Renato F. Werneck. Reach for A*: Efficient point-to-point shortest path algorithms. In 8th Workshop on Algorithm Engineering and Experiments (ALENEX), Miami, 2006. Google Scholar
  14. Ronald J. Gutman. Reach-based routing: A new approach to shortest path algorithms optimized for road networks. In 6th Workshop on Algorithm Engineering and Experiments (ALENEX), pages 100-111, 2004. Google Scholar
  15. Kunihiro Ishikawa, Michima Ogawa, Shigetoshi Azuma, and Tooru Ito. Map navigation software of the electro-multivision of the'91 Toyota Soarer. In Vehicle Navigation and Information Systems Conference, volume 2, pages 463-473. IEEE, 1991. Google Scholar
  16. George R. Jagadeesh, Thambipillai Srikanthan, and K. H. Quek. Heuristic techniques for accelerating hierarchical routing on road networks. IEEE Transactions on intelligent transportation systems, 3(4):301-309, 2002. Google Scholar
  17. Spyros C. Kontogiannis, Dorothea Wagner, and Christos D. Zaroliagis. Hierarchical time-dependent oracles. In 27th International Symposium on Algorithms and Computation (ISAAC), pages 47:1-47:13, 2016. Google Scholar
  18. Jens Maue, Peter Sanders, and Domagoj Matijevic. Goal directed shortest path queries using Precomputed Cluster Distances. ACM Journal of Experimental Algorithmics, 14, 2009. Google Scholar
  19. Rolf H. Möhring, Heiko Schilling, Birk Schütz, Dorothea Wagner, and Thomas Willhalm. Partitioning graphs to speed up Dijkstra’s algorithm. In 4th Workshop on Efficient and Experimental Algorithms (WEA), pages 189-202, 2005. Google Scholar
  20. Peter Sanders and Dominik Schultes. Highway hierarchies hasten exact shortest path queries. In 13th Annual European Symposium on Algorithms (ESA), pages 568-579. Springer, 2005. Google Scholar
  21. Dominik Schultes and Peter Sanders. Dynamic highway-node routing. In 6th Workshop on Experimental Algorithms (WEA), volume 4525 of LNCS, pages 66-79. Springer, 2007. Google Scholar
  22. Frank Schulz, Dorothea Wagner, and Christos D. Zaroliagis. Using multi-level graphs for timetable information. In 4th Workshop on Algorithm Engineering and Experiments (ALENEX), volume 2409 of LNCS, pages 43-59. Springer, 2002. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact