arXiv:1708.01625 · Frontiers in ICT

Traffic Flow Optimization Using a Quantum Annealer

Florian Neukart, G. Compostella, Christian Seidel, David Von Dollen, Sheir Yarkoni, Bob Parney

Published Dec 19, 2017• 464 citations

Abstract

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 a 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 computing. 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.

DOI: 10.3389/fict.2017.00029

Related papers

Optimizing traffic flow using quantum annealing and classical machine learning

Florian Neukart, G. Compostella, Christian Seidel +3 more

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.

Aug 4, 20171 citation

Mini-scale traffic flow optimization: an iterative QUBOs approach converting from hybrid solver to pure quantum processing unit

Hadi Salloum, Sanzhar Zhanalin, Amer Al Badr +1 more

Traffic congestion continues to pose a significant challenge in urban environments, necessitating innovative approaches to traffic management. This paper explores the application of Quantum Annealing (QA) for real-world traffic optimization, expanding on the pioneering work of Volkswagen and D-Wave. In 2017, a collaborative team demonstrated the potential of QA to optimize traffic flow by solving a complex Quadratic Unconstrained Binary Optimization (QUBO) problem involving 418 cars, which required 1,254 qubits. Later, this research culminated in a pilot project at the Web Summit conference in Lisbon, one of Europe's largest technology events, showcasing quantum computing-based traffic optimization. Since the QPU alone could not directly handle the full problem size, the team employed a hybrid classical-quantum approach, leading to significant improvements in traffic distribution. This paper builds on that foundation by investigating potential speedups using a purely quantum approach, particularly by utilizing the QPU for smaller QUBO problems. The proposed method (MTF) enhances traffic management by decomposing the overall optimization problem into smaller, more manageable subproblems. This decomposition enables us to harness the advantages of the QPU while tackling more complex traffic scenarios that previous approaches struggled to manage. By breaking the problem into smaller parts, we mitigate the challenges associated with embedding large-scale problems into the QPU, which often presents computational difficulties. To evaluate our approach, we conducted experiments involving 100, 200, 300, 400, and 500 cars on a complex traffic map featuring multiple start and end points. We successfully embedded the problem into the D-Wave Advantage Quantum Processing Unit, utilizing the "Pegasus" topology, which resulted in a significant acceleration of the solution process. The experiment results show improved speed and effectiveness in real-world scenarios by leveraging the QPU for better traffic optimization.

Scientific ReportsJul 1, 202511 citations

Quantum Congestion-Focused Traffic Optimization (Q-CFTO): Enhancing Traffic Congestion Solutions with Quantum Annealing

Hadi Salloum, Sanzhar Zhanalin, Amer Al Badr +1 more

Traffic congestion remains a significant challenge in urban environments, necessitating innovative solutions for efficient traffic management. This paper explores the use of quantum annealing for traffic optimization, building on the pioneering work of Volkswagen and D-Wave. In 2017, a collaborative team demonstrated the potential of quantum annealing to optimize traffic flow by addressing a complex 418-car Quadratic Unconstrained Binary Optimization problem. Using a hybrid classical and quantum computing approach, they achieved notable improvements in traffic distribution. In this paper, we introduce a novel approach: Quantum Congestion-Focused Traffic Optimization (Q-CFTO). Our approach is designed to enhance traffic management optimization by breaking down the problem of optimizing traffic flow into smaller and more manageable subproblems rather than dealing with a single large optimization challenge. This decomposition facilitates the handling of the problem's complexity as embedding a large problem into a Quantum Processing Unit can be difficult. We successfully embedded the problem directly into the D-Wave Advantage Quantum Processing Unit with the "Pegasus" topology, significantly accelerating the solution process. The results demonstrate that our approach is both faster and more effective in real-world scenarios.

Aug 12, 20245 citations

Applying a Quantum Annealer to the Traffic Assignment Problem

Darren M. Chitty, James Charles, Alberto Moraglio +1 more

The Traffic Assignment Problem (TAP) is a complex transportation optimisation problem typically solved using meta-heuristics on classical computers. Quantum computers, despite being a nascent technology, have the potential to significantly speed up computation by exploiting quantum parallelism. A quantum annealer (QA) is a quantum computer tailored to solve combinatorial optimisation problems formulated as a Quadratic Unconstrained Binary Optimisation (QUBO). Formulating complex optimisation problems as QUBO is an open challenge. This paper derives a new QUBO formulation for TAP by employing a streamlined methodology of general applicability. It also attempts a direct comparison at solving TAP encompassing a QA (D-WAVE), a hybrid quantum-classical algorithm, and classical methods including Simulated Annealing and Genetic Algorithms. This comparison is difficult and seldom done due to the inherent differences between quantum and classic hardware. As expected from the current quantum technology, our results show that a pure QA suffers from significant noise in qubits and requires significant additional computational time, although we show that the time required solely by the QPU does not increase with problem size. We also show that the hybrid QA mitigates these noise issues and is on a par with traditional methods.

Genetic and Evolutionary Computation Conference (GECCO)Jul 8, 20248 citations

Quantum annealing for vehicle routing problem with weighted segment

Toufan Diansyah Tambunan, Andriyan Bayu Suksmono, Ian Joseph Matheus Edward +1 more

Quantum annealing technologies aim to solve computational optimization and sampling problems. QPU (Quantum Processing Unit) machines such as the D-Wave system use the QUBO (Quadratic Unconstrained Binary Optimization) formula to define model optimization problems for quantum annealing. This machine uses quantum effects to speed up computing time better than classical computers. We propose a vehicle routing problem that can be formulated in the QUBO model as a combinatorial problem, which gives the possible route solutions increases exponentially. The solution aims to optimize the vehicle's journey to reach a destination. The study presents a QUBO formulation to solve traffic congestion problems on certain roads. The resulting route selection by optimizing the distribution of the flow of alternative road vehicles based on the weighting of road segments. Constraints formulated as a condition for the level of road density. The road weight parameter influences the cost function for each road choice. The simulations on the D-Wave quantum annealer show optimal results on the route deployment of several vehicles. So that each vehicle will be able to go through different road options and reduce road congestion accurately. This solution provides an opportunity to develop QUBO modeling for more complex vehicle routing problems for road congestion.

arXiv:2203.13469AIP conference proceedingsJan 1, 202319 citations

Traffic signal optimization using quantum annealing on real map

Reo Shikanai, Masayuki Ohzeki, Kazuyuki Tanaka

Abstract The quantum annealing machine manufactured by D-Wave Systems is expected to find the optimal solution for QUBO (Quadratic Unconstrained Binary Optimization) accurately and quickly.This would be useful in future applications where real-time calculation is needed.One such application is traffic signal optimization.Some studies use quantum annealing for this.However, they are formulated in unrealistic settings, such as only crossroads on the map.Therefore, we suggest a QUBO, which can deal with T-junctions and multi-forked roads.To validate the efficiency of our approach, SUMO (Simulation of Urban MObility) is used.This enables us to experiment with geographic information data very close to the real world.We compared results with those using the Gurobi Optimizer in the experiment to confirm that quantum annealing can find a ground state.The results show that the quantum annealing cannot find the ground state, but our model can reduce the time that vehicles wait at a red light.It is also inferior to the Gurobi Optimizer in calculation time. This seems to be due to the D-Wave machine's hardware limitations and noise effects, such as ambient temperature.If these problems are solved, and the number of qubits is increased, the use of quantum annealing is likely to be superior in terms of the speed of calculating an optimal solution.

Sep 4, 20234 citations