Combining hierarchical and goal-directed speed-up techniques for dijkstra's algorithm

Abstract

In recent years, highly effective hierarchical and goal-directed speed-up techniques for routing in large road networks have been developed. This article makes a systematic study of combinations of such techniques. These combinations turn out to give the best results in many scenarios, including graphs for unit disk graphs, grid networks, and time-expanded timetables. Besides these quantitative results, we obtain general insights for successful combinations.

References

1. Bast, H., Funke, S., Matijevic, D., Sanders, P., and Schultes, D. 2007. In transit to constant shortest-path queries in road networks. In Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX'07). SIAM, Philadelphia, 46--59.
2. Bast, H., Funke, S., Sanders, P., and Schultes, D. 2007. Fast routing in road networks with transit modes. Science 316, 5824, 566.
3. Batz, G. V., Delling, D., Sanders, P., and Vetter, C. 2009. Time-dependent contraction hierarchies. In Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX'09). SIAM, Philadelphia, 97--105.
4. Bauer, R. and Delling, D. 2008. SHARC: Fast and robust unidirectional routing. In Proceedings of the 10th Workshop on Algorithm Engineering and Experiments (ALENEX'08). SIAM, Philadelphia, 13--26.
5. Bauer, R. and Delling, D. 2009. SHARC: Fast and robust unidirectional routing. ACM J. Exp. Algorithmics 14, 2.4--2.29.
6. 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). Springer, Berlin, 303--318.
7. 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).
8. Beier, R., Funke, S., Matijevic, D., and Sanders, P. 2009. Energy-efficient paths in radio networks. Algorithmica.
9. Chan, T. M., Efrat, A., and Har-Peled, S. 2001. Fly cheaply: On the minimum fuel consumption problem. J. Algorithms 41, 2, 330--337.
10. Dantzig, G. B. 1962. Linear Programming and Extensions. Princeton University Press.
11. Delling, D. 2008. Time-dependent SHARC-routing. In Proceedings of the 16th Annual European Symposium on Algorithms (ESA'08). Springer, Berlin, 332--343.
12. Delling, D. 2009. Time-dependent SHARC-routing. Algorithmica.
13. Delling, D. and Nannicini, G. 2008. Bidirectional core-based routing in dynamic time-dependent road networks. In Proceedings of the 19th International Symposium on Algorithms and Computation (ISAAC'08). Springer, Berlin, 813--824.
14. Delling, D., Pajor, T., and Wagner, D. 2008. Engineering time-expanded graphs for faster timetable information. In Proceedings of the 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08).
15. Delling, D., Sanders, P., Schultes, D., and Wagner, D. 2009a. Engineering route planning algorithms. In Algorithmics of Large and Complex Networks. Springer, Berlin, 117--139.
16. Delling, D., Sanders, P., Schultes, D., and Wagner, D. 2009b. Highway hierarchies star. In The Shortest Path Problem: Ninth DIMACS Implementation Challenge, C. Demetrescu, A. V. Goldberg, and D. S. Johnson, Eds. DIMACS Book, vol. 74. American Mathematical Society, Providence, RI, 141--174.
17. Delling, D. and Wagner, D. 2007. Landmark-based routing in dynamic graphs. In Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07). Springer, Berlin, 52--65.
18. Delling, D. and Wagner, D. 2009. Pareto paths with SHARC. In Proceedings of the 8th International Symposium on Experimental Algorithms (SEA'09). Springer, Berlin, 125--136.
19. Demetrescu, C., Goldberg, A. V., and Johnson, D. S., Eds. 2006. Proceedings of the 9th DIMACS Implementation Challenge—Shortest Paths. American Mathematical Society, Providence, RI.
20. Dijkstra, E. W. 1959. A note on two problems in connexion with graphs. Numerische Mathematik 1, 269--271.
21. 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 (WEA'08).Springer, Berlin, 319--333.
22. Goldberg, A. V. and Harrelson, C. 2005. Computing the shortest path: A* search meets graph theory. In Proceedings of the 16th Annual ACM--SIAM Symposium on Discrete Algorithms (SODA'05). ACM, New York, 156--165.
23. Goldberg, A. V., Kaplan, H., and Werneck, R. F. 2006. Reach for A*: Efficient point-to-point shortest path algorithms. In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments (ALENEX'06). SIAM, Philadelphia, 129--143.
24. 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). Springer, Berlin, 38--51.
25. Goldberg, A. V., Kaplan, H., and Werneck, R. F. 2009. Reach for A*: shortest path algorithms with preprocessing. In The Shortest Path Problem: Ninth DIMACS Implementation Challenge, C. Demetrescu, A. V. Goldberg, and D. S. Johnson, Eds. DIMACS Book, vol. 74. American Mathematical Society, Providence, RI, 93--139.
26. Goldberg, A. V. and Werneck, R. F. 2005. Computing point-to-point shortest paths from external, emory. In Proceedings of the 7th Workshop on Algorithm Engineering and Experiments (ALENEX'05). SIAM, Philadelphia, 26--40.
27. Gutman, R. J. 2004. Reach-based routing: A new approach to shortest path algorithms optimized for road networks. In Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX'04). SIAM, Philadelphia, 100--111.
28. Hilger, M., Köhler, E., Möhring, R. H., and Schilling, H. 2009. Fast point-to-point shortest path computations with ArcFlags. In The Shortest Path Problem: Ninth DIMACS Implementation Challenge, C. Demetrescu, A. V. Goldberg, and D. S. Johnson, Eds. DIMACS Book, vol. 74. American Mathematical Society, Providence, RI, 41--72.
29. Holzer, M., Schulz, F., and Wagner, D. 2006. Engineering multi-level overlay graphs for shortest-path queries. In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments (ALENEX'06). SIAM, Philadelphia, 156--170.
30. Holzer, M., Schulz, F., Wagner, D., and Willhalm, T. 2006. Combining speed-up techniques for shortest-path computations. ACM J. Exp. Algorithmics 10, 2.5.
31. Holzer, M., Schulz, F., and Willhalm, T. 2004. Combining speed-up techniques for Shortest path computations. In Proceedings of the 3rd Workshop on Experimental Algorithms (WEA'04). Springer, Berlin, 269--284.
32. 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 Workshop on Experimental Algorithms (WEA'05). Springer, Berlin, 126--138.
33. Lauther, U. 2004. 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. vol. 22. IfGI, 219--230.
34. Möhring, R. H., Schilling, H., Schütz, B., Wagner, D., and Willhalm, T. 2005. Partitioning graphs to speed up Dijkstra's algorithm. In Proceedings of the 4th Workshop on Experimental Algorithms (WEA'05). Springer, Berlin, 189--202.
35. Pellegrini, F. 2007. SCOTCH: Static mapping, graph, mesh and hyper-graph partitioning, and parallel and sequential sparse matrix ordering package. http://www.labri.fr/perso/pelegrin/scotch/.
36. Sanders, P. and Schultes, D. 2005. Highway hierarchies hasten exact shortest path queries. In Proceedings of the 13th Annual European Symposium on Algorithms (ESA'05). Springer, Berlin, 568--579.
37. Sanders, P. and Schultes, D. 2006. Engineering highway hierarchies. In Proceedings of the 14th Annual European Symposium on Algorithms (ESA'06). Springer, Berlin, 804--816.
38. Schieferdecker, D. 2008. Systematic combination of speed-up techniques for exact shortest path queries. M.S. thesis, Universität Karlsruhe (TH), Fakultät für Informatik.
39. Schultes, D. 2008. Route planning in road networks. Ph.D. thesis, Universitäat Karlsruhe (TH), Fakultät für Informatik. http://algo2.iti.uka.de/schultes/hwy/schultes_diss.pdf.
40. Schultes, D. and Sanders, P. 2007. Dynamic highway-node routing. In Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07). Springer, Berlin, 66--79.
41. Schulz, F., Wagner, D., and Weihe, K. 2000. Dijkstra's algorithm online: An empirical case study from public railroad transport. ACM J. Exp. Algorithmics 5,12.
42. Schulz, F., Wagner, D., and Zaroliagis, C. 2002. Using multi-level graphs for timetable information in railway systems. In Proceedings of the 4th Workshop on Algorithm Engineering and Experiments (ALENEX'02). Springer, Berlin, 43--59.
43. Wagner, D., Willhalm, T., and Zaroliagis, C. 2005. Geometric containers for efficient shortest path computation. ACM J. Exp. Algorithmics 10, 1.3.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory