TD-H2H: Shortest Path Query on Time-Dependent Graphs

A shortest path query on road networks is a fundamental problem, which has been studied widely. Existing studies usually model road networks as a static graph and query the path with the shortest distance between given vertices. However, a road network has time-dependent property, so modeling the road network as a time-dependent graph is more realistic. Compared with the static graph, the time-dependent graph is larger and more complex, which increases the difficulty of time-dependent shortest path query. The time-dependent shortest path refers to the path with the shortest travel time between a source and a destination in a time-dependent graph under a given departure time. Therefore, the result of the time-dependent shortest path is impacted by the given departure time, which brings a new challenge for the query. These difficulties and challenges make the traditional shortest path algorithms not applicable to the time-dependent shortest path query. This paper employs a time-dependent graph to model the road network, and TD-H2H (time dependent-hierarchical 2-hop) index is proposed based on the tree decomposition, which can be used to quickly and accurately solve the time-dependent shortest path problem. Firstly, a time-dependent tree decomposition algorithm based on the traditional tree decomposition is presented to transform the time-dependent graph into a tree structure. Then, the index structure is quickly determined by tree decomposition, and an efficient index construction algorithm is proposed, denoted as TD-H2H. Finally, based on the TD-H2H index, an efficient time-dependent shortest path query algorithm is designed, named as TD-OAI. Experiments with existing algorithms are performed on 4 real-world datasets. Experimental results show that the query speed of the proposed algorithm is 1 to 2 orders of magnitude better than existing algorithms, and prove the effectiveness and efficiency of the proposed algorithms.