Engineering highway hierarchies

Abstract

Highway hierarchies exploit hierarchical properties inherent in real-world road networks to allow fast and exact point-to-point shortest-path queries. A fast preprocessing routine iteratively performs two steps: First, it removes edges that only appear on shortest paths close to source or target; second, it identifies low-degree nodes and bypasses them by introducing shortcut edges. The resulting hierarchy of highway networks is then used in a Dijkstra-like bidirectional query algorithm to considerably reduce the search space size without losing exactness. The crucial fact is that ‘far away’ from source and target it is sufficient to consider only high-level edges.

Experiments with road networks for a continent show that using a preprocessing time of around 15 min, one can achieve a query time of around 1ms on a 2.0GHz AMD Opteron.

Highway hierarchies can be combined with goal-directed search, they can be extended to answer many-to-many queries, and they can be used as a basis for other speed-up techniques (e.g., for transit-node routing and highway-node routing).

References

1. Abraham, I., Delling, D., Goldberg, A. V., and Werneck, R. F. 2010. A hub-based labeling algorithm for shortest paths on road networks. Tech. rep. MSR-TR-2010-165, Microsoft Research.
2. Bast, H., Funke, S., Matijevic, D., Sanders, P., and Schultes, D. 2007. In transit to constant time shortest-path queries in road networks. In Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX). 46--59.
3. Batz, G., Delling, D., Sanders, P., and Vetter, C. 2009. Time-dependent contraction hierarchies. In Proceedings of the 10th Workshop on Algorithm Engineering and Experiments (ALENEX). 97--105. http://algo2.iti.uni-karlsruhe.de/1222.php.
4. Bauer, R. and Delling, D. 2008. SHARC: fast and robust unidirectional routing. In Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX'08).
5. Bauer, R., Delling, D., Sanders, P., Schieferdecker, D., Schultes, D., and Wagner, D. 2008. Combining hierarchical and goal-directed speed-up techniques for Dijkstra's algorithm. In Proceedings of the 7th Workshop on Experimental Algorithms (WEA'08). Lecture Notes in Computer Science, vol. 5038, Springer, 303--318.
6. Bauer, R., Delling, D., and Wagner, D. 2007. Experimental study on speed-up techniques for timetable information systems. In Proceedings of the 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07).
7. Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. 2001. Introduction to Algorithms. 2nd Ed. MIT Press.
8. Delling, D. 2008. Time-dependent SHARC-routing. In Proceedings of the 16th Annual European Symposium on Algorithms (ESA'08). Lecture Notes in Computer Science, vol. 5193, Springer, 332--343.
9. Delling, D., Sanders, P., Schultes, D., and Wagner, D. 2006. Highway hierarchies star. In Proceedings of the 9th DIMACS Implementation Challenge.
10. Delling, D., Sanders, P., Schultes, D., and Wagner, D. 2009. Engineering route planning algorithms. In Proceedings of the Algorithmics of Large and Complex Networks. Lecture Notes in Computer Science, vol. 5515, Springer, 117--139.
11. Dijkstra, E. W. 1959. A note on two problems in connexion with graphs. Numerische Mathematik 1, 269--271.
12. DIMACS 9th Implementation Challenge. 2006. Shortest Paths. http://www.dis.uniroma1.it/~challenge9/.
13. Fakcharoenphol, J. and Rao, S. 2001. Planar graphs, negative weight edges, shortest paths, and near linear time. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. 232--241.
14. Geisberger, R., Sanders, P., Schultes, D., and Delling, D. 2008. Contraction hierarchies: faster and simpler hierarchical routing in road networks. In Proceedings of the 7th Workshop on Experimental Algorithms. Lecture Notes in Computer Science, vol. 5038, Springer, 319--333.
15. Geisberger, R., Sanders, P., Schultes, D., and Vetter, C. 2012. Exact routing in large road networks using contraction hierarchies. Transport. Sci.
16. Goldberg, A., Kaplan, H., and Werneck, R. F. 2006. Reach for A^*: efficient point-to-point shortest path algorithms. In Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX'06). 129--143.
17. Goldberg, A. V. and Harrelson, C. 2005. Computing the shortest path: A^* meets graph theory. In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms. 156--165.
18. Goldberg, A. V., Kaplan, H., and Werneck, R. F. 2007. Better landmarks within reach. In Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07). Lecture Notes in Computer Science, vol. 4525, Springer, 38--51.
19. Goldberg, A. V. and Werneck, R. F. 2005. Computing point-to-point shortest paths from external memory. In Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX'05). 26--40.
20. Gutman, R. 2004. Reach-based routing: A new approach to shortest path algorithms optimized for road networks. In Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX'04). 100--111.
21. Hart, P. E., Nilsson, N. J., and Raphael, B. 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4, 2, 100--107.
22. Ishikawa, K., Ogawa, M., Azume, S., and Ito, T. 1991. Map navigation software of the electro multivision of the '91 Toyota Soarer. In Proceedings of the IEEE International Conference on Vehicle Navigation Information System. 463--473.
23. Jagadeesh, G., Srikanthan, T., and Quek, K. 2002. Heuristic techniques for accelerating hierarchical routing on road networks. IEEE Trans. Intell. Transport. Syst. 3, 4, 301--309.
24. Knopp, S., Sanders, P., Schultes, D., Schulz, F., and Wagner, D. 2007. Computing many-to-many shortest paths using highway hierarchies. In Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX'07).
25. Köhler, E., Möhring, R. H., and Schilling, H. 2005. Acceleration of shortest path and constrained shortest path computation. In Proceedings of the 4th International Workshop on Efficient and Experimental Algorithms (WEA'05).
26. Köhler, E., Möhring, R. H., and Schilling, H. 2006. Fast point-to-point shortest path computations with arc-flags. In Proceedings of the 9th DIMACS Implementation Challenge.
27. Lauther, U. 2004. An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background. In Proceedings of the Geoinformation und Mobilität -- von der Forschung zur praktischen Anwendung. Vol. 22. IfGI prints, Institut für Geoinformatik, Münster, 219--230.
28. Lauther, U. 2006. An experimental evaluation of point-to-point shortest path calculation on roadnetworks with precalculated edge-flags. In Proceedings of the 9th DIMACS Implementation Challenge.
29. Maue, J., Sanders, P., and Matijevic, D. 2006. Goal directed shortest path queries using Precomputed Cluster Distances. In Proceedings of the 5th Workshop on Experimental Algorithms (WEA'06). Lecture Notes in Computer Science, vol. 4007, Springer, 316--328.
30. Maue, J., Sanders, P., and Matijevic, D. 2009. Goal directed shortest path queries using Precomputed Cluster Distances. ACM J. Exp. Algor. (submitted for special issue on WEA'06).
31. Möhring, R., Schilling, H., Schütz, B., Wagner, D., and Willhalm, T. 2005. Partitioning graphs to speed up Dijkstra's algorithm. In Proceedings of the 4th International Workshop on Efficient and Experimental Algorithms (WEA'05). 189--202.
32. Möhring, R. H., Schilling, H., Schütz, B., Wagner, D., and Willhalm, T. 2007. Partitioning graphs to speed up dijkstra's algorithm. ACM J. Exp. Algor. 11.
33. Müller, K. 2005. Berechnung kürzester Pfade unter Beachtung von Abbiegeverboten. Student Research Project, Universität Karlsruhe (TH).
34. Muller, L. F. and Zachariasen, M. 2007. Fast and compact oracles for approximate distances in planar graphs. In Proceedings of the 15th European Symposium on Algorithms (ESA'07). Lecture Notes in Computer Science, vol. 4698, Springer, 657--668.
35. Nannicini, G., Baptiste, P., Barbier, G., Krob, D., and Liberti, L. 2010. Fast paths in large-scale dynamic road networks. Comput. Optim. Appl. 45, 1, 143--158.
36. R Development Core Team. 2004. R: A language and environment for statistical computing. http://www.r-project.org.
37. Sanders, P. and Schultes, D. 2005. Highway hierarchies hasten exact shortest path queries. In Proceedings of the 13th European Symposium on Algorithms (ESA'05). Lecture Notes in Computer Science, vol. 3669, Springer, 568--579.
38. Sanders, P. and Schultes, D. 2006. Engineering highway hierarchies. In Proceedings of the 14th European Symposium on Algorithms (ESA'06). Lecture Notes in Computer Science, vol. 4168, Springer, 804--816.
39. Schmid, W. 2000. Berechnung kürzester wege in straßennetzen mit wegeverboten. Ph.D. thesis, Universität Stuttgart.
40. Schultes, D. 2008. Route planning in road networks. Ph.D. thesis, Universität Karlsruhe (TH).
41. Schultes, D. and Sanders, P. 2007. Dynamic highway-node routing. In Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07). Lecture Notes in Computer Science, vol. 4525, Springer, 66--79.
42. Schulz, F., Wagner, D., and Weihe, K. 1999. Dijkstra's algorithm on-line: An empirical case study from public railroad transport. In Proceedings of the 3rd Workshop on Algorithm Engineering (WAE'99). Lecture Notes in Computer Science, vol. 1668, Springer, 110--123.
43. Schulz, F., Wagner, D., and Zaroliagis, C. D. 2002. Using multi-level graphs for timetable information. In Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX'02). Lecture Notes in Computer Science, vol. 2409, Springer, 43--59.
44. Skiena, S. S. 1998. The Algorithm Design Manual. Springer.
45. Thorup, M. 2001. Compact oracles for reachability and approximate distances in planar digraphs. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. 242--251.
46. U.S. Census Bureau, Washington, DC. 2002. UA Census 2000 TIGER/Line Files. http://www.census.gov/geo/www/tiger/tigerua/ua_tgr2k.html.
47. Wagner, D. and Willhalm, T. 2003. Geometric speed-up techniques for finding shortest paths in large sparse graphs. In Proceedings of the 11th European Symposium on Algorithms (ESA'03). Lecture Notes in Computer Science, vol. 2832, Springer, 776--787.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms