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

Discrete Dynamics in Nature and Society

Study on Quantum Approximate Optimization Algorithm for the Capacitated Vehicle Routing Problem Based on Real Airport Cargo Transportation

Xudong Zhao, Lan Liu, Jianping Chen

Published Jan 1, 2026• 0 citations
Publisher

Abstract

This paper investigates the application of the quantum approximate optimization algorithm (QAOA) to solve the capacitated vehicle routing problem (CVRP) within the context of airport cargo logistics. The core of this research is to establish a comprehensive theoretical framework that systematically transforms the NP‐hard CVRP—including its objective function (cost minimization) and complex constraints (vehicle capacity, customer visit requirements, and subtour elimination)—into a quadratic unconstrained binary optimization (QUBO) model. This QUBO model is subsequently mapped to a problem Hamiltonian suitable for the QAOA. The study also explores practical implementation challenges, such as the critical role of penalty factors in obtaining feasible solutions, and proposes a method for determining these factors based on the problem’s scale. Through a case study of airport cargo transportation, the feasibility of this framework is validated. Finally, the paper identifies the limitations of current quantum algorithms in handling hard constraints and outlines future research directions.

DOI
10.1155/ddns/6174076

Related papers

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

A feasibility-preserved quantum approximate solver for the Capacitated Vehicle Routing Problem

Ningyi Xie, Xinwei Lee, Dongsheng Cai +3 more

Abstract The Capacitated Vehicle Routing Problem (CVRP) is an NP-optimization problem (NPO) that arises in various fields including transportation and logistics. The CVRP extends from the Vehicle Routing Problem (VRP), aiming to determine the most efficient plan for a fleet of vehicles to deliver goods to a set of customers, subject to the limited carrying capacity of each vehicle. As the number of possible solutions skyrockets when the number of customers increases, finding the optimal solution remains a significant challenge. Recently, the Quantum Approximate Optimization Algorithm (QAOA), a quantum-classical hybrid algorithm, has exhibited enhanced performance in certain combinatorial optimization problems compared to classical heuristics. However, its ability diminishes notably in solving constrained optimization problems including the CVRP. This limitation primarily arises from the typical approach of encoding the given problems as penalty-inclusive binary optimization problems. In this case, the QAOA faces challenges in sampling solutions satisfying all constraints. Addressing this, our work presents a new binary encoding for the CVRP, with an alternative objective function of minimizing the shortest path that bypasses the vehicle capacity constraint of the CVRP. The search space is further restricted by the constraint-preserving mixing operation. We examine and discuss the effectiveness of the proposed encoding under the framework of the variant of the QAOA, Quantum Alternating Operator Ansatz (AOA), through its application to several illustrative examples. Compared to the typical QAOA approach, the proposed method not only preserves the feasibility but also achieves a significant enhancement in the probability of measuring optimal solutions.

arXiv:2308.08785•Quantum Information Processing•Jul 29, 2024•43 citations

Solving the Capacitated Vehicle Routing Problem Using the Quantum Approximate Optimization Algorithm: A Benchmark Against Classical Guided Local Search

Ninad Hirani

The Capacitated Vehicle Routing Problem (CVRP) is a combinatorial optimization problem that can be formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem, making it a potential application for near-term quantum optimization. This paper benchmarks the Quantum Approximate Optimization Algorithm (QAOA, p = 2) against Google OR-Tools Guided Local Search on a seeded instance with three customers and two vehicles. The study examines the QUBO formulation, energy spectrum, optimization behavior, penalty weights, Hamiltonian scaling, and circuit depths. The experiments show that the tested QAOA configurations do not reliably concentrate probability on optimal solutions. The classical solver identifies the optimal solution for the selected instance. The study provides a reproducible baseline and discusses limitations and future research directions. The findings are limited to the tested instance, formulation, and optimization configurations.

•Oct 15, 2026•0 citations

Quantum Optimization Pipeline for the Capacitated Vehicle Routing Problem (CVRP)

Ninad Hirani

Quantum Optimization Pipeline for the Capacitated Vehicle Routing Problem (CVRP) This repository presents a research-oriented implementation of classical and quantum optimization techniques for solving the Capacitated Vehicle Routing Problem (CVRP). The project serves as an educational and experimental framework for studying hybrid quantum-classical optimization methods and benchmarking their performance on combinatorial optimization problems. The implementation includes: Classical CVRP optimization using Google OR-Tools Mathematical formulation of the routing problem Transformation of the optimization problem into a Quadratic Unconstrained Binary Optimization (QUBO) model Conversion of the QUBO formulation into an Ising Hamiltonian Implementation of the Quantum Approximate Optimization Algorithm (QAOA) using Qiskit Classical versus quantum performance comparison Route visualization and benchmarking Modular Python code designed for experimentation and future extensions The project is intended as a foundation for exploring applications of Quantum Computing, Operations Research, and Hybrid Quantum-Classical Optimization in real-world routing and logistics problems. It provides a reproducible environment for understanding optimization workflows, evaluating quantum algorithms, and extending the framework toward more complex scenarios such as dynamic vehicle routing and emergency ambulance dispatch. Keywords: Quantum Computing, Quantum Optimization, QAOA, QUBO, Ising Model, Capacitated Vehicle Routing Problem (CVRP), Operations Research, OR-Tools, Qiskit, Combinatorial Optimization, Hybrid Quantum-Classical Algorithms. This software was developed as part of a research internship focused on quantum optimization and serves as a learning and experimentation platform for future research.

