QUBO-Based Simulated Annealing Approach for the Shortest Path Problem with Applications to Urban Transportation Networks

The shortest path problem remains a central challenge in graph optimization, particularly for dense or large-scale networks where classical algorithms face scalability limitations. This paper presents a QUBO-based Simulated Annealing (QUBO-SA) approach to compute the shortest path instances by employing an existing Quadratic Unconstrained Binary Optimization (QUBO) formulation that jointly encodes path costs and structural constraints. The approach is evaluated on both synthetic graphs, spanning sparse to dense connectivity regimes, and a real-world urban transportation network extracted from the downtown area of Querétaro, Mexico. The performance becomes quantified through probabilistic reliability metrics, including success probability, Time-to-Solution (TTS), and relative runtime ratio R(ptarget), benchmarked against the deterministic Dijkstra algorithm. Results show that QUBO-SA achieves near-optimal performance for small to medium graphs and maintains competitive efficiency for large-scale and sparse urban networks. In particular, the solver achieves a success probability of 0.57 with a workspace of 443 nodes corresponding to an urban graph, requiring only 35% more runtime than Dijkstra to reach 99% confidence, with this gap halved when relaxing the confidence to 90%. These results highlight the balance between the method’s exploration and computational complexity resources needed, which demonstrates its potential for scalable path optimization in both synthetic and real-world networks.