  Querying the shortest path between two vertexes is a fundamental operation in
a variety of applications, which has been extensively studied over 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. Existing work focuses on a hierarchical partition structure,
which makes the index construction and travel cost query inefficient. To
improve the efficiency of such queries, we propose a novel index by decomposing
a road network into a tree structure and selecting a set of shortcuts on the
tree to speed up the query processing. Specifically, we first 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.
