Document Open Access Logo

A Fast and Tight Heuristic for A* in Road Networks

Authors Ben Strasser, Tim Zeitz

PDF
Thumbnail PDF

File

LIPIcs.SEA.2021.6.pdf
  • Filesize: 1.71 MB
  • 16 pages

Document Identifiers

Author Details

Ben Strasser
  • Stuttgart, Germany
Tim Zeitz
  • Karlsruhe Institute of Technology, Germany

Cite As Get BibTex

Ben Strasser and Tim Zeitz. A Fast and Tight Heuristic for A* in Road Networks. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.SEA.2021.6

Abstract

We study exact, efficient and practical algorithms for route planning in large road networks. Routing applications often require integrating the current traffic situation, planning ahead with traffic predictions for the future, respecting forbidden turns, and many other features depending on the exact application. While Dijkstra’s algorithm can be used to solve these problems, it is too slow for many applications. A* is a classical approach to accelerate Dijkstra’s algorithm. A* can support many extended scenarios without much additional implementation complexity. However, A*’s performance depends on the availability of a good heuristic that estimates distances. Computing tight distance estimates is a challenge on its own. On road networks, shortest paths can also be quickly computed using hierarchical speedup techniques. They achieve speed and exactness but sacrifice A*’s flexibility. Extending them to certain practical applications can be hard. In this paper, we present an algorithm to efficiently extract distance estimates for A* from Contraction Hierarchies (CH), a hierarchical technique. We call our heuristic CH-Potentials. Our approach allows decoupling the supported extensions from the hierarchical speed-up technique. Additionally, we describe A* optimizations to accelerate the processing of low degree nodes, which often occur in road networks.

Subject Classification

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

Metrics

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

