Accelerating A* algorithm based search in time-dependent graphs with learned heuristics

Andrii Liashenko, Larysa Globa

Abstract


Finding the shortest path in busy urban transport networks represented as time-dependent graphs is a complex task that demands algorithms with low computational complexity. Static heuristics based on geometric distance do not account for traffic dynamics, which limits the effectiveness of the A* algorithm. The subject of the study is methods for increasing the efficiency of the A* search algorithm by creating heuristic functions based on machine learning. The goal of the work is to reduce the number of node explorations of the A* algorithm in a time-dependent graph by training the heuristic function. The research tasks are to conduct a comparative analysis of machine learning models that can be used as a heuristic function (LightGBM, GNN, TGNN); develop a hybrid method where TGNN predicts the future physical state of the system; and experimentally evaluate the efficiency gain. The main contribution is a hybrid approach where a Temporal Graph Neural Network (TGNN) predicts the future speed at neighboring nodes, which is then integrated into a classical geometric formula to compute an admissible and consistent heuristic. This resolves the contradiction between the high average accuracy of ML forecasts and the strict requirements for A* consistency. The models were evaluated based on three key criteria: admissibility, consistency, and search space reduction. The best model was selected as the one satisfying all criteria while achieving the greatest reduction in search space. The model was trained on real GPS data and tested on the road graph of the city of Irpin (2,400 nodes, 5,600 edges). The TGNN-based heuristic reduced the search space by 41.8% compared to Dijkstra and by 27.9% compared to the classical heuristic, with an average execution time of 0.44–0.65 ms per query and a 99.92–100% optimality rate across multiple routing scenarios. Conclusions. The scientific novelty lies in proving that reformulating the ML model’s task from predicting total travel time to predicting a physical parameter (speed) effectively resolves the contradiction between ML forecast accuracy and A* consistency requirements, enabling the creation of adaptive heuristic functions for time-dependent pathfinding.

Keywords


A* algorithm; time-dependent graph; machine learning; shortest path search; temporal graph neural networks TGNN

Full Text:

PDF

References


INRIX. INRIX Global Traffic Scorecard. INRIX, 2024. Available at: https://inrix.com/scorecard/#form-download-the-full-report (accessed 06 October 2025).

Hart, P. E., Nilsson, N. J., & Raphael, B. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 1968, vol. 4, no. 2, pp. 100–107. DOI: 10.1109/TSSC.1968.300136.

Werner, N., & Zeitz, T. Combining predicted and live traffic with time-dependent A potentials. Proc. European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), vol. 244. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, pp. 89:1–89:15. DOI: 10.4230/LIPIcs.ESA.2022.89.

Ron, D., Yusufzai, F. A., Kwayke, S., & Roy, S. Time-dependent network topology optimization for LEO satellite constellations. IEEE Conference on Aerospace and Electronic Systems, 2025. DOI: 10.48550/arXiv.2501.13280.

Zhang, Q., Shao, W., Shao, Z., & Pi, D. Graph-based reinforced multi-objective optimization for distributed heterogeneous flexible job shop scheduling problem under nonidentical time-of-use electricity pricing. Expert Systems with Applications, 2025. Available at: https://www.sciencedirect.com/science/article/abs/pii/S0957417425020470 (accessed 06 October 2025).

Maue, J., Sanders, P., & Matijevic, D. Goal-directed shortest-path queries using precomputed cluster distances. In: Experimental Algorithms: 5th International Workshop, WEA 2006. Lecture Notes in Computer Science, vol. 4007. Springer, Berlin, 2006, pp. 316–327. DOI: 10.1007/11764298_29. Available at: https://link.springer.com/chapter/10.1007/11764298_29 (accessed 06 October 2025).

Wu, F., & Wu, L. DeepETA: A spatial-temporal sequential neural network model for estimating time of arrival in package delivery system. In: Proc. 30th International Joint Conference on Artificial Intelligence (IJCAI-21), 2021, pp. 2822–2828. DOI: 10.24963/ijcai.2021/388.

Chen, H., Huang, J., Lu, Y., & Huang, J. Multi-scale spatio-temporal graph neural network for urban traffic flow prediction (STGMS). Scientific Reports, 2025, vol. 15, no. 1, article 26732. DOI: 10.1038/s41598-025-11072-0.

Xiao, Y., Wang, J., Ding, Z., & Zhao, L. Adaptive spatio-temporal dynamic graph convolutional network (AST-DGCN) for urban traffic forecasting. Scientific Reports, 2025, vol. 15, no. 1, article 12261. DOI: 10.1038/s41598-025-12261-7.

