A QUBO-Driven Simulated Annealing Methodology for Solving the Shortest Path Problem in Urban Transportation Networks

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étaro, 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’s algorithm. In small synthetic instances (n=10), the QUBO-SA method demonstrates outstanding success rates (psuccess≥0.97) with runtimes on par with the deterministic baseline (R0.99≈1). 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.