Quantum-Inspired Optimization for Traffic Congestion: A QUBO-Based Approach with Simulated Annealing

Abstract

Urban traffic congestion remains a persistent challenge, especially when road segments exceed vehicle capacity, leading to increased travel times and road density. This study introduces a new QUBO framework designed to dynamically reduce congestion by optimizing vehicle routes while considering the capacity constraints of road segments. The proposed model establishes quadratic penalties for road segments that exceed the set capacity thresholds, providing incentives to redistribute vehicles to alternative routes while maintaining overall traffic flow efficiency. The QUBO formulation also incorporates road density as a factor to distribute vehicle routing more evenly. The challenge is to ensure that the chosen route does not create potential congestion on the next road segment. We conducted the simulation on a road network consisting of 15 segments (edges) to effectively manage up to 21 vehicles in dense traffic. This QUBO model was created using a quantum annealing approach, but its execution was carried out on an annealing simulation with the Fixstars Amplify and D-Wave Neal machines. The results indicate that the proposed QUBO congestion model can maintain road segment density between 60% and 80% across almost all segment routes. The QUBO congestion model is capable of distributing vehicles evenly, with a Gini coefficient reaching 0.0496 (in an experiment with 21 vehicles), which has the potential to reduce vehicle congestion on road segments. In addition, this model is also capable of avoiding segment choices that exceed road capacity, which is expected to reduce vehicle congestion. Therefore, the resulting QUBO model can be applied to QA engines to reduce congestion on road segments.