•Jul 23, 2026•0 citations

Enhancing vehicle routing problem through a qubit-efficient Symmetric Arc Reduction using Quantum Approximate Optimization Algorithm

Jayaraja A, Senthil Kumaran U

Introduction Finding the most efficient routes for a fleet of delivery vehicles remains a critical and costly challenge for nearly any logistics business. This core idea is known as the Vehicle Routing Problem (VRP). The primary goal is to minimize operational costs, such as the total travel distance or the number of trucks deployed, while ensuring all the customers are served. Because VRP is NP-hard, finding a perfect solution is often impossible, forcing industries to rely on classical approximate algorithms. However, quantum variational algorithms offer a new paradigm by iteratively optimizing parameters to navigate the solution space, presenting a new and promising avenue for finding better and faster solutions. Methods In this paper, we introduce Symmetric Arc Reduction in Quantum Approximate Optimization Algorithm (SAR-QAOA), which systematically eliminates redundant symmetric routing variables in the binary integer programming formulation prior to the Quadratic Unconstrained Binary Optimization (QUBO) formulation. The proposed SAR-QAOA encodes edge-based VRP while reducing the qubit requirement from n ( n −1) to n ( n −1)/2, thereby improving the resource efficiency of the QUBO formulation by prioritizing regions of the solution space that are more likely to contain high-quality solutions; SAR enhances both search accuracy and computational efficiency. Results Experimental results on noiseless quantum simulators validate the feasibility of the proposed formulation and its integration with the QAOA framework, providing a promising foundation for future investigations on larger routing problems and evolving quantum hardware.

Frontiers in Artificial Intelligence•Oct 1, 2026•0 citations

Hybrid Quantum-Classical Algorithm for Solving Capacitated Vehicle Routing Problems

Wei‐Hao Huang, Hiromichi Matsuyama, Yu Yamashiro

