Forward search in contraction hierarchies

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

Contraction hierarchies are graph-based data structure developed to speed up shortest path search in road networks. Built during an offline pre-processing step, contraction hierarchies are always paired with an online query algorithm which is a variation on bi-directional Dijkstra search. Though effective and highly popular this combination can sometimes be difficult to extend, for example in order to leverage goal-directed heuristics or other forward-driven pruning techniques. In this paper we deconstruct the bi-directional query algorithm of contraction hierarchies and derive a new algorithmic schema which is compatible with standard uni-directional or bi-directional search. We then develop a variety of new uni-directional query algorithms to find optimal paths in contraction hierarchies. These are based on the combination of A* search and Geometric Containers, a well known and successful edge-pruning technique. Empirical results show that our approach can improve search times by an order of magnitude vs bi-directional Dijkstra, albeit at the cost of additional memory and pre-processing time.
Original languageEnglish
Title of host publicationProceedings of the Eleventh International Symposium on Combinatorial Search
EditorsVadim Bulitko, Sabine Storandt
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages55-62
Number of pages8
ISBN (Electronic)9781577358022
Publication statusPublished - 2018
EventInternational Symposium on Combinatorial Search 2018 - Stockholm, Sweden
Duration: 14 Jul 201815 Jul 2018
Conference number: 11th
https://sites.google.com/view/socs18/

Conference

ConferenceInternational Symposium on Combinatorial Search 2018
Abbreviated titleSOCS 2018
CountrySweden
CityStockholm
Period14/07/1815/07/18
Internet address

Cite this

Harabor, D. D., & Stuckey, P. J. (2018). Forward search in contraction hierarchies. In V. Bulitko, & S. Storandt (Eds.), Proceedings of the Eleventh International Symposium on Combinatorial Search (pp. 55-62). Association for the Advancement of Artificial Intelligence (AAAI). https://aaai.org/ocs/index.php/SOCS/SOCS18/paper/view/17970