Hops Can be Constrained: Efficient Distance Queries on Large Time-Dependent Road Networks

Weihao Yu; Dian OuYang; Fan Zhang; Xiang Zhao; Shen Su; Xuemin Lin; Zhihong Tian

doi:10.1145/3769801

journal article Dec 04, 2025

Hops Can be Constrained: Efficient Distance Queries on Large Time-Dependent Road Networks

Weihao Yu

Proceedings of the ACM on Management of Data Vol. 3 No. 6 pp. 1-25 · Association for Computing Machinery (ACM)

View at Publisher Save 10.1145/3769801

Abstract

With the increasing complexity of urban transportation systems and the growing demand for dynamic, real-time responsiveness, Time-Dependent Minimum Travel Time Queries (TD-MTTQs) in time-dependent road networks have become a core challenge in intelligent transportation system research. To address the trade-offs between preprocessing complexity and query efficiency in existing index-based methods for large-scale road network applications, this paper proposes a 4-hop index method, TD-TNR-CH. The core methodology involves establishing local indexes from each node to its nearest critical nodes (named transit nodes) through strategic critical node selection, while simultaneously constructing query tables associated with candidate sets between these critical nodes. This architecture enables rapid computation of medium-to-long distance queries through efficient index lookups, while ensuring high responsiveness for short-distance queries via TCH-based local searches. Extensive experimental results on large-scale real-world road networks demonstrate that our method exhibits superior scalability, achieving query efficiency of up to 103 times that of the fastest existing algorithms. Furthermore, it shows exceptional stability across queries of varying distances. Additionally, leveraging its parallelized architecture, TD-TNR-CH requires only approximately 30 minutes of preprocessing time for large-scale networks, significantly outperforming comparable methods in terms of preprocessing efficiency.

Topics

No keywords indexed for this article. Browse by subject →

References

51

[1]

10.1145/2463676.2465315

[2]

10.1007/978-3-642-38527-8_7

[3]

Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F Werneck. 2016. Route planning in transportation networks. Algorithm engineering: Selected results and surveys (2016), 19-80.

[4]

Holger Bast, Stefan Funke, and Domagoj Matijevic. 2006. Transit ultrafast shortest-path queries with linear-time preprocessing. 9th DIMACS Implementation Challenge [1] (2006), 19.

[5]

10.1137/1.9781611972870.5

[6]

Holger Bast, Stefan Funke, Peter Sanders, and Dominik Schultes. 2007b. Fast routing in road networks with transit nodes. Science, Vol. 316, 5824 (2007), 566-566.

[7]

10.1137/1.9781611972894.10

[8]

10.1007/978-3-642-13193-6_15

[9]

Gernot Veit Batz Robert Geisberger and Peter Sanders. 2008. Time Dependent Contraction Hierarchies-Basic Algorithmic Ideas. Technical Report. Citeseer.

[10]

G Veit Batz, Robert Geisberger, Peter Sanders, and Christian Vetter. 2013. Minimum time-dependent travel times with contraction hierarchies. Journal of Experimental Algorithmics (JEA), Vol. 18 (2013), 1-1.

[11]

10.1109/icde51399.2021.00035

[12]

10.1016/0022-247x(66)90009-6

[13]

10.1109/icde55515.2023.00161

[14]

10.1007/s00453-010-9461-6

[15]

10.1007/978-3-642-22922-0_7

[16]

A note on two problems in connexion with graphs

E. W. Dijkstra

Numerische Mathematik 10.1007/bf01386390

[17]

Edsger W Dijkstra. 2022. A note on two problems in connexion with graphs. In Edsger Wybe Dijkstra: his life work and legacy. 287-290. 10.1145/3544585.3544600

[18]

10.1145/1353343.1353371

[19]

Stuart E Dreyfus. 1969. An appraisal of some shortest-path algorithms. Operations research, Vol. 17, 3 (1969), 395-412.

[20]

Muhammad Farhan, Qing Wang, Yu Lin, and Brendan D. McKay. 2019. A Highly Scalable Labelling Approach for Exact Distance Queries in Complex Networks. (2019), 13-24.

[21]

10.1007/978-3-642-19094-0_4

[22]

10.1007/978-3-540-68552-4_24

[23]

Andrew V Goldberg and Chris Harrelson. 2005. Computing the shortest path: A search meets graph theory. In SODA, Vol. 5. 156-165.

[24]

Andrew V Goldberg Haim Kaplan and Renato F Werneck. 2006. Reach for A*: Shortest Path Algorithms with Preprocessing. In The shortest path problem. 93-139. 10.1090/dimacs/074/05

[25]

10.1109/icde60146.2024.00345

[26]

10.1007/s41019-016-0030-0

[27]

10.1109/icde.2006.71

[28]

David E Kaufman and Robert L Smith. 1993. Fastest paths in time-dependent networks for intelligent vehicle-highway systems application. Journal of Intelligent Transportation Systems, Vol. 1, 1 (1993), 1-11.

[29]

10.1007/s10898-022-01269-2

[30]

10.1007/s00778-022-00758-w

[31]

10.1109/icde.2019.00085

[32]

Lei Li, Sibo Wang, and Xiaofang Zhou. 2020. Fastest path query answering using time-dependent hop-labeling in road network. IEEE Transactions on Knowledge and Data Engineering, Vol. 34, 1 (2020), 300-313.

[33]

10.1145/3299869.3319877

[34]

Xinling Li, Yishu Wang, Ye Yuan, Xiang Gu, and Guoren Wang. 2023b. Td-h2h: Shortest path query on time-dependent graphs. Journal of Frontiers of Computer Science and Technology, Vol. 17, 5 (2023), 1210-1224.

[35]

Linbo Liao, Shipeng Yang, Yongxuan Lai, Wenhua Zeng, Fan Yang, and Min Jiang. 2021. Efficient estimation of time-dependent shortest paths based on shortcuts. In International Conference on Algorithms and Architectures for Parallel Processing. Springer, 18-32.

[36]

10.1002/net.20438

[37]

10.1145/79147.214078

[38]

10.1145/3183713.3196913

[39]

10.1007/s00778-023-00789-x

[40]

10.1007/11561071_51

[41]

10.1109/icde.2017.115

[42]

10.1109/tkde.2017.2760880

[43]

10.1109/icde.2018.00255

[44]

10.1007/s41019-017-0044-2

[45]

10.14778/3342263.3342265

[46]

10.1109/icde51399.2021.00034

[47]

10.1109/icde.2019.00115

[48]

10.1145/2020408.2020462

[49]

10.1145/1869790.1869807

[50]

10.1145/2505515.2505749

Showing 50 of 51 references

Metrics

0

Citations

51

References

Details

Published: Dec 04, 2025
Vol/Issue: 3(6)
Pages: 1-25

Authors

W

Weihao Yu