Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2002.01351 · IEEE Transactions on Intelligent Transportation Systems

Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm

Utkarsh Azad, Bikash K. Behera, Emad A. Ahmed, Prasanta Kumar Panigrahi, Ahmed Farouk

Published May 13, 2022• 149 citations
arXivHTMLPDF

Abstract

Intelligent transportation systems (ITS) are a critical component of Industry 4.0 and 5.0, particularly having applications in logistic management. One of their crucial utilization is in supply-chain management and scheduling for optimally routing transportation of goods by vehicles at a given set of locations. This paper discusses the broader problem of vehicle traffic management, more popularly known as the Vehicle Routing Problem (VRP), and investigates the possible use of near-term quantum devices for solving it. For this purpose, we give the Ising formulation for VRP and some of its constrained variants. Then, we present a detailed procedure to solve VRP by minimizing its corresponding Ising Hamiltonian using a hybrid quantum-classical heuristic called Quantum Approximate Optimization Algorithm (QAOA), implemented on the IBM Qiskit platform. We compare the performance of QAOA with classical solvers such as CPLEX on problem instances of up to 15 qubits. We find that performance of QAOA has a multifaceted dependence on the classical optimization routine used, the depth of the ansatz parameterized by$p$, initialization of variational parameters, and problem instance itself.

DOI
10.1109/tits.2022.3172241

Related papers

Variational Quantum Algorithms for Solving Vehicle Routing Problem

Muhammad Alsaiyari, Muhamad Felemban

Vehicle Routing Problem (VRP) is considered one of the most challenging problems with application in several domains, including transportation and logistics distribution. VRP is known to be NP-Hard problem. Several algorithms have been proposed to solve VRP in polynomial time. However, these algorithms are inefficient if the VRP instance increases. Recently, researchers investigated how quantum computing can be used to solve VRP. In particular, two promising variational quantum algorithms have been studied, i.e., Variational Quantum Eigensolver (VQE) and Quantum Approximate Optimization Algorithm (QAOA). In this paper, we implement both algorithms on IBM Qiskit and compare their evaluation in solving several instances of VRP. We observe that current Noisy-Intermediate Scale Quantum (NISQ) devices cannot solve VRP instances beyond 5 nodes and 2 vehicles. Furthermore, we observe that classical optimizers still provide better results. However, we believe that with the rapid advancement of quantum computing manufacturing, VQE and QAOA can provide better performance as compared to classical computing,

International Conference on Smart Computing and Application (ICSCA)•Feb 5, 2023•8 citations

Applying quantum approximate optimization to the heterogeneous vehicle routing problem

David Fitzek, Toheed Ghandriz, Leo Laine +2 more

Quantum computing offers new heuristics for combinatorial problems. With small- and intermediate-scale quantum devices becoming available, it is possible to implement and test these heuristics on small-size problems. A candidate for such combinatorial problems is the heterogeneous vehicle routing problem (HVRP): the problem of finding the optimal set of routes, given a heterogeneous fleet of vehicles with varying loading capacities, to deliver goods to a given set of customers. In this work, we investigate the potential use of a quantum computer to find approximate solutions to the HVRP using the quantum approximate optimization algorithm (QAOA). For this purpose we formulate a mapping of the HVRP to an Ising Hamiltonian and simulate the algorithm on problem instances of up to 21 qubits. We show that the number of qubits needed for this mapping scales quadratically with the number of customers. We compare the performance of different classical optimizers in the QAOA for varying problem size of the HVRP, finding a trade-off between optimizer performance and runtime.

arXiv:2110.06799•Scientific Reports•Oct 25, 2024•42 citations

Quantum-Assisted Vehicle Routing: Realizing QAOA-based Approach on Gate-Based Quantum Computer

Talha Azfar, Osama M. Raisuddin, Ruimin Ke +1 more

