An Explainable Machine Learning Approach for Shortest Path Optimization in Urban Transportation Networks

Adriel Moses Anson

doi:10.70356/jafotik.v4i2.139

Authors

Adriel Moses Anson University of Cape Town, South Africa

DOI:

https://doi.org/10.70356/jafotik.v4i2.139

Keywords:

explainable artificial intelligence, machine learning, shortest path, urban transportation

Abstract

Urban transportation networks are characterized by complex spatial structures, dynamic traffic conditions, uncertain travel times, and heterogeneous road characteristics. Conventional shortest-path algorithms, such as Dijkstra's algorithm, generally optimize a predetermined edge cost and therefore may not adequately represent rapidly changing traffic conditions. This study proposes an explainable machine learning framework for shortest-path optimization in urban transportation networks by integrating traffic-time prediction, graph-based representation, shortest-path optimization, and explainable artificial intelligence. The transportation network is represented as a directed weighted graph (G=(V,E)), where vertices represent intersections and edges represent road segments. A machine learning model estimates the expected travel time of each road segment using traffic-related features, including historical speed, traffic volume, road length, congestion level, time of day, day of week, and weather-related variables. The predicted travel time is then incorporated into a dynamic edge-weight function and optimized using a shortest-path algorithm. To improve transparency, SHAP-based explanations are employed to quantify the contribution of each input feature to predicted travel time and, consequently, to route selection. The proposed framework is evaluated using conventional distance-based routing, static travel-time routing, machine-learning-based routing, and explainable machine-learning-based routing. Illustrative simulation results indicate that incorporating predicted traffic conditions can reduce estimated travel time compared with static shortest-path routing, while the XAI component provides a transparent interpretation of why particular road segments are selected or avoided. The proposed approach provides a mathematical and interpretable framework for intelligent urban route planning and can support transportation agencies in developing more adaptive, transparent, and trustworthy intelligent transportation systems.

Downloads

Download data is not yet available.

References

E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, vol. 1, pp. 269–271, 1959. doi: https://doi.org/10.1007/BF01386390

G. Gallo and S. Pallottino, “Improved shortest path algorithms for transport networks,” Transportation Research, vol. 12, no. 1, pp. 7–20, 1978. doi: https://doi.org/10.1016/0041-1647(78)90102-8

A. M. Falek, C. Pelsser, S. Julien, and F. Theoleyre, “MUSE: Multimodal separators for efficient route planning in transportation networks,” Transportation Science, 2022. doi: https://doi.org/10.1287/trsc.2021.1104

M. Schmidt et al., “Computing all shortest passenger routes with a tropical Dijkstra algorithm,” EURO Journal on Transportation and Logistics, vol. 14, Art. no. 100163, 2025. doi: https://doi.org/10.1016/j.ejtl.2025.100163

“Graph neural networks for travel distance estimation and route recommendation under probabilistic hazards,” International Journal of Transportation Science and Technology, vol. 21, pp. 372–383, 2026. doi: https://doi.org/10.1016/j.ijtst.2025.02.006

J. Xue, R. Tan, J. Ma, et al., “Data science in transportation networks with graph neural networks: A review and outlook,” Data Science for Transportation, vol. 7, Art. no. 10, 2025. doi: https://doi.org/10.1007/s42421-025-00124-6

“GROM: A generalized routing optimization method using graph neural network and deep reinforcement learning,” Journal of Network and Computer Applications, vol. 229, Art. no. 103927, 2024. doi: https://doi.org/10.1016/j.jnca.2024.103927

B. Yu, H. Yin, and Z. Zhu, “Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting,” in Proc. IJCAI, 2018, pp. 3634–3640. doi: https://doi.org/10.24963/ijcai.2018/505

Y. Li, R. Yu, C. Shahabi, and Y. Liu, “Diffusion convolutional recurrent neural network: Data-driven traffic forecasting,” in Proc. Int. Conf. Learn. Representations (ICLR), 2018. doi: https://doi.org/10.48550/arXiv.1707.01926

C. Song, Y. Lin, S. Guo, and H. Wan, “Spatial-temporal synchronous graph convolutional networks: A new framework for spatial-temporal network data forecasting,” in Proc. AAAI Conf. Artif. Intell., vol. 34, 2020, pp. 914–921. doi: https://doi.org/10.1609/aaai.v34i01.5438

K. Guo, Y. Hu, Z. Qian, H. Liu, K. Zhang, Y. Sun, J. Gao, and B. Yin, “Optimized graph convolution recurrent neural network for traffic prediction,” IEEE Transactions on Intelligent Transportation Systems, vol. 22, no. 2, pp. 1138–1149, 2021. doi: https://doi.org/10.1109/TITS.2019.2963722

M. Lu, H. Li, et al., “Urban traffic flow forecast based on FastGCRNN,” Journal of Advanced Transportation, 2020. doi: https://doi.org/10.1155/2020/8859538

L. Liu, Y. Cao, and Y. Dong, “Attention-based multiple graph convolutional recurrent network for traffic forecasting,” Sustainability, vol. 15, no. 6, Art. no. 4697, 2023. doi: https://doi.org/10.3390/su15064697

Z. Shi, Y. Zhang, J. Wang, et al., “DAGCRN: Graph convolutional recurrent network for traffic forecasting with dynamic adjacency matrix,” Expert Systems with Applications, vol. 227, Art. no. 120259, 2023. doi: https://doi.org/10.1016/j.eswa.2023.120259

C. Wang, K. Zhang, H. Wang, et al., “Auto-STGCN: Autonomous spatial-temporal graph convolutional network search,” ACM Transactions on Knowledge Discovery from Data, vol. 17, no. 5, Art. no. 73, 2023. doi: https://doi.org/10.1145/3571285.

I. Anwar, “The impact of intelligent agriculture on sustainability and food security,” Jurnal Sistem Informasi dan Teknik Informatika (JAFOTIK), vol. 4, no. 1, pp. 9–15, 2026. doi: https://doi.org/10.70356/jafotik.v4i1.98

A. Amirah, “Machine learning innovations in ophthalmology,” Jurnal Sistem Informasi dan Teknik Informatika (JAFOTIK), vol. 3, no. 1, pp. 7–12, 2025. doi: https://doi.org/10.70356/jafotik.v3i1.51

M. M. Maulana and A. Sanmorino, “A data-driven approach to dengue fever mapping: A review,” Jurnal Sistem Informasi dan Teknik Informatika (JAFOTIK), vol. 3, no. 1, pp. 25–30, 2025. doi: https://doi.org/10.70356/jafotik.v3i1.54

A. M. Anson and Amirah, “Machine learning-based route optimization for smart urban transportation systems,” Journal of Computer Science Application and Engineering (JOSAPEN), vol. 3, no. 2, pp. 31–36, 2025. doi: https://doi.org/10.70356/josapen.v3i2.65

A. Ahmad, “Optimizing the traveling salesman problem using machine learning and predictive algorithms,” Journal of Computer Science Application and Engineering (JOSAPEN), vol. 3, no. 1, pp. 1–5, 2025. doi: https://doi.org/10.70356/josapen.v3i1.46

Amirah, “Editorial: Smart parking management system using artificial intelligence,” Journal of Computer Science Application and Engineering (JOSAPEN), vol. 2, no. 1, pp. 20–23, 2024. doi: https://doi.org/10.70356/josapen.v2i1.25