This study introduces a hybrid quantum-classical approach to solving the Capacitated Vehicle Routing Problems (CVRP), combining the Column Generation method and the Quantum Alternating Operator Ansatz (QAOAnsatz). The column generation method divides the problem into a master problem and subproblems to effectively solve the problem. We solved the subproblem by using QAOAnsatz to enhance the optimal solution search. Moreover, we generated the problem Hamiltonian using an Augmented Lagrangian-inspired Method to reduce the number of required qubits to handle the inequality. As a result, our experiments obtained an optimal solution for a CVRP problem with 6 customers. This study demonstrates a practical quantum application in logistics and sets a new technique for hybrid quantum-classical optimization frameworks.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•1 citation
This paper investigates the application of the quantum approximate optimization algorithm (QAOA) to solve the capacitated vehicle routing problem (CVRP) within the context of airport cargo logistics. The core of this research is to establish a comprehensive theoretical framework that systematically transforms the NP‐hard CVRP—including its objective function (cost minimization) and complex constraints (vehicle capacity, customer visit requirements, and subtour elimination)—into a quadratic unconstrained binary optimization (QUBO) model. This QUBO model is subsequently mapped to a problem Hamiltonian suitable for the QAOA. The study also explores practical implementation challenges, such as the critical role of penalty factors in obtaining feasible solutions, and proposes a method for determining these factors based on the problem’s scale. Through a case study of airport cargo transportation, the feasibility of this framework is validated. Finally, the paper identifies the limitations of current quantum algorithms in handling hard constraints and outlines future research directions.
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.
Abstract The Capacitated Vehicle Routing Problem (CVRP) is an NP-optimization problem (NPO) that arises in various fields including transportation and logistics. The CVRP extends from the Vehicle Routing Problem (VRP), aiming to determine the most efficient plan for a fleet of vehicles to deliver goods to a set of customers, subject to the limited carrying capacity of each vehicle. As the number of possible solutions skyrockets when the number of customers increases, finding the optimal solution remains a significant challenge. Recently, the Quantum Approximate Optimization Algorithm (QAOA), a quantum-classical hybrid algorithm, has exhibited enhanced performance in certain combinatorial optimization problems compared to classical heuristics. However, its ability diminishes notably in solving constrained optimization problems including the CVRP. This limitation primarily arises from the typical approach of encoding the given problems as penalty-inclusive binary optimization problems. In this case, the QAOA faces challenges in sampling solutions satisfying all constraints. Addressing this, our work presents a new binary encoding for the CVRP, with an alternative objective function of minimizing the shortest path that bypasses the vehicle capacity constraint of the CVRP. The search space is further restricted by the constraint-preserving mixing operation. We examine and discuss the effectiveness of the proposed encoding under the framework of the variant of the QAOA, Quantum Alternating Operator Ansatz (AOA), through its application to several illustrative examples. Compared to the typical QAOA approach, the proposed method not only preserves the feasibility but also achieves a significant enhancement in the probability of measuring optimal solutions.
The Capacitated Vehicle Routing Problem (CVRP) is a combinatorial optimization problem that can be formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem, making it a potential application for near-term quantum optimization. This paper benchmarks the Quantum Approximate Optimization Algorithm (QAOA, p = 2) against Google OR-Tools Guided Local Search on a seeded instance with three customers and two vehicles. The study examines the QUBO formulation, energy spectrum, optimization behavior, penalty weights, Hamiltonian scaling, and circuit depths. The experiments show that the tested QAOA configurations do not reliably concentrate probability on optimal solutions. The classical solver identifies the optimal solution for the selected instance. The study provides a reproducible baseline and discusses limitations and future research directions. The findings are limited to the tested instance, formulation, and optimization configurations.
Quantum Optimization Pipeline for the Capacitated Vehicle Routing Problem (CVRP) This repository presents a research-oriented implementation of classical and quantum optimization techniques for solving the Capacitated Vehicle Routing Problem (CVRP). The project serves as an educational and experimental framework for studying hybrid quantum-classical optimization methods and benchmarking their performance on combinatorial optimization problems. The implementation includes: Classical CVRP optimization using Google OR-Tools Mathematical formulation of the routing problem Transformation of the optimization problem into a Quadratic Unconstrained Binary Optimization (QUBO) model Conversion of the QUBO formulation into an Ising Hamiltonian Implementation of the Quantum Approximate Optimization Algorithm (QAOA) using Qiskit Classical versus quantum performance comparison Route visualization and benchmarking Modular Python code designed for experimentation and future extensions The project is intended as a foundation for exploring applications of Quantum Computing, Operations Research, and Hybrid Quantum-Classical Optimization in real-world routing and logistics problems. It provides a reproducible environment for understanding optimization workflows, evaluating quantum algorithms, and extending the framework toward more complex scenarios such as dynamic vehicle routing and emergency ambulance dispatch. Keywords: Quantum Computing, Quantum Optimization, QAOA, QUBO, Ising Model, Capacitated Vehicle Routing Problem (CVRP), Operations Research, OR-Tools, Qiskit, Combinatorial Optimization, Hybrid Quantum-Classical Algorithms. This software was developed as part of a research internship focused on quantum optimization and serves as a learning and experimentation platform for future research.
Introduction Finding the most efficient routes for a fleet of delivery vehicles remains a critical and costly challenge for nearly any logistics business. This core idea is known as the Vehicle Routing Problem (VRP). The primary goal is to minimize operational costs, such as the total travel distance or the number of trucks deployed, while ensuring all the customers are served. Because VRP is NP-hard, finding a perfect solution is often impossible, forcing industries to rely on classical approximate algorithms. However, quantum variational algorithms offer a new paradigm by iteratively optimizing parameters to navigate the solution space, presenting a new and promising avenue for finding better and faster solutions. Methods In this paper, we introduce Symmetric Arc Reduction in Quantum Approximate Optimization Algorithm (SAR-QAOA), which systematically eliminates redundant symmetric routing variables in the binary integer programming formulation prior to the Quadratic Unconstrained Binary Optimization (QUBO) formulation. The proposed SAR-QAOA encodes edge-based VRP while reducing the qubit requirement from n ( n −1) to n ( n −1)/2, thereby improving the resource efficiency of the QUBO formulation by prioritizing regions of the solution space that are more likely to contain high-quality solutions; SAR enhances both search accuracy and computational efficiency. Results Experimental results on noiseless quantum simulators validate the feasibility of the proposed formulation and its integration with the QAOA framework, providing a promising foundation for future investigations on larger routing problems and evolving quantum hardware.
This study introduces a hybrid quantum-classical approach to solving the Capacitated Vehicle Routing Problems (CVRP), combining the Column Generation method and the Quantum Alternating Operator Ansatz (QAOAnsatz). The column generation method divides the problem into a master problem and subproblems to effectively solve the problem. We solved the subproblem by using QAOAnsatz to enhance the optimal solution search. Moreover, we generated the problem Hamiltonian using an Augmented Lagrangian-inspired Method to reduce the number of required qubits to handle the inequality. As a result, our experiments obtained an optimal solution for a CVRP problem with 6 customers. This study demonstrates a practical quantum application in logistics and sets a new technique for hybrid quantum-classical optimization frameworks.