Improving Time-Dependent Contraction Hierarchies
Keywords:Road Network, Time-dependent Routing, Time-dependent Contraction Hierarchies
AbstractComputing time-optimal shortest paths, in road networks, is one of the most popular applications of Artificial Intelligence. This problem is tricky to solve because road congestion affects travel times. The state-of-the-art in this area is an algorithm called Time-dependent Contraction Hierarchies (TCH). Although fast and optimal, TCH still suffers from two main drawbacks: (1) the usual query process uses bi-directional Dijkstra search to find the shortest path, which can be time-consuming; and (2) the TCH is constructed w.r.t. the entire time domain T, which complicates the search process for queries q that start and finish in a smaller time period Tq ⊂ T. In this work, we improve TCH by making use of time-independent heuristics, which speed up optimal search, and by computing TCHs for different subsets of the time domain, which further reduces the size of the search space. We give a full description of these methods and discuss their optimality-preserving characteristics. We report significant query time improvements against a baseline implementation of TCH.
How to Cite
Shen, B., Cheema, M. A., Harabor, D. D., & Stuckey, P. J. (2022). Improving Time-Dependent Contraction Hierarchies. Proceedings of the International Conference on Automated Planning and Scheduling, 32(1), 338-347. https://doi.org/10.1609/icaps.v32i1.19818