{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T09:13:30Z","timestamp":1778836410478,"version":"3.51.4"},"reference-count":41,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T00:00:00Z","timestamp":1777680000000},"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>The shortest path problem presents formidable challenges in graph optimization, particularly within dense or large-scale networks, where traditional algorithms face serious scalability limitations. This paper puts forth a robust QUBO-based simulated annealing (QUBO-SA) methodology that effectively utilizes a Quadratic Unconstrained Binary Optimization (QUBO) framework to encode path costs and structural constraints simultaneously. Our approach has been rigorously evaluated on synthetic graphs with controlled connectivity, varying from n=10 to n=40, and on a real-world urban transportation network from Quer\u00e9taro, Mexico, comprising n=443 nodes. We assess performance through rigorous probabilistic reliability indicators, notably the success probability psuccess, Time-to-Solution, and the relative runtime ratio R(ptarget), benchmarked against Dijkstra\u2019s algorithm. In small synthetic instances (n=10), the QUBO-SA method demonstrates outstanding success rates (psuccess\u22650.97) with runtimes on par with the deterministic baseline (R0.99\u22481). However, as the problem size increases, success probabilities diminish while computational overhead rises, with R0.99 soaring from approximately 1.0 at n=10 to between 4.63 and 5.83 at n=40. For the urban network, our solver achieves success probabilities between 0.49 and 0.91, depending on the specified path length, with R0.99 values ranging from 2.17 to 9.41. Notably, reducing the target confidence level from 99% to 90% cuts runtime overhead by approximately fifty percent across all configurations. Although the QUBO formulation demonstrates scalability in relation to n+m, potentially limiting its use in dense graphs, the sparse structure typical of real-world road networks enables competitive performance in moderately large instances. These findings decisively highlight the trade-off between solution reliability and computational efficiency, pinpointing specific problem regimes where QUBO-based optimization methods are not only viable but advantageous for path-optimization tasks.<\/jats:p>","DOI":"10.3390\/a19050352","type":"journal-article","created":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T01:12:09Z","timestamp":1777857129000},"page":"352","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A QUBO-Driven Simulated Annealing Methodology for Solving the Shortest Path Problem in Urban Transportation Networks"],"prefix":"10.3390","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-2174-8861","authenticated-orcid":false,"given":"Isaac","family":"Oliva-Gonz\u00e1lez","sequence":"first","affiliation":[{"name":"Facultad de Inform\u00e1tica, Universidad Aut\u00f3noma de Quer\u00e9taro, Av. de las Ciencias S\/N, Juriquilla, Santiago de Quer\u00e9taro 76230, Mexico"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0827-6645","authenticated-orcid":false,"given":"Hugo","family":"Jim\u00e9nez-Hern\u00e1ndez","sequence":"additional","affiliation":[{"name":"Facultad de Inform\u00e1tica, Universidad Aut\u00f3noma de Quer\u00e9taro, Av. de las Ciencias S\/N, Juriquilla, Santiago de Quer\u00e9taro 76230, Mexico"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2026,5,2]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"121130","DOI":"10.1016\/j.jclepro.2020.121130","article-title":"The constrained reliable shortest path problem for electric vehicles in the urban transportation network","volume":"261","author":"Tu","year":"2020","journal-title":"J. Clean. Prod."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Koritsoglou, K., Tsoumanis, G., Patras, V., and Fudos, I. (2022). Shortest Path Algorithms for Pedestrian Navigation Systems. Information, 13.","DOI":"10.3390\/info13060269"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Geisberger, R., Sanders, P., Schultes, D., and Delling, D. (2008). Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks. Experimental Algorithms, Springer.","DOI":"10.1007\/978-3-540-68552-4_24"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/978-3-319-49487-6_2","article-title":"Route Planning in Transportation Networks","volume":"Volume 9220","author":"Bast","year":"2016","journal-title":"Algorithm Engineering; Lecture Notes in Computer Science"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Luxen, D., and Vetter, C. (2011). Real-Time Routing with OpenStreetMap Data. Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM.","DOI":"10.1145\/2093973.2094062"},{"key":"ref_6","first-page":"3101512","article-title":"Solving the network shortest path problem on a quantum annealer","volume":"1","author":"Krause","year":"2020","journal-title":"IEEE Trans. Quantum Eng."},{"key":"ref_7","unstructured":"Weso\u0142owski, A., and Piddock, S. (2024). Advances in quantum algorithms for the shortest path problem. arXiv."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"608","DOI":"10.1287\/ijoc.2017.0798","article-title":"What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO","volume":"30","author":"Dunning","year":"2018","journal-title":"INFORMS J. Comput."},{"key":"ref_9","unstructured":"D-Wave Systems Inc. (2026, March 19). Ocean Software Development Kit. Available online: https:\/\/docs.ocean.dwavesys.com."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by simulated annealing","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Science"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1090\/qam\/102435","article-title":"On a routing problem","volume":"16","author":"Bellman","year":"1958","journal-title":"Q. Appl. Math."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Punnen, A.P. (2022). The Quadratic Unconstrained Binary Optimization Problem, Springer International Publishing.","DOI":"10.1007\/978-3-031-04520-2"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Quintero, R.A., and Zuluaga, L.F. (2022). QUBO Formulations of Combinatorial Optimization Problems for Quantum Computing Devices. Encyclopedia of Optimization, Springer.","DOI":"10.1007\/978-3-030-54621-2_853-1"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Lucas, A. (2014). Ising formulations of many NP problems. Front. Phys., 2.","DOI":"10.3389\/fphy.2014.00005"},{"key":"ref_15","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2022). Introduction to Algorithms, MIT Press."},{"key":"ref_16","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_17","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/0305-0548(81)90015-0","article-title":"A computational study of Floyd\u2019s algorithm","volume":"8","author":"Shier","year":"1981","journal-title":"Comput. Oper. Res."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","article-title":"Fibonacci heaps and their uses in improved network optimization algorithms","volume":"34","author":"Fredman","year":"1987","journal-title":"J. ACM (JACM)"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1343","DOI":"10.1145\/50087.50096","article-title":"Relaxed heaps: An alternative to Fibonacci heaps with applications to parallel computation","volume":"31","author":"Driscoll","year":"1988","journal-title":"Commun. ACM"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Salzman, O., Felner, A., Zhang, H., Chan, S.H., and Koenig, S. (2023, January 19\u201325). Heuristic-Search Approaches for the Multi-Objective Shortest-Path Problem: Progress and Research Opportunities [Survey Track]. Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), Macao, China.","DOI":"10.24963\/ijcai.2023\/757"},{"key":"ref_21","first-page":"28","article-title":"Implementation of the A Star Heuristic Search Algorithm in Determining the Shortest Path","volume":"2","author":"Marlina","year":"2023","journal-title":"Int. J. Comput. Sci. Math. Eng."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"3016","DOI":"10.1109\/JLT.2024.3519778","article-title":"Improved ILP Models and Heuristics for Solving Routing and Resource Allocation Problems in Optical Networks","volume":"43","author":"Zheng","year":"2024","journal-title":"J. Light. Technol."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Hara, T., and Sasabe, M. (2022, January 25\u201329). Lagrangian Heuristics for Capacitated Shortest Path Tour Problem Based Online Service Chaining. Proceedings of the NOMS, Budapest, Hungary.","DOI":"10.1109\/NOMS54207.2022.9789758"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"4378","DOI":"10.1016\/j.jfranklin.2023.01.033","article-title":"Dynamic path planning of mobile robot based on improved simulated annealing algorithm","volume":"360","author":"Shi","year":"2023","journal-title":"J. Frankl. Inst."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"012086","DOI":"10.1088\/1742-6596\/1972\/1\/012086","article-title":"Research on picking route optimization based on simulated annealing algorithm","volume":"1972","author":"Zhang","year":"2021","journal-title":"J. Phys. Conf. Ser."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1091","DOI":"10.70003\/160792642024122507013","article-title":"Application of improved genetic algorithms in path planning","volume":"25","author":"Chen","year":"2024","journal-title":"J. Internet Technol."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1016\/j.procs.2018.01.113","article-title":"Genetic algorithm based approach for autonomous mobile robot path planning","volume":"127","author":"Lamini","year":"2018","journal-title":"Procedia Comput. Sci."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"77","DOI":"10.5957\/JOSR.10230029","article-title":"A Review of Improved Methods for Ant Colony Optimization in Path Planning","volume":"68","author":"Bai","year":"2024","journal-title":"J. Ship Res."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Cheng, Q., Zhang, Z., Du, Y., and Li, Y. (2024). Research on Particle Swarm Optimization-Based UAV Path Planning Technology in Urban Airspace. Drones, 8.","DOI":"10.3390\/drones8120701"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Rosas-Carrillo, A.S., Sol\u00eds-Santom\u00e9, A., Silva-S\u00e1nchez, C., and Camacho-Nieto, O. (2025). UAV Path Planning Using an Adaptive Strategy for the Particle Swarm Optimization Algorithm. Drones, 9.","DOI":"10.3390\/drones9030170"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Jmaa, Y.B., and Duvivier, D. (2023). A review of path planning algorithms. Intelligent Systems Design and Applications, Springer.","DOI":"10.1007\/978-3-031-64850-2_11"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/s00607-022-01126-w","article-title":"Algorithms for path optimizations: A short survey","volume":"105","author":"Fernando","year":"2023","journal-title":"Computing"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1007\/s11128-025-04870-y","article-title":"Review of the application of quantum annealing-related technologies in transportation optimization","volume":"24","author":"Mohammed","year":"2025","journal-title":"Quantum Inf. Process."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"2350002","DOI":"10.1142\/S2010324723500029","article-title":"Solving the shortest path problem with qaoa","volume":"13","author":"Fan","year":"2023","journal-title":"Spin"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0167-6377(92)90043-3","article-title":"Complexity of uniqueness and local search in quadratic 0\u20131 programming","volume":"11","author":"Pardalos","year":"1992","journal-title":"Oper. Res. Lett."},{"key":"ref_36","unstructured":"Karp, R.M. (2010). Reducibility Among Combinatorial Problems, Springer."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1063\/1.1699114","article-title":"Equation of state calculations by fast computing machines","volume":"21","author":"Metropolis","year":"1953","journal-title":"J. Chem. Phys."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1038\/s42254-022-00440-8","article-title":"Ising machines as hardware solvers of combinatorial optimization problems","volume":"4","author":"Mohseni","year":"2022","journal-title":"Nat. Rev. Phys."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Aramon, M., Rosenberg, G., Valiante, E., Miyazawa, T., Tamura, H., and Katzgraber, H.G. (2019). Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer. Front. Phys., 7.","DOI":"10.3389\/fphy.2019.00048"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1126\/science.1252319","article-title":"Defining and detecting quantum speedup","volume":"345","author":"Wang","year":"2014","journal-title":"Science"},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Zielewski, M.R., and Takizawa, H. (2022, January 12\u201314). A method for reducing time-to-solution in quantum annealing through pausing. Proceedings of the International Conference on High Performance Computing in Asia-Pacific Region, Virtual Event.","DOI":"10.1145\/3492805.3492815"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/19\/5\/352\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T08:55:59Z","timestamp":1778835359000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/19\/5\/352"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,2]]},"references-count":41,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2026,5]]}},"alternative-id":["a19050352"],"URL":"https:\/\/doi.org\/10.3390\/a19050352","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,2]]}}}