Applying a Quantum Annealer to the Traffic Assignment Problem
Chitty, DM; Charles, J; Moraglio, A; et al.Keedwell, E
Date: 2024
Conference paper
Publisher
Association for Computing Machinery (ACM)
Abstract
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 computa tion by exploiting quantum parallelism. A quantum annealer (QA)
is a quantum ...
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 computa tion by exploiting quantum parallelism. A quantum annealer (QA)
is a quantum computer tailored to solve combinatorial optimisa tion 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.
Computer Science
Faculty of Environment, Science and Economy
Item views 0
Full item downloads 0