Abstract: 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.

Key words: time-dependent graph, road network, tree decomposition, time-dependent index, shortest path

摘要： 道路网络上的最短路径查询是一个已经被广泛研究的基本问题。现有的研究通常将道路网络建模为静态图，查询给定节点间距离最短的路径。然而，道路网络具有时序性，将道路网络建模为时序图更符合实际情况。与静态图相比，时序图的规模更大，结构也更为复杂，增加了时序最短路径的查询难度。时序最短路径是指在给定出发时间下，时序图上源节点和目的节点之间旅行时间最短的路径。因此，时序最短路径的结果受给定出发时间影响，为时序最短路径的查询带来了新的挑战，传统的最短路径算法不适用于时序最短路径的查询。将道路网络建模为时序图，并基于树分解提出了TD-H2H索引，利用该索引可以快速准确地实现时序最短路经查询。首先，研究了时序图上的树分解问题，提出时序树分解算法，将图结构转变为树结构。然后，通过树分解快速确定索引结构，提出了高效的索引构建算法，用以构建TD-H2H索引。最后，基于TD-H2H设计了高效的最短路径查询算法TD-OAI。在4个真实公开的数据集上与现有算法进行了实验，结果表明提出算法的查询效率优于现有算法1~2个数量级，证明了提出算法的有效性和效率。

关键词: 时序图, 道路网络, 树分解, 时序索引, 最短路径