Route planning with flexible edge restrictions

Abstract

In this work, we explore a new type of flexible shortest-path query, in which the query can be dynamically parameterized to constrain the type of edges that may be included in the resulting shortest path (e.g., find the shortest path in a road network that avoids toll roads and low overpasses, respective of the specified vehicle height). We extend the hierarchical preprocessing technique known as Contraction Hierarchies to efficiently support such flexible queries. We also present several effective algorithmic optimizations for further improving the overall scalability and query times of this approach, including the addition of goal-directed search techniques, search space pruning techniques, and generalizing the constraints of the local search. Experiments are presented for both the North American and the European road networks, showcasing the general effectiveness and scalability of our proposed methodology to large-scale, real-world graphs.

References

1. Bauer, R., Delling, D., Sanders, P., Schieferdecker, D., Schultes, D., and Wagner, D. 2010. Combining hierarchical and goal-directed speed-up techniques for Dijkstra's algorithm. ACM J. Exp. Algor. 15, 2.3, 1--31. (Special Section WEA'08.)
2. Delling, D., Sanders, P., Schultes, D., and Wagner, D. 2009. Engineering route planning algorithms. In Algorithmics of Large and Complex Networks, J. Lerner, D. Wagner, and K. A. Zweig, Eds., Lecture Notes in Computer Science, vol. 5515, Springer, Berlin, 117--139.
3. Delling, D. and Wagner, D. 2007. Landmark-based routing in dynamic graphs. In Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07). Lecture Notes in Computer Science, vol. 4525, Springer, Berlin, 52--65.
4. Demetrescu, C., Ed. 2007. Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07). Lecture Notes in Computer Science, vol. 4525, Springer, Berlin.
5. Dijkstra, E. W. 1959. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik 1, 269--271.
6. Geisberger, R., Kobitzsch, M., and Sanders, P. 2010. Route planning with flexible objective functions. In Proceedings of the 12th Workshop on Algorithm Engineering and Experiments (ALENEX'10). SIAM, Philadelphia, 124--137.
7. 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). C. C. McGeoch, Ed., Lecture Notes in Computer Science, vol. 5038, Springer, Berlin, 319--333.
8. 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). SIAM, Philadelphia, 156--165.
9. Goldberg, A. V. and Werneck, R. F. 2005. Computing point-to-point shortest paths from external memory. In Proceedings of the 7th Workshop on Algorithm Engineering and Experiments (ALENEX'05). SIAM, Philadelphia, 26--40.
10. Hart, P. E., Nilsson, N., and Raphael, B. 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4, 100--107.
11. Hilger, M., Köhler, E., Möhring, R. H., and Schilling, H. 2009. Fast point-to-point shortest path computations with arc-flags. 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, 41--72.
12. Holzer, M., Schulz, F., and Wagner, D. 2008. Engineering multi-level overlay graphs for shortest-path queries. ACM J. Exp. Algor. 13, 2.5, 1--26.
13. 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 prints, 219--230.
14. Rice, M. N. and Tsotras, V. J. 2010. Graph indexing of road networks for shortest path queries with label restrictions. Proc. VLDB Endow. 4, 2, 69--80.
15. 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). Lecture Notes in Computer Science, vol. 3669, Springer, Berlin, 568--579.
16. 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, Berlin, 66--79.

Index Terms

• Information systems

  • Information retrieval

  • Information storage systems