Querying Shortest Path on Large Time-Dependent Road Networks with Shortcuts
Zengyang Gong, Yuxiang Zeng, Lei Chen
Abstract
Querying the shortest path between two locations is a fundamental task in many applications, and has been extensively studied for static road networks. However, in reality, the travel costs of road segments evolve over time, and hence the road network can be modeled as a time-dependent graph. In this paper, we study the shortest path query over large-scale time-dependent road networks. We first present a tree decomposition method to model the time-dependent road network as a tree structure that preserves travel costs. To further improve query efficiency, a set of shortcuts is selected and built on the constructed tree structure. Specifically, we formally define a shortcut selection problem over the tree decomposition of the time-dependent road network. This problem, which is proven to be NP-hard, aims to select and build the most effective shortcut set. We first devise a dynamic programming method with exact results to solve the selection problem. To obtain the optimal shortcut set quickly, we design an approximation algorithm that guarantees a 0.5-approximation ratio. Based on the novel tree structure, we devise a shortcut-based algorithm to answer the shortest path query over time-dependent road networks. Finally, we conduct extensive performance studies using large-scale real-world road networks. The results demonstrate that our method can achieve better efficiency and scalability than the state-of-the-art method.