The Vehicle Routing Problem (VRP) is a fundamental combinatorial optimization challenge with broad applications in logistics and transportation. In this work, we present a quantum-assisted framework that integrates the Quantum Approximate Optimization Algorithm (QAOA) with a link-based formulation of VRP. Our approach encodes flow conservation and subtour elimination directly into the cost Hamiltonian, preserving graph structure while minimizing resource requirements for practical hardware implementation. We design and implement the full pipeline on a gate-based quantum computer, including problem formulation, encoding, circuit synthesis, and execution on IBM Quantum System One. Experimental results on small VRP instances highlight the effects of penalty scaling, coefficient normalization, and circuit depth on solution feasibility under hardware noise. While scalability remains constrained by circuit complexity and decoherence, the study demonstrates a practical pathway for implementing VRP on quantum hardware and identifies methodological directions for advancing near-term quantum optimization.

arXiv:2505.01614•May 2, 2025•3 citations

Study on Quantum Approximation Optimization Algorithm in Airport Cargo Transportation Problem

Xudong Zhao, Jianping Chen, Lan Liu +1 more

The vehicle routing problem (VRP) is a core NP‐hard combinatorial optimization problem in logistics and supply chain management. Quantum computing, particularly the Quantum Approximate Optimization Algorithm (QAOA), is being explored as a promising heuristic tool for tackling such problems. Therefore, this study employs the QAOA approach to solve the airport cargo VRP. Subsequently, through a concrete airport cargo case study, the paper analyzes the process of solving single‐vehicle TSP and multivehicle VRP problems using QAOA. It compares the performance of different classical optimizers and discusses the impact of parameter settings (e.g., penalty factors, QAOA depth, and number of iterations) on the solution quality and feasibility, especially comparing the convergence speed of dynamic and fixed penalty coefficients. The paper also describes the design principles of QAOA quantum circuits for such VRP problems. Furthermore, the study presents a preliminary benchmark on a real quantum computer, demonstrating that its computation time for the problem’s QUBO matrix (14 ms) is approximately comparable to that of classical algorithms. Finally, it summarizes the current scalability challenges and limitations faced by QAOA in VRP applications concerning qubit count, circuit depth, and classical optimizer performance, and offers an outlook on future development directions. The research indicates that although QAOA demonstrates solution capabilities on specific small‐scale VRP instances, the complexity of parameter tuning and sensitivity to the spatial distribution of aircraft stands are critical considerations before practical application.

Journal of Advanced Transportation•Jan 1, 2026•0 citations

Quantum Path Integral Approach for Vehicle Routing Optimization With Limited Qubit

Kumar Gautam, Chang Wook Ahn

The Vehicle Routing Problem (VRP) is a crucial combinatorial optimization problem in transportation, logistics, and supply chain management. Quantum computing has gained interest in solving complex optimization issues. This review paper proposes a novel approach that combines quantum computing principles with the Feynman path integral formulation to address the VRP. The paper focuses on limited qubits and how quantum algorithms can circumvent this limitation. Conventional methods, such as Lagrangian and combinatorial optimization, require computational time to solve complex atomic-scale problems. The path integral formulation with the first Born approximation method offers a more elegant explanation of quantum computing. The algorithm investigates quantum system dynamics using the Schrodinger wave equation and computes probability amplitude distributions for optimal vehicle routing techniques. This work will take advantage of entanglement and interference effects for heuristic sampling of high-quality solutions, making the Quantum Path Integral Approach (QPIA) a promising study environment for investigating quantum circuits and algorithms in routing problems with constrained qubits.

IEEE Transactions on Intelligent Transportation Systems•Dec 6, 2023•17 citations

Quantum Vehicle Routing Problem: a smart initialization strategy for ill-conditioned optimization landscapes

Emanuele Casciaro, Mario De Simone, Stefano Martina +3 more