Supplementary Materials

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. Google Scholar
  2. Gernot Veit Batz. Time-Dependent Route Planning with Contraction Hierarchies. PhD thesis, Karlsruhe Institute of Technology (KIT), 2014. Google Scholar
  3. Gernot Veit Batz, Daniel Delling, Peter Sanders, and Christian Vetter. Time-Dependent Contraction Hierarchies. In Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX'09), pages 97-105. SIAM, April 2009. Google Scholar
  4. Gernot Veit Batz, Robert Geisberger, Sabine Neubauer, and Peter Sanders. Time-Dependent Contraction Hierarchies and Approximation. In Paola Festa, editor, Proceedings of the 9th International Symposium on Experimental Algorithms (SEA'10), volume 6049 of Lecture Notes in Computer Science, pages 166-177. Springer, May 2010. URL: http://www.springerlink.com/content/u787292691813526/.
  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(1.4):1-43, April 2013. Google Scholar
  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(2.3):1-31, January 2010. Special Section devoted to WEA'08. Google Scholar
  7. Moritz Baum, Julian Dibbelt, Andreas Gemsa, Dorothea Wagner, and Tobias Zündorf. Shortest Feasible Paths with Charging Stops for Battery Electric Vehicles. Transportation Science, 2019. Google Scholar
  8. Moritz Baum, Julian Dibbelt, Thomas Pajor, Jonas Sauer, Dorothea Wagner, and Tobias Zündorf. Energy-optimal routes for battery electric vehicles. Algorithmica, 82(5):1490-1546, 2020. URL: https://doi.org/10.1007/s00453-019-00655-9.
  9. 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. Google Scholar
  10. Massimo Bono, Alfonso Emilio Gerevini, Daniel Damir Harabor, and Peter J. Stuckey. Path planning with CPD heuristics. In Sarit Kraus, editor, Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pages 1199-1205. ijcai.org, 2019. URL: https://doi.org/10.24963/ijcai.2019/167.
  11. Valentin Buchhold, Dorothea Wagner, Tim Zeitz, and Michael Zündorf. Customizable Contraction Hierarchies with Turn Costs. In Dennis Huisman and Christos Zaroliagis, editors, Proceedings of the 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'20), OpenAccess Series in Informatics (OASIcs), 2020. Accepted for publication. Google Scholar
  12. Liron Cohen, Tansel Uras, Shiva Jahangiri, Aliyah Arunasalam, Sven Koenig, and T. K. Satish Kumar. The fastmap algorithm for shortest path computations. In Jérôme Lang, editor, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden, pages 1427-1433. ijcai.org, 2018. URL: https://doi.org/10.24963/ijcai.2018/198.
  13. Daniel Delling, Andrew V. Goldberg, Andreas Nowatzyk, and Renato F. Werneck. PHAST: Hardware-accelerated shortest path trees. Journal of Parallel and Distributed Computing, 73(7):940-952, 2013. Google Scholar
  14. Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck. Customizable Route Planning in Road Networks. Transportation Science, 51(2):566-591, 2017. Google Scholar
  15. Daniel Delling and Giacomo Nannicini. Core Routing on Dynamic Time-Dependent Road Networks. Informs Journal on Computing, 24(2):187-201, 2012. Google Scholar
  16. Daniel Delling, Dennis Schieferdecker, and Christian Sommer. Traffic-Aware Routing in Road Networks. In Proceedings of the 34rd International Conference on Data Engineering. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/ICDE.2018.00172.
  17. Daniel Delling and Dorothea Wagner. Landmark-Based Routing in Dynamic Graphs. In Camil Demetrescu, editor, Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07), volume 4525 of Lecture Notes in Computer Science, pages 52-65. Springer, June 2007. Google Scholar
  18. Julian Dibbelt, Ben Strasser, and Dorothea Wagner. Fast exact shortest path and distance queries on road networks with parametrized costs. In Jie Bao, Christian Sengstock, Mohammed Eunus Ali, Yan Huang, Michael Gertz, Matthias Renz, and Jagan Sankaranarayanan, editors, Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, Bellevue, WA, USA, November 3-6, 2015, pages 66:1-66:4. ACM, 2015. URL: https://doi.org/10.1145/2820783.2820856.
  19. 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. Google Scholar
  20. Edsger W. Dijkstra. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1(1):269-271, 1959. Google Scholar
  21. Stuart E. Dreyfus. An Appraisal of Some Shortest-Path Algorithms. Operations Research, 17(3):395-412, 1969. Google Scholar
  22. Jochen Eisner, Stefan Funke, and Sabine Storandt. Optimal route planning for electric vehicles in large networks. In Wolfram Burgard and Dan Roth, editors, Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2011, San Francisco, California, USA, August 7-11, 2011. AAAI Press, 2011. URL: http://www.aaai.org/ocs/index.php/AAAI/AAAI11/paper/view/3637.
  23. Stefan Funke, André Nusser, and Sabine Storandt. On k-Path Covers and their Applications. In Proceedings of the 40th International Conference on Very Large Databases (VLDB 2014), pages 893-902, 2014. Google Scholar
  24. Robert Geisberger, Moritz Kobitzsch, and Peter Sanders. Route Planning with Flexible Objective Functions. In Proceedings of the 12th Workshop on Algorithm Engineering and Experiments (ALENEX'10), pages 124-137. SIAM, 2010. Google Scholar
  25. 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
  26. Robert Geisberger and Christian Vetter. Efficient Routing in Road Networks with Turn Costs. In Panos M. Pardalos and Steffen Rebennack, editors, Proceedings of the 10th International Symposium on Experimental Algorithms (SEA'11), volume 6630 of Lecture Notes in Computer Science, pages 100-111. Springer, 2011. Google Scholar
  27. 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
  28. Andrew V. Goldberg, Haim Kaplan, and Renato F. Werneck. Better Landmarks Within Reach. In Camil Demetrescu, editor, Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07), volume 4525 of Lecture Notes in Computer Science, pages 38-51. Springer, June 2007. Google Scholar
  29. Andrew V. Goldberg and Renato F. Werneck. Computing Point-to-Point Shortest Paths from External Memory. In Proceedings of the 7th Workshop on Algorithm Engineering and Experiments (ALENEX'05), pages 26-40. SIAM, 2005. Google Scholar
  30. Michael Hamann and Ben Strasser. Graph Bisection with Pareto Optimization. ACM Journal of Experimental Algorithmics, 23(1):1.2:1-1.2:34, 2018. URL: https://doi.org/10.1145/3173045.
  31. 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
  32. Tim Kieritz, Dennis Luxen, Peter Sanders, and Christian Vetter. Distributed Time-Dependent Contraction Hierarchies. In Paola Festa, editor, Proceedings of the 9th International Symposium on Experimental Algorithms (SEA'10), volume 6049 of Lecture Notes in Computer Science, pages 83-93. Springer, May 2010. Google Scholar
  33. Alexander Kleff, Frank Schulz, Jakob Wagenblatt, and Tim Zeitz. Efficient Route Planning with Temporary Driving Bans, Road Closures, and Rated Parking Areas. In Simone Faro and Domenico Cantone, editors, Proceedings of the 18th International Symposium on Experimental Algorithms (SEA'20), volume 160 of Leibniz International Proceedings in Informatics, 2020. URL: https://doi.org/10.4230/LIPIcs.SEA.2020.17.
  34. Maxim Likhachev, Geoffrey J. Gordon, and Sebastian Thrun. Ara*: Anytime a* with provable bounds on sub-optimality. In Sebastian Thrun, Lawrence K. Saul, and Bernhard Schölkopf, editors, Advances in Neural Information Processing Systems 16 [Neural Information Processing Systems, NIPS 2003, December 8-13, 2003, Vancouver and Whistler, British Columbia, Canada], pages 767-774. MIT Press, 2003. URL: https://proceedings.neurips.cc/paper/2003/hash/ee8fe9093fbbb687bef15a38facc44d2-Abstract.html.
  35. Bing maps new routing engine. https://blogs.bing.com/maps/2012/01/05/bing-maps-new-routing-engine/. Accessed: 2020-01-25.
  36. 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
  37. 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
  38. Frank Schulz, Dorothea Wagner, and Christos Zaroliagis. Using Multi-Level Graphs for Timetable Information in Railway Systems. In Proceedings of the 4th Workshop on Algorithm Engineering and Experiments (ALENEX'02), volume 2409 of Lecture Notes in Computer Science, pages 43-59. Springer, 2002. Google Scholar
  39. Ben Strasser, Daniel Harabor, and Adi Botea. Fast first-move queries through run-length encoding. In Stefan Edelkamp and Roman Barták, editors, Proceedings of the Seventh Annual Symposium on Combinatorial Search, SOCS 2014, Prague, Czech Republic, 15-17 August 2014. AAAI Press, 2014. URL: http://www.aaai.org/ocs/index.php/SOCS/SOCS14/paper/view/8906.
  40. Ben Strasser, Dorothea Wagner, and Tim Zeitz. Space-efficient, Fast and Exact Routing in Time-dependent Road Networks. In Proceedings of the 28th Annual European Symposium on Algorithms (ESA'20), Leibniz International Proceedings in Informatics, September 2020. Google Scholar
  41. Ben Strasser and Tim Zeitz. A* with perfect potentials, 2019. URL: http://arxiv.org/abs/1910.12526.
  42. Nathan R. Sturtevant, Jason M. Traish, James R. Tulip, Tansel Uras, Sven Koenig, Ben Strasser, Adi Botea, Daniel Harabor, and Steve Rabin. The grid-based path planning competition: 2014 entries and results. In Levi Lelis and Roni Stern, editors, Proceedings of the Eighth Annual Symposium on Combinatorial Search, SOCS 2015, 11-13 June 2015, Ein Gedi, the Dead Sea, Israel, page 241. AAAI Press, 2015. URL: http://www.aaai.org/ocs/index.php/SOCS/SOCS15/paper/view/11290.
  43. Robert Tarjan. Depth-First Search and Linear Graph Algorithms. SIAM Journal on Computing, 1972. Google Scholar
  44. Tansel Uras and Sven Koenig. Identifying hierarchies for fast optimal search. In Carla E. Brodley and Peter Stone, editors, Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, July 27 -31, 2014, Québec City, Québec, Canada, pages 878-884. AAAI Press, 2014. URL: http://www.aaai.org/ocs/index.php/AAAI/AAAI14/paper/view/8497.
  45. Rong Zhou and Eric A. Hansen. Multiple sequence alignment using anytime a^*. In Rina Dechter, Michael J. Kearns, and Richard S. Sutton, editors, Proceedings of the Eighteenth National Conference on Artificial Intelligence and Fourteenth Conference on Innovative Applications of Artificial Intelligence, July 28 - August 1, 2002, Edmonton, Alberta, Canada, pages 975-977. AAAI Press / The MIT Press, 2002. URL: http://www.aaai.org/Library/AAAI/2002/aaai02-155.php.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact