TD-H2H：时序图上的最短路径查询

doi:10.3778/j.issn.1673-9418.2111064

摘要/Abstract

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

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

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：时序图上的最短路径查询[J]. 计算机科学与探索, 2023, 17(5): 1210-1224.

LI Xinling, WANG Yishu, YUAN Ye, GU Xiang, WANG Guoren. TD-H2H: Shortest Path Query on Time-Dependent Graphs[J]. Journal of Frontiers of Computer Science and Technology, 2023, 17(5): 1210-1224.

参考文献

[1] FAN W, HU C. Big graph analyses: from queries to depend-encies and association rules[J]. Data Science and Enginee-ring, 2017, 2: 36-55.
[2] LI L, WANG S, ZHOU X. Time-dependent hop labeling on road network[C]//Proceedings of the IEEE 35th Intern-ational Conference on Data Engineering, Macao, China, Apr 8-11, 2019. Piscataway: IEEE, 2019: 902-913.
[3] HUANG W, YU J X. Investigating TSP heuristics for location-based services[J]. Data Science and Engineering, 2017, 2: 71-93.
[4] WANG Y, YUAN Y, MA Y, et al. Time-dependent graphs: definitions, applications, and algorithms[J]. Data Science and Engineering, 2019, 4: 352-366.
[5] 杨雅君, 高宏, 李建中. 时间依赖代价函数下的最优路径查询问题研究[J]. 计算机学报, 2012, 35(11): 2247-2264.
YANG Y J, GAO H, LI J Z. Finding the optimal path under time-dependent cost function on graphs[J]. Chinese Journal of Computers, 2012, 35(11): 2247-2264.
[6] KAUFMAN D E, SMITH R L. Fastest paths in time-depen-dent networks for intelligent vehicle-highway systems app-lication[J]. Journal of Intelligent Transportation Systems, 1993, 1(1): 1-11.
[7] 马慧, 汤庸, 傅瑜, 等. 时间依赖图下的最小费用路径搜索[J]. 电子科技大学学报, 2020, 49(3): 458-466.
MA H, TANG Y, FU Y, et al. Finding the minimal cost path in time-dependent graphs[J]. Journal of University of Elect-ronic Science and Technology of China, 2020, 49(3): 458-466.
[8] HALIN R. S-functions for graphs[J]. Journal of Geometry, 1976, 8(1/2): 171-186.
[9] KLEINER W. Tree decomposition-based indexing for effi-cient shortest path and nearest neighbors query answering on graphs[J]. Journal of Computer and System Sciences, 2016, 82(1): 23-44.
[10] OUYANG D, QIN L, CHANG L J, et al. When hierarchy meets 2-hop labeling: efficient shortest distance queries on road networks[C]//Proceedings of the 2018 International Conference on Management of Data, Houston, Jun 10-15, 2018. New York: ACM, 2018: 709-724.
[11] 高文宇, 李绍华. 图的树分解及其算法应用研究进展[J]. 计算机科学, 2012, 39(3): 14-18.
GAO W Y, LI S H. Tree decomposition and its applica-tions in algorithms: survey[J]. Computer Science, 2012, 39(3): 14-18.
[12] KOSTER A, BODLAENDER H L, HOESEL S P. Treewidth: computational experiments[J]. Electronic Notes in Discrete Mathematics, 2001, 8: 54-57.
[13] SBODLAENDER H L. Treewidth: characterizations, appli-cations, and computations[C]//LNCS 4271: Proceedings of the 32nd International Workshop on Graph-Theoretic Con-cepts in Computer Science, Bergen, Jun 22-24, 2006. Berlin, Heidelberg: Springer, 2006: 1-14.
[14] DIJKSTRA E W. A note on two problems in connection with graphs[J]. Numerische Mathematik, 1959, 1(1): 269-271.
[15] CHABINI I, LAN S. Adaptations of the A* algorithm for the computation of fastest paths in deterministic discrete-time dynamic networks[J]. IEEE Transactions on Intellig-ent Transportation Systems, 2002, 3(1): 60-74.
[16] FLOYD R W. Algorithm 97: shortest path[J]. Communica-tions of the ACM, 1962, 5(6): 345-346.
[17] GEISBERGER R, SANDERS P, SCHULTES D, et al. Cont-raction hierarchies: faster and simpler hierarchical routing in road networks[C]//LNCS 5038: Proceedings of the 7th International Workshop on Experimental Algorithms, Provi-ncetown, May 30-Jun 1, 2008. Berlin, Heidelberg: Springer, 2008: 319-333.
[18] ABRAHAM I, DELLING D, GOLDBERG A V, et al. Hier-archical hub labelings for shortest paths[C]//LNCS 7501: Proceedings of the 20th Annual European Symposium on Algorithms, Ljubljana, Sep 10-12, 2012. Berlin, Heidelberg: Springer, 2012: 24-35.
[19] KANOULAS E, YANG D, TIAN X, et al. Finding fastest paths on a road network with speed patterns[C]//Procee-dings of the 22nd International Conference on Data Engine-ering, Atlanta, Apr 3-8, 2006. Washington: IEEE Computer Society, 2006: 10-19.
[20] ORDA A, ROM R. Shortest-path and minimum delay algor-ithms in networks with time-dependent edge length[J]. Jour-nal of the ACM, 1990, 37(3): 607-625.
[21] DREYFUS S E. An appraisal of some shortest path algorithms[J]. Operations Research, 1969, 17(3): 395-412.
[22] COOKE K L, HALSEY E. The shortest route through a network with time-dependent internodal transit times[J]. Jou-rnal of Mathematical Analysis and Applications, 1966，14(3): 493-498.
[23] BATZ G V, DELLING D, SANDERS P, et al. Time-depend-ent contraction hierarchies[C]//Proceedings of the 2009 Work-shop on Algorithm Engineering and Experiments, New York, Jan 3, 2009. Philadelphia: SIAM, 2009: 97-105.
[24] WANG Y, LI G L, TANG N. Querying shortest paths on time dependent road networks[J]. Proceedings of the VLDB Endowment, 2019, 12(11): 1249-1261.
[25] LI J C, JEFFREY X Y, LU Q, et al. The exact distance to destination in undirected world[J]. VLDB Journal, 2012, 21(6): 869-888.