Cooke, K. L., & Halsey, E. The shortest route through a network with time-dependent internodal transit times. Journal of Mathematical Analysis and Applications, 1966, vol. 14, no. 3, pp. 493–498. DOI: 10.1016/0022-247X(66)90009-6.

Orda, A., & Rom, R. Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length. Journal of the ACM, 1990, vol. 37, no. 3, pp. 607–625. DOI: 10.1145/79147.214078.

Dreyfus, S. E. An appraisal of some shortest-path algorithms. Operations Research, 1969, vol. 17, no. 3, pp. 395–412. DOI: 10.1287/opre.17.3.395.

Zhao, L., Song, Y., Zhang, C., Liu, Y., Wang, P., Lin, T., & Deng, M. T-GCN: A temporal graph convolutional network for traffic prediction. IEEE Transactions on Intelligent Transportation Systems, 2019. DOI: 10.1109/TITS.2019.2935152.

Haklay, M., & Weber, P. OpenStreetMap: User-generated street maps. IEEE Pervasive Computing, 2008, vol. 7, no. 4, pp. 12–18. DOI: 10.1109/MPRV.2008.80.

Boeing, G. OSMnx: New methods for acquiring, constructing, analyzing, and visualizing complex street networks. Computers, Environment and Urban Systems, 2017, vol. 65, pp. 126–139. DOI: 10.1016/j.compenvurbsys.2017.05.004.

Ke, G., Meng, Q., Finley, T., Wang, T., Chen, W., Ma, W., Ye, Q., & Liu, T.-Y. LightGBM: A highly efficient gradient boosting decision tree. In: Advances in Neural Information Processing Systems 30 (NIPS 2017), pp. 3146–3154. Available at: https://proceedings.neurips.cc/paper/2017/hash/6449f44a102fde848669bdd9eb6b76fa-Abstract.html (accessed 06 October 2025).

Wu, Z., & et al. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2020, vol. 32, no. 1, pp. 4–24.

Xu, D., Ruan, C., Korpeoglu, E., Kumar, S., & Achan, K. Temporal graph networks for deep learning on dynamic graphs. arXiv preprint, arXiv:2006.10637, 2020. DOI: 10.48550/arXiv.2006.10637.

Kipf, T. N., & Welling, M. Semi-supervised classification with graph convolutional networks. arXiv preprint, arXiv:1609.02907, 2016. DOI: 10.48550/arXiv.1609.02907.

Hamilton, W. L., Ying, R., & Leskovec, J. Inductive representation learning on large graphs. In: Advances in Neural Information Processing Systems 30 (NeurIPS 2017), pp. 1024–1034. Available at: https://papers.nips.cc/paper/2017/hash/5dd9db5e033da9c6fb5ba83c7a7ebea9-Abstract.html (accessed 06 October 2025).

Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., & Bengio, Y. Graph attention networks. ICLR 2018. DOI: 10.48550/arXiv.1710.10903.

Seo, Y., Defferrard, M., Vandergheynst, P., & Bresson, X. Structured sequence modeling with graph convolutional recurrent networks. In: Neural Information Processing (ICONIP 2018). Lecture Notes in Computer Science, vol. 11301. Springer, 2018, pp. 362–373. DOI: 10.1007/978-3-030-04167-0_33.

Cho, K., van Merriënboer, B., Gulcehre, C., Bahdanau, D., Bougares, F., Schwenk, H., & Bengio, Y. Learning phrase representations using RNN encoder–decoder for statistical machine translation. arXiv preprint, arXiv:1406.1078, 2014. DOI: 10.48550/arXiv.1406.1078.

Oono, K., & Suzuki, T. Graph neural networks exponentially lose expressive power for node classification. In: International Conference on Learning Representations (ICLR 2020). DOI: 10.48550/arXiv.1905.10947.

Liu, Z., Shojaee, P., & Reddy, C. K. Graph-based multi-ODE neural networks for spatio-temporal traffic forecasting (GRAM-ODE). arXiv preprint, arXiv:2305.18687, 2023. DOI: 10.48550/arXiv.2305.18687.

Liu, Y., & Meidani, H. Fast graph neural network approximations for shortest distances and route estimation under uncertainty. arXiv preprint, arXiv:2501.09803, 2025. DOI: 10.48550/arXiv.2501.09803.

Francies, R., Zhu, K., & Tan, C. Continual learning-enhanced spatio-temporal graph neural networks for dynamic traffic forecasting. Complex & Intelligent Systems, 2025, vol. 11, article 20497. DOI: 10.1007/s40747-025-02049-7.




DOI: https://doi.org/10.32620/reks.2026.1.12

Refbacks

  • There are currently no refbacks.