⚛️ quantum physics

Quantum Annealing for Realistic Traffic Flow Optimization: Clustering and Data-Driven QUBO

This paper presents a scalable, data-driven framework for city-wide traffic flow optimization that combines Leiden clustering with a Quadratic Unconstrained Binary Optimization (QUBO) formulation to effectively solve large-scale problems on realistic urban networks using hybrid quantum annealing, achieving near-optimal congestion reductions comparable to classical solvers while significantly outperforming traditional shortest-route baselines.

Original authors: Renáta Rusnáková, Martin Chovanec, Juraj Gazda

Published 2026-06-30

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Renáta Rusnáková, Martin Chovanec, Juraj Gazda

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a city as a giant, living puzzle where every car is a piece trying to find its way home. Usually, everyone just picks the fastest path they see on their GPS. But when thousands of people do this at the same time, they all end up clogging the same few streets, turning a smooth flow into a gridlocked jam.

This paper presents a new way to solve that puzzle using a special kind of "super-brain" called a Quantum Annealer (specifically, a machine made by D-Wave). Here is how they did it, explained simply:

1. The Problem: The "Too Many Cooks" Dilemma

The researchers wanted to optimize traffic for a whole city (up to 25,000 cars at once). The challenge is that if you try to calculate the best route for every single car simultaneously, the number of possible combinations is so huge it would break a normal computer. It's like trying to solve a Rubik's Cube where the number of squares keeps doubling every second.

2. The Solution: Turning Traffic into a Game

The team turned the traffic problem into a math game called a QUBO (Quadratic Unconstrained Binary Optimization).

The Goal: Minimize "congestion cost." Think of this as a score where cars get points for being too close to each other (like bumper-to-bumper traffic) or taking a route that is way too long.
The Rules: Every car must pick exactly one route from a few options provided by a standard map engine.
The Penalty: They added a rule that says, "Don't pick a route that is 30 minutes longer just to avoid a tiny traffic light." This keeps the solution realistic for drivers.

3. The Trick: Breaking the Puzzle into Pieces

Because the puzzle was too big for the quantum computer to solve in one go, the researchers used a clever trick called Leiden Clustering.

The Analogy: Imagine a massive crowd of people at a concert. Instead of trying to organize the whole crowd at once, you group people into smaller, tight-knit circles based on who they are standing near.
How it worked: They grouped cars that were likely to interact (like cars on the same street at the same time) into small "communities." They solved the traffic puzzle for each small group independently, then stitched the answers back together. This made the impossible problem manageable.

4. The Showdown: Quantum vs. Classical

They tested their method against the best "classical" (normal) computers available, specifically a powerful solver called Gurobi.

The Result: The quantum-assisted method (called a "hybrid" solver because it uses both quantum and classical parts) performed almost as well as the super-powerful Gurobi.
The Score: The quantum solution was usually within 1% of the perfect answer found by Gurobi.
The Speed: While Gurobi got faster on small problems, the quantum method was surprisingly steady. It didn't get slower as the problem got bigger; it just took a consistent amount of time to do its work, which is a unique trait of this technology.

5. The Payoff: Less Traffic, More Flow

When they compared their optimized routes to the standard "shortest path" routes that GPS usually suggests:

The Improvement: The optimized system reduced the overall "congestion cost" by up to 24.4% (for the quantum method) and 29.4% (for the classical method).
The Catch: This doesn't mean every single driver got home faster. In fact, some drivers might have taken a slightly longer route. But because the traffic was spread out more evenly across the city, the whole system moved much better, and the total time lost to traffic jams dropped significantly.

6. The "City Shape" Factor

The paper also found that the shape of the city matters.

Regular Cities: In cities with a neat, grid-like layout (like Cardiff), the quantum computer worked very smoothly.
Irregular Cities: In cities with winding, messy streets (like Košice), the quantum computer had to work a bit harder, and the results were slightly less perfect. This shows that the "terrain" of the city affects how well the quantum brain can think.

Summary

The paper proves that we can use quantum computers to help manage city traffic on a massive scale. By breaking the city into smaller groups of interacting cars and using a quantum "super-brain" to solve those groups, we can find a "sweet spot" where traffic flows much smoother than if everyone just drove the shortest route. It's not a magic wand that eliminates traffic, but it's a powerful new tool that can help cities breathe a little easier.

Technical Summary: Quantum Annealing for Realistic Traffic Flow Optimization

Problem Formulation
This work addresses the Traffic Flow Optimization (TFO) problem, defined as the assignment of exactly one route to each vehicle from a set of precomputed alternatives within a city-wide network. The objective is to minimize a composite cost function comprising two elements:

Spatiotemporal Congestion: Modeled as "leader–follower" interactions where vehicles occupy the same road segment in the same direction at overlapping times. Congestion is quantified by a score based on the time headway between vehicles, scaled by a sensitivity parameter $\gamma$ .
Route Duration Penalties: A linear penalty discourages assignments of routes significantly longer than a vehicle's shortest available option, ensuring individual travel efficiency is not sacrificed excessively for system-wide gains.

The problem is formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem. Binary variables $x_{i,a_i}$ represent the selection of route $a_i$ for vehicle $i$ . The QUBO objective function includes quadratic terms encoding pairwise congestion interactions and linear terms for duration penalties. A critical component is the analytically derived penalty parameter $\lambda$ , which enforces the "one-hot" constraint (each vehicle selects exactly one route) without manual tuning, following the Verma–Lewis principle.

Methodology
The study employs a data-driven workflow utilizing OpenStreetMap (OSM) for city network extraction and the Valhalla routing engine to generate multiple route alternatives per vehicle. Vehicle trajectories are sampled at fixed intervals to compute congestion weights based on spatiotemporal overlaps.

To address the combinatorial explosion of variables in large-scale instances (up to 25,000 vehicles), the framework utilizes Leiden clustering. Vehicles are partitioned into dense communities based on their pairwise congestion interactions. This decomposition allows the global problem to be solved as a series of smaller, independent subproblems.

The optimization is evaluated using:

Quantum/Hybrid Solvers: D-Wave's LeapHybridBQMSampler (QAHS), which utilizes a quantum annealer as a subroutine within a classical hybrid workflow.
Classical Solvers: Gurobi (exact Mixed-Integer Programming), CBC (open-source MILP), Simulated Annealing (SA), and Tabu Search.
Baselines: Random route assignment and shortest-duration routing.

The evaluation spans three instance categories: small-scale (direct QPU execution), medium-scale, and large-scale city scenarios across multiple cities (Košice, Prague, Cardiff).

Key Contributions

Data-Driven QUBO Formulation: A scalable, time-resolved TFO model that captures fine-grained spatiotemporal vehicle conflicts and travel-time penalties.
Analytical Penalty Parameter: An analytically derived $\lambda$ that guarantees feasible one-hot route assignments without empirical tuning.
Scalable Workflow: A simulation-to-optimization pipeline combining Leiden clustering with congestion modeling, enabling benchmarking on instances with up to 25,000 vehicles.
Extensive Benchmarking: A comparative analysis of quantum, hybrid, and classical solvers across diverse city topologies and traffic patterns (random vs. attraction-point directed flows).
Framework Flexibility: An extensible architecture capable of operating as a standalone analysis tool or an add-on module for navigation platforms, supporting dynamic adjustments for events or road closures.

Results

Solution Quality: Across large-scale scenarios, the hybrid quantum-classical approach (QAHS) consistently produces feasible solutions within approximately 1% of the objective values achieved by the exact solver Gurobi.
Congestion Reduction: Compared to the shortest-route baseline, the proposed optimization reduces the congestion-cost objective by up to 24.4% for the hybrid solver and 29.4% for Gurobi.
Scalability and Runtime: While Gurobi outperforms QAHS in runtime for smaller instances ( $n \le 4,000$ ), QAHS exhibits stable, predictable runtimes (ranging from ~3s to ~117s) as problem size increases, whereas classical solvers face exponential growth in complexity. The QPU access time remains negligible (<0.1s), with the bottleneck lying in problem embedding and orchestration.
Topology Sensitivity: Solver performance is heavily influenced by city map structure. Regular topologies (e.g., Cardiff) yield smaller energy gaps between QAHS and Gurobi (<0.83%), while irregular, heterogeneous networks (e.g., Košice) result in larger deviations.
Clustering Efficacy: Leiden clustering successfully captures the majority of dominant congestion interactions within subproblems (intra-cluster interaction fraction $\eta$ ), though this fraction decreases as the number of vehicles increases and interactions become more distributed.

Significance and Claims
The paper posits that hybrid quantum-classical approaches serve as a viable complementary method for complex, large-scale optimization problems like TFO. The study demonstrates that while exact classical solvers (Gurobi) currently achieve the absolute best solutions, hybrid solvers offer a practical alternative with stable runtimes and near-optimal quality for city-scale networks.

The authors highlight that the framework balances individual driver efficiency with system-wide congestion reduction, offering a potential addition to Intelligent Transportation Systems (ITS). The work emphasizes that the effectiveness of quantum annealing in this domain is instance-dependent, particularly sensitive to network topology and the density of pairwise interactions. The study acknowledges current limitations, including the need for offline preprocessing (non-real-time) and the reliance on static simulation windows, but suggests that as quantum hardware and embedding techniques mature, the approach could handle larger and more detailed formulations.