Improving Time-Dependent Contraction Hierarchies

Authors

  • Bojie Shen Monash University
  • Muhammad Aamir Cheema Monash University
  • Daniel D. Harabor Monash University
  • Peter J. Stuckey Monash University

Keywords:

Road Network, Time-dependent Routing, Time-dependent Contraction Hierarchies

Abstract

Computing 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.

Downloads

Published

2022-06-13

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. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/19818