{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T17:02:56Z","timestamp":1773162176144,"version":"3.50.1"},"reference-count":56,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2025,10,23]],"date-time":"2025-10-23T00:00:00Z","timestamp":1761177600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>With the accelerating pace of urbanization and the increasing complexity of traffic systems, urban transportation faces growing challenges such as congestion, inefficiency, and environmental strain. Path planning algorithms\u2014key components in intelligent transportation systems\u2014have evolved from classical graph-based methods like Dijkstra and A* to modern approaches leveraging metaheuristics and deep learning. This paper systematically reviews the development of urban path planning algorithms, tracing their progression from foundational methods to state-of-the-art techniques such as Ant Colony Optimization, Probabilistic Roadmaps, and Rapidly Exploring Random Trees. Recent innovations, including improved genetic algorithms, hybrid A* variants, and reinforcement learning models, are analyzed in terms of adaptability, efficiency, and real-time performance. Furthermore, the review highlights ongoing challenges in scalability, dynamic adaptation, and algorithmic fairness, while discussing future directions that integrate technical innovation with policy and ethical considerations to support sustainable and equitable urban mobility.<\/jats:p>","DOI":"10.3390\/a18110676","type":"journal-article","created":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T01:35:11Z","timestamp":1761269711000},"page":"676","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Review of Urban Path Planning Algorithms in Intelligent Transportation Systems"],"prefix":"10.3390","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-5472-2627","authenticated-orcid":false,"given":"Zhenyu","family":"Tian","sequence":"first","affiliation":[{"name":"College of Design and Engineering, National University of Singapore, Singapore 119077, Singapore"}]},{"given":"Huaqi","family":"Yao","sequence":"additional","affiliation":[{"name":"Zhejiang Institute of Mechanical & Electrical Engineering Co., Ltd., Hangzhou 310051, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2435-5618","authenticated-orcid":false,"given":"Yu","family":"Shao","sequence":"additional","affiliation":[{"name":"College of Civil Engineering and Architecture, Zhejiang University, Hangzhou 310058, China"}]}],"member":"1968","published-online":{"date-parts":[[2025,10,23]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3737280","article-title":"Comprehensive review of path planning techniques for unmanned aerial vehicles (uavs)","volume":"58","author":"Kumar","year":"2025","journal-title":"ACM Comput. Surv."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"104612","DOI":"10.1016\/j.robot.2024.104630","article-title":"Path Planning Algorithms in the Autonomous Driving System: Challenges and Recent Advances","volume":"174","author":"Reda","year":"2024","journal-title":"Robot. Auton. Syst."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Hu, J., Zhao, Y., Wang, Q., and Li, X. (2025). A Survey of Decision-Making and Planning Methods for Self-Driving Vehicles: Bridging Knowledge-Driven and Data-Driven Paradigms. Front. Neurorobot., 19.","DOI":"10.3389\/fnbot.2025.1451923"},{"key":"ref_4","first-page":"65","article-title":"Shortest Path Algorithms: An Evaluation Using Real Road Networks","volume":"32","author":"Zhan","year":"1998","journal-title":"Transp. Sci. Inst. Oper. Res. Manag. Sci. (INFORMS)"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A Note on Two Problems in Connexion with Graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"ref_6","first-page":"208","article-title":"An Efficient Implementation of Dijkstra\u2019s Shortest Path Algorithm","volume":"24","author":"Le","year":"1999","journal-title":"J. Wuhan Tech. Univ. Surv. Mapp."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Yang, L., Li, P., Qian, S., Quan, H., Miao, J., Liu, M., Hu, Y., and Memetimin, E. (2023). Path Planning Technique for Mobile Robots: A Review. Machines, 11.","DOI":"10.3390\/machines11100980"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Makariye, N. (2017, January 19\u201320). Towards Shortest Path Computation Using Dijkstra Algorithm. Proceedings of the 2017 International Conference on IoT and Application (ICIOT), Nagapattinam, India.","DOI":"10.1109\/ICIOTA.2017.8073641"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Verma, D., Messon, D., Rastogi, M., and Singh, A. (2021, January 19\u201320). Comparative Study Of Various Approaches Of Dijkstra Algorithm. Proceedings of the 2021 International Conference on Computing, Communication, and Intelligent Systems (ICCCIS), Greater Noida, India.","DOI":"10.1109\/ICCCIS51004.2021.9397200"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/367766.368168","article-title":"Algorithm 97: Shortest Path","volume":"5","author":"Floyd","year":"1962","journal-title":"Commun. ACM"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/321105.321107","article-title":"A Theorem on Boolean Matrices","volume":"9","author":"Warshall","year":"1962","journal-title":"J. ACM"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Azis, H., Mallongi, R.d., Lantara, D., and Salim, Y. (2018, January 6\u20137). Comparison of Floyd-Warshall Algorithm and Greedy Algorithm in Determining the Shortest Route. Proceedings of the 2018 2nd East Indonesia Conference on Computer and Information Technology (EIConCIT), Makassar, Indonesia.","DOI":"10.1109\/EIConCIT.2018.8878582"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"012019","DOI":"10.1088\/1755-1315\/144\/1\/012019","article-title":"Floyd-Warshall Algorithm to Determine the Shortest Path Based on Android","volume":"144","author":"Ramadiani","year":"2018","journal-title":"IOP Conf. Ser. Earth Environ. Sci."},{"key":"ref_14","first-page":"99","article-title":"A Review and Evaluations of Shortest Path Algorithms","volume":"2","author":"Magzhan","year":"2012","journal-title":"Int. J. Sci. Technol. Res."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Risald, A.E. (2017, January 31). Mirino and Suyoto, Best Routes Selection using Dijkstra and Floyd-Warshall Algorithm. Proceedings of the 2017 11th International Conference on Information & Communication Technology and System (ICTS), Surabaya, Indonesia.","DOI":"10.1109\/ICTS.2017.8265662"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Khan, P., Konar, G., and Chakraborty, N. (2014, January 11\u201313). Modification of Floyd-Warshall\u2019s Algorithm for Shortest Path Routing in Wireless Sensor Networks. Proceedings of the 2014 Annual IEEE India Conference (INDICON), Pune, India.","DOI":"10.1109\/INDICON.2014.7030504"},{"key":"ref_17","first-page":"012116","article-title":"The shortest path search application based on the city transport route in Semarang using the Floyd-warshall algorithm","volume":"Volume 1217","author":"Khamami","year":"2019","journal-title":"Journal of Physics: Conference Series"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","article-title":"A Formal Basis for the Heuristic Determination of Minimum Cost Paths","volume":"4","author":"Hart","year":"1968","journal-title":"IEEE Trans. Syst. Sci. Cybern."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"75","DOI":"10.14257\/ijsh.2014.8.3.07","article-title":"A multiple mobile robots path planning algorithm based on A-star and Dijkstra algorithm","volume":"8","author":"Zhang","year":"2014","journal-title":"Int. J. Smart Home"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/j.proeng.2014.12.098","article-title":"Path Planning with Modified A Star Algorithm for a Mobile Robot","volume":"96","author":"Babinec","year":"2014","journal-title":"Procedia Eng."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1016\/j.plrev.2005.10.001","article-title":"Ant Colony Optimization: Introduction and Recent trends","volume":"2","author":"Blum","year":"2005","journal-title":"Phys. Life Rev."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Pei, Y., Wang, W., and Zhang, S. (2012, January 23\u201325). Basic Ant Colony Optimization. Proceedings of the 2012 International Conference on Computer Science and Electronics Engineering, Hangzhou, China.","DOI":"10.1109\/ICCSEE.2012.178"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"4618","DOI":"10.1016\/j.eswa.2011.09.076","article-title":"A Survey: Ant Colony Optimization Based Recent Research and Implementation on Several Engineering Domain","volume":"39","author":"Mohan","year":"2012","journal-title":"Expert Syst. Appl."},{"key":"ref_24","unstructured":"Gendreau, M., and Potvin, J.Y. (2019). Ant Colony Optimization: Overview and Recent Advances. Handbook of Metaheuristics, Springer. International Series in Operations Research & Management Science."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1109\/70.508439","article-title":"Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces","volume":"12","author":"Kavraki","year":"1996","journal-title":"IEEE Trans. Robot. Autom."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Boissonnat, J.D., Burdick, J., Goldberg, K., and Hutchinson, S. (2004). A Comparative Study of Probabilistic Roadmap Planners. Algorithmic Foundations of Robotics V, Springer. Springer Tracts in Advanced Robotics.","DOI":"10.1007\/b80173"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1555","DOI":"10.1007\/s00521-019-04172-2","article-title":"Research on Path Planning of Mobile Robot Based on Improved Ant Colony Algorithm","volume":"32","author":"Luo","year":"2020","journal-title":"Neural Comput. Appl."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1109\/70.660866","article-title":"Analysis of Probabilistic Roadmaps for Path Planning","volume":"14","author":"Kavraki","year":"1998","journal-title":"IEEE Trans. Robot. Autom."},{"key":"ref_29","unstructured":"LaValle, S.M. (1998). Rapidly Exploring Random Trees: A New Tool for Path Planning, Computer Science Department, Iowa State University. In Technical Report."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"50933","DOI":"10.1109\/ACCESS.2019.2908100","article-title":"Systematic Literature Review of Sampling Process in Rapidly-Exploring Random Trees","volume":"7","author":"Medeiros","year":"2019","journal-title":"IEEE Access"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"e32451","DOI":"10.1016\/j.heliyon.2024.e32451","article-title":"Recent Advances in Rapidly-Exploring Random Tree: A Review","volume":"10","author":"Tong","year":"2024","journal-title":"Heliyon"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Umari, H., and Mukhopadhyay, S. (2017, January 24\u201328). Autonomous Robotic Exploration Based on Multiple Rapidly-Exploring Randomized Trees. Proceedings of the 2017 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), Vancouver, BC, Canada.","DOI":"10.1109\/IROS.2017.8202319"},{"key":"ref_33","unstructured":"Nam, T., Sun, S.H., Pertsch, K., Su, Y., Gao, J., Zhang, H., Wang, Y., and Chau, L.P. (2023, January 18\u201322). SignEye: Traffic-Sign Interpretation from Vehicle First-Person View. Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition (CVPR), Vancouver, BC, Canada."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"805","DOI":"10.1007\/s11263-023-01912-9","article-title":"SignParser: An end-to-end framework for traffic sign understanding","volume":"132","author":"Guo","year":"2024","journal-title":"Int. J. Comput. Vis."},{"key":"ref_35","unstructured":"Ajay, A., Han, S., Du, Y., Ma, H., Han, X., Han, T., Guo, C., Han, H., Zhao, B., and Wang, Q. (2023, January 10\u201316). Traffic Sign Interpretation via Natural Language Description. Proceedings of the Advances in Neural Information Processing Systems (NeurIPS), New Orleans, LA, USA."},{"key":"ref_36","first-page":"2316","article-title":"A Method for the Shortest Path Search by Extended Dijkstra Algorithm","volume":"Volume 3","author":"Noto","year":"2000","journal-title":"SMC 2000 Conference Proceedings, Proceedings of the 2000 IEEE International Conference on Systems, Man and Cybernetics. \u2018Cybernetics Evolving to Systems, Humans, Organizations, and Their Complex Interactions\u2019, Nashville, TN, USA, 8\u201311 October 2000"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"106131","DOI":"10.1016\/j.oceaneng.2019.106131","article-title":"Leif Eriksson, A Three-Dimensional Dijkstra\u2019s algorithm for multi-objective ship voyage optimization","volume":"186","author":"Wang","year":"2019","journal-title":"Ocean Eng."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Duan, R., Mao, J., Shu, X., and Yin, L. (2023, January 6\u20139). A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs. Proceedings of the 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, Santa Cruz, CA, USA.","DOI":"10.1109\/FOCS57990.2023.00035"},{"key":"ref_39","first-page":"17","article-title":"Shortest Path of Urban Traffic Based on the Improved Floyd Algorithm","volume":"30","author":"Xu","year":"2017","journal-title":"Electron. Sci. Technol."},{"key":"ref_40","first-page":"703","article-title":"Path Planning for Mobile Robots Based on Improved Genetic Algorithm","volume":"46","author":"Wei","year":"2020","journal-title":"J. Beihang Univ."},{"key":"ref_41","first-page":"372","article-title":"Research on Local Path Planning and Tracking Algorithms for Intelligent Vehicles in Complex Dynamic Environments","volume":"35","author":"Zhang","year":"2022","journal-title":"China J. Highw. Transp."},{"key":"ref_42","first-page":"44","article-title":"Research Progress on Deep Reinforcement Learning and Its Application in Path Planning","volume":"57","author":"Zhang","year":"2021","journal-title":"Comput. Eng. Appl."},{"key":"ref_43","unstructured":"Xie, S., Zheng, H., Liu, C., and Lin, L. (2018). SNAS: Stochastic neural architecture search. arXiv."},{"key":"ref_44","unstructured":"Zheng, Z., Bewley, T., Kuester, F., and Ma, J. (2022). BTO-RRT: A Rapid, Optimal, Smooth and Point Cloud-Based Path Planning Algorithm. arXiv."},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Bonetti, A., Guidetti, S., and Sabattini, L. (2023). Improved Path Planning Algorithms for Non-Holonomic Autonomous Vehicles in Industrial Environments with Narrow Corridors: Roadmap Hybrid A* and Waypoints Hybrid A*. arXiv.","DOI":"10.1109\/ECMR59166.2023.10256368"},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Diab, M., Mohammadkarimi, M., and Rajan, R.T. (2023). Artificial Potential Field-Based Path Planning for Cluttered Environments. arXiv.","DOI":"10.1109\/AERO55745.2023.10115857"},{"key":"ref_47","unstructured":"Clawson, Z., Ding, X., Englot, B., Frewen, T., Sisson, W., and Vladimirsky, A. (2015, January 19\u201325). A Bi-Criteria Path Planning Algorithm for Robotics Applications. Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), Hangzhou, China."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"012061","DOI":"10.1088\/1742-6596\/1566\/1\/012061","article-title":"Analysis of Dijkstra\u2019s algorithm and A* algorithm in shortest path problem","volume":"1566","author":"Rachmawati","year":"2020","journal-title":"J. Phys. Conf. Ser."},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"AbuJabal, N., Baziyad, M., Fareh, R., Brahmi, B., Rabie, T., and Bettayeb, M. (2024). A Comprehensive Study of Recent Path-Planning Techniques in Dynamic Environments for Autonomous Robots. Sensors, 24.","DOI":"10.3390\/s24248089"},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Ugwoke, K.C., Nnanna, N.A., and Abdullahi, S.E.Y. (2025). Simulation-based review of classical, heuristic, and metaheuristic path planning algorithms. Sci. Rep., 15.","DOI":"10.1038\/s41598-025-96614-2"},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"Hsueh, H.Y. (2022). Systematic Comparison of Path Planning Algorithms using Path Bench. arXiv.","DOI":"10.1080\/01691864.2022.2062259"},{"key":"ref_52","doi-asserted-by":"crossref","unstructured":"Qin, H., Shao, S., Wang, T., Yu, X., Jiang, Y., and Cao, Z. (2023). Review of Autonomous Path Planning Algorithms for Mobile Robots. Drones, 7.","DOI":"10.3390\/drones7030211"},{"key":"ref_53","unstructured":"Cohen, A., Martens, K., and Golub, A. (2022). Algorithmic equity in transport systems. Transp. Res. Part A Policy Pract."},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"575","DOI":"10.4236\/cus.2022.104034","article-title":"Transportation Equity Quantification and Related Issues and Challenges","volume":"10","author":"Faghri","year":"2022","journal-title":"Curr. Urban Stud."},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1038\/s42949-024-00168-7","article-title":"Towards a public policy of cities and human settlements in the 21st century","volume":"4","author":"Creutzig","year":"2024","journal-title":"npj Urban Sustain."},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"128423","DOI":"10.1016\/j.neucom.2024.128423","article-title":"Recent Progress, Challenges and Future Prospects of Applied Deep Reinforcement Learning: A Practical Perspective in Path Planning","volume":"608","author":"Zhang","year":"2024","journal-title":"Neurocomputing"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/11\/676\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T01:43:47Z","timestamp":1761270227000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/11\/676"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,23]]},"references-count":56,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2025,11]]}},"alternative-id":["a18110676"],"URL":"https:\/\/doi.org\/10.3390\/a18110676","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,23]]}}}