With the expansion of complex transport infrastructure, new paths for linking different destinations have emerged, allowing the definition of multiple routes. The introduction of new roads may also lead to disruptions in traffic flow. This problem can be generalized into a special case of VRP, which aims to find the optimal route for a fleet of vehicles within a network of destinations. Finding solutions to this problem requires an exponential number of operations, hindering the ability of exact solvers to deal with large instances, which must therefore be tackled using heuristics, often leading to suboptimal results. Quantum-based algorithms may allow us to find exact solutions in polynomial time with high probability, offering a potential future alternative to classical solvers and in this work, we focus on the QAOA. Our novel contributions are a parameter-initialization strategy that improves the convergence probability and the integration of the subtour constraints directly into the optimization without using additional qubits by employing an approximation of exponential equality constraints. We believe that our results pave the way for effectively solving instances of VRP using quantum-based solutions, leveraging the space-efficient problem encoding and our initialization strategy, which limits the effect of barren-plateau under random parameter initialization.

quant-pharXiv:2610.41120•Nov 2, 2026
Intelligent transportation systems (ITS) are a critical component of Industry 4.0 and 5.0, particularly having applications in logistic management. One of their crucial utilization is in supply-chain management and scheduling for optimally routing transportation of goods by vehicles at a given set of locations. This paper discusses the broader problem of vehicle traffic management, more popularly known as the Vehicle Routing Problem (VRP), and investigates the possible use of near-term quantum devices for solving it. For this purpose, we give the Ising formulation for VRP and some of its constrained variants. Then, we present a detailed procedure to solve VRP by minimizing its corresponding Ising Hamiltonian using a hybrid quantum-classical heuristic called Quantum Approximate Optimization Algorithm (QAOA), implemented on the IBM Qiskit platform. We compare the performance of QAOA with classical solvers such as CPLEX on problem instances of up to 15 qubits. We find that performance of QAOA has a multifaceted dependence on the classical optimization routine used, the depth of the ansatz parameterized byppp, initialization of variational parameters, and problem instance itself.
Vehicle Routing Problem (VRP) is considered one of the most challenging problems with application in several domains, including transportation and logistics distribution. VRP is known to be NP-Hard problem. Several algorithms have been proposed to solve VRP in polynomial time. However, these algorithms are inefficient if the VRP instance increases. Recently, researchers investigated how quantum computing can be used to solve VRP. In particular, two promising variational quantum algorithms have been studied, i.e., Variational Quantum Eigensolver (VQE) and Quantum Approximate Optimization Algorithm (QAOA). In this paper, we implement both algorithms on IBM Qiskit and compare their evaluation in solving several instances of VRP. We observe that current Noisy-Intermediate Scale Quantum (NISQ) devices cannot solve VRP instances beyond 5 nodes and 2 vehicles. Furthermore, we observe that classical optimizers still provide better results. However, we believe that with the rapid advancement of quantum computing manufacturing, VQE and QAOA can provide better performance as compared to classical computing,
Quantum computing offers new heuristics for combinatorial problems. With small- and intermediate-scale quantum devices becoming available, it is possible to implement and test these heuristics on small-size problems. A candidate for such combinatorial problems is the heterogeneous vehicle routing problem (HVRP): the problem of finding the optimal set of routes, given a heterogeneous fleet of vehicles with varying loading capacities, to deliver goods to a given set of customers. In this work, we investigate the potential use of a quantum computer to find approximate solutions to the HVRP using the quantum approximate optimization algorithm (QAOA). For this purpose we formulate a mapping of the HVRP to an Ising Hamiltonian and simulate the algorithm on problem instances of up to 21 qubits. We show that the number of qubits needed for this mapping scales quadratically with the number of customers. We compare the performance of different classical optimizers in the QAOA for varying problem size of the HVRP, finding a trade-off between optimizer performance and runtime.
The Vehicle Routing Problem (VRP) is a fundamental combinatorial optimization challenge with broad applications in logistics and transportation. In this work, we present a quantum-assisted framework that integrates the Quantum Approximate Optimization Algorithm (QAOA) with a link-based formulation of VRP. Our approach encodes flow conservation and subtour elimination directly into the cost Hamiltonian, preserving graph structure while minimizing resource requirements for practical hardware implementation. We design and implement the full pipeline on a gate-based quantum computer, including problem formulation, encoding, circuit synthesis, and execution on IBM Quantum System One. Experimental results on small VRP instances highlight the effects of penalty scaling, coefficient normalization, and circuit depth on solution feasibility under hardware noise. While scalability remains constrained by circuit complexity and decoherence, the study demonstrates a practical pathway for implementing VRP on quantum hardware and identifies methodological directions for advancing near-term quantum optimization.
The vehicle routing problem (VRP) is a core NP‐hard combinatorial optimization problem in logistics and supply chain management. Quantum computing, particularly the Quantum Approximate Optimization Algorithm (QAOA), is being explored as a promising heuristic tool for tackling such problems. Therefore, this study employs the QAOA approach to solve the airport cargo VRP. Subsequently, through a concrete airport cargo case study, the paper analyzes the process of solving single‐vehicle TSP and multivehicle VRP problems using QAOA. It compares the performance of different classical optimizers and discusses the impact of parameter settings (e.g., penalty factors, QAOA depth, and number of iterations) on the solution quality and feasibility, especially comparing the convergence speed of dynamic and fixed penalty coefficients. The paper also describes the design principles of QAOA quantum circuits for such VRP problems. Furthermore, the study presents a preliminary benchmark on a real quantum computer, demonstrating that its computation time for the problem’s QUBO matrix (14 ms) is approximately comparable to that of classical algorithms. Finally, it summarizes the current scalability challenges and limitations faced by QAOA in VRP applications concerning qubit count, circuit depth, and classical optimizer performance, and offers an outlook on future development directions. The research indicates that although QAOA demonstrates solution capabilities on specific small‐scale VRP instances, the complexity of parameter tuning and sensitivity to the spatial distribution of aircraft stands are critical considerations before practical application.
The Vehicle Routing Problem (VRP) is a crucial combinatorial optimization problem in transportation, logistics, and supply chain management. Quantum computing has gained interest in solving complex optimization issues. This review paper proposes a novel approach that combines quantum computing principles with the Feynman path integral formulation to address the VRP. The paper focuses on limited qubits and how quantum algorithms can circumvent this limitation. Conventional methods, such as Lagrangian and combinatorial optimization, require computational time to solve complex atomic-scale problems. The path integral formulation with the first Born approximation method offers a more elegant explanation of quantum computing. The algorithm investigates quantum system dynamics using the Schrodinger wave equation and computes probability amplitude distributions for optimal vehicle routing techniques. This work will take advantage of entanglement and interference effects for heuristic sampling of high-quality solutions, making the Quantum Path Integral Approach (QPIA) a promising study environment for investigating quantum circuits and algorithms in routing problems with constrained qubits.
With the expansion of complex transport infrastructure, new paths for linking different destinations have emerged, allowing the definition of multiple routes. The introduction of new roads may also lead to disruptions in traffic flow. This problem can be generalized into a special case of VRP, which aims to find the optimal route for a fleet of vehicles within a network of destinations. Finding solutions to this problem requires an exponential number of operations, hindering the ability of exact solvers to deal with large instances, which must therefore be tackled using heuristics, often leading to suboptimal results. Quantum-based algorithms may allow us to find exact solutions in polynomial time with high probability, offering a potential future alternative to classical solvers and in this work, we focus on the QAOA. Our novel contributions are a parameter-initialization strategy that improves the convergence probability and the integration of the subtour constraints directly into the optimization without using additional qubits by employing an approximation of exponential equality constraints. We believe that our results pave the way for effectively solving instances of VRP using quantum-based solutions, leveraging the space-efficient problem encoding and our initialization strategy, which limits the effect of barren-plateau under random parameter initialization.