Source-linked AI summary
Traffic flow optimization using a quantum annealer
Florian Neukart, Gabriele Compostella, Christian Seidel, David von Dollen, Sheir Yarkoni, Bob Parney
TL;DR
The paper addresses how quantum annealing can support real-time traffic-flow optimization. It maps route redistribution into a QUBO and integrates D-Wave processing within a hybrid workflow, concluding that this class of task is suitable for D-Wave systems.
Problem
The paper examines how to map time-critical traffic-flow optimization, including continuous car-position redistribution in dense road networks, onto quantum annealing.
Method
The authors use T-Drive trajectories, transform route redistribution into QUBO form, and combine classical processing with D-Wave QPU calls.
Results
The workflow demonstrates that D-Wave QPU calls can be integrated into a real-world-like traffic-optimization application.
Takeaways & Limitations
The paper concludes that these real-time optimization problems are well-suited for D-Wave systems and hybrid tools using them.
Takeaways & Limitations
The presented traffic-flow problem is simplified to a limited set of cars without infrastructure communication or other traffic participants.
Abstract
from arXiv · showhide
Quantum annealing algorithms belong to the class of meta-heuristic tools, applicable for solving binary optimization problems. Hardware implementations of quantum annealing, such as the quantum processing units (QPUs) produced by D-Wave Systems, have been subject to multiple analyses in research, with the aim of characterizing the technology's usefulness for optimization and sampling tasks. In this paper, we present a real-world application that uses quantum technologies. Specifically, we show how to map certain parts of the real-world traffic flow optimization problem to be suitable for quantum annealing. We show that time-critical optimization tasks, such as continuous redistribution of position data for cars in dense road networks, are suitable candidates for quantum applications. Due to the limited size and connectivity of current-generation D-Wave QPUs, we use a hybrid quantum and classical approach to solve the traffic flow problem.
1 Introduction
The paper maps a real-world traffic-flow optimization problem onto D-Wave quantum annealing, using a hybrid quantum/classical workflow because current QPUs have limited size and connectivity.
- D-Wave QPUs are designed for quadratic unconstrained binary optimization problems, with qubits representing variables and couplers representing pairwise costs.The QPU implements an undirected graph whose vertices are qubits and edges are couplers.
- A QUBO objective has the form Obj(x, Q) = xT · Q · x, where x is a binary-variable vector and Q describes variable relationships.Minimizing this objective is equivalent to minimizing an Ising model.
- The study starts from car GPS trajectories and develops a workflow intended to optimize traffic flow in real time.The workflow uses the T-Drive trajectory dataset and transforms key elements of the problem into QUBO form.
- The D-Wave system is treated as an optimizer within a workflow combining its machine and software tools with classical processing.The paper presents a novel mapping of this real-world problem onto a quantum computer.
2 Formulation of the traffic flow problem
The traffic-flow formulation uses trajectory and map data to identify congestion, generate alternative routes, encode route assignments as a QUBO, and iteratively redistribute cars.
- 2 Formulation of the traffic flow problem: The objective is to reduce cars’ travel time by minimizing total congestion across road segments.Segment congestion depends on the number of cars traversing the segment during a time interval.
- 2 Formulation of the traffic flow problem: The workflow preprocesses map and GPS data, identifies congestion, determines valid alternative routes, and formulates the redistribution problem as a QUBO.Classical steps prepare the data and routes before optimization.
- 2 Formulation of the traffic flow problem: The hybrid quantum/classical step finds route assignments that reduce congestion across the whole traffic graph, after which cars are redistributed and the process iterates.Iteration continues until no traffic congestion is identified.
- 2.1 Determination of alternate routes: For the Beijing scenario, 418 cars traveling to or from the city center and airport were selected, with three candidate routes proposed for each car.Alternative paths were selected using dissimilarity from the original route and from one another, measured with the Jaccard similarity index.
- 2.1 Determination of alternate routes: The route-assignment objective minimizes intersecting road segments while optimizing all cars simultaneously so that relieving one congestion area does not create another.The road graph is extracted from the Beijing map using OSMnx, with segments and nodes assigned unique IDs.
- 2.2 Formulating the traffic flow optimization in QUBO form: The QUBO combines segment-occupancy costs with one-route constraints, using λ large enough that violating a route constraint costs more than increasing every segment occupancy by one.Binary simplification and matrix construction produce the required quadratic upper-triangular QUBO matrix, including route-overlap coefficients and constraint terms.
- 2.2 Formulating the traffic flow optimization in QUBO form: Each binary variable qij represents car i taking route j, and the QUBO requires exactly one route per car while minimizing total congestion on assigned routes.The formulation uses at most three routes per car for simplicity, although the mathematical description is unchanged for more routes.
3 D-Wave solvers and architecture
The D-Wave 2X QPU uses a Chimera graph with restricted connectivity, so larger QUBO problems require minor-embedding or hybrid decomposition. qbsolv partitions large inputs into sub-problems, solves them iteratively, and can submit those sub-problems to the QPU.
- QPU architecture: The D-Wave 2X QPU uses a C12 Chimera graph with 1152 vertices and over 3000 couplers.Each Chimera cell contains a K4,4 graph, and vertices connect within cells and to neighboring cells.
- Problem size: The 418-car example used 1254 logical variables, exceeding the 1135 functional qubits available on the QPU.Consequently, the logical variables could not be embedded on the QPU at once.
- Connectivity limitations: QPU connectivity restricts direct solution of arbitrarily structured problems because variable interactions require physical couplers.Most problem-variable interactions do not match the QPU connectivity.
- Connectivity limitations: Minor-embedding maps one graph structure to another to accommodate problem interactions on the QPU topology.The technique is used to circumvent connectivity mismatches between logical variables and physical qubits.
- Hybrid solver: qbsolv handles larger QUBOs by partitioning them into important components and solving those components independently with Tabu search and QPU queries.In hybrid classical/quantum mode, it ranks variables, creates fitting sub-problems, updates the bit-string, and iterates until no objective improvement is found.
4 Results
The experiments evaluated a 418-car QUBO formulation with qbsolv against random route assignments, measuring congested road segments. qbsolv redistributed traffic and reduced congestion, resolving it in all 50 experiments with a minimum observed runtime of 22 seconds.
- Traffic quality was evaluated by counting road segments appearing in more than Nintersections = 10 routes as congested.
- The experiments solved the 418-car QUBO problem 50 times with qbsolv and generated 50 random route assignments as a reference.
- qbsolv redistributed traffic over alternative routes and reduced the number of congested roads relative to the reference assignments.
- The optimized assignment improved on the original routes, where many cars shared the same streets and average occupancy exceeded Nintersections = 10.
- The experiments used a VFYC version of the D-Wave 2X solver, which simulated missing qubits and couplers with classical software.
- All 50 experiments using qbsolv resolved the congestion.
- 22 seconds was the minimum observed qbsolv runtime, while cloud queueing caused substantial runtime variation without evidence of correlation between runtime and performance.
5 Conclusions and future work
The authors present the traffic-flow problem as a simplified real-world optimization workflow using D-Wave systems and hybrid tools. They identify real-time optimization as suitable for this approach while noting that larger, richer formulations remain future work.
- The presented traffic-flow problem is simplified to a limited set of cars, without infrastructure communication or other traffic participants.
- The current formulation optimizes only the minimization of road congestion.
- Future work will incorporate the omitted parameters and formulate them as part of the QUBO problem.
- The authors find real-time optimization problems well-suited to D-Wave systems and the hybrid tools that use them.
- The authors expect future QPU generations to embed larger problems directly as qubit counts continue to grow.
Figures
The figures depict the Beijing road graph, route segmentation for an individual car, the QUBO formulation, and traffic distributions before and after optimization.
- Figure 1 shows an OSMnx graph of downtown Beijing.
- Figure 2 illustrates one car's assigned routes divided into segments.
- Figure 3 presents the QUBO matrix describing the traffic flow problem.
- Figure 4 compares random route assignments with qbsolv using D-Wave 2X QPU calls, plotting distributions of congested roads against the original assignment.
- Figure 5 contrasts an unoptimized traffic situation with qbsolv's optimized redistribution, where red high-density areas are mostly absent.