Quantum optimization has recently drawn considerable attention as one of the possible applications of noisy intermediate-scale quantum computation, yet the problem of qubit requirement remains a major bottleneck when combinatorial optimization problems are converted into quantum circuits. This issue becomes especially critical in solving the capacitated vehicle routing problem (CVRP) with the quantum approximate optimization algorithm (QAOA), since the number of required qubits increases polynomially with respect to the number of nodes. This study investigates whether a heuristic divide-and-conquer strategy can be adapted to the quantum setting so as to improve qubit efficiency while preserving the optimization capability to a reasonable extent. The proposed method decomposes a single CVRP into multiple traveling salesman problems (TSPs) by the sweeping-based clustering method, searches for the sector configuration with the smallest angle sum by Grover’s search algorithm, and then solves each sector-wise TSP with the QAOA aided by the gravitational search algorithm. Experiments on five benchmark datasets show that the proposed approach attains feasible solutions within 3.4 to 12.7% of the reinforcement-learning baseline on the main test set. These results suggest that the proposed approach serves as a plausible quantum heuristic framework for constrained routing optimization, with the advantage of reducing the qubit burden by decomposing the original problem into smaller subproblems.
Quantum optimization has recently drawn considerable attention as one of the possible applications of noisy intermediate-scale quantum computation, yet the problem of qubit requirement remains a major bottleneck when combinatorial optimization problems are converted into quantum circuits. This issue becomes especially critical in solving the capacitated vehicle routing problem (CVRP) with the quantum approximate optimization algorithm (QAOA), since the number of required qubits increases polynomially with respect to the number of nodes. This study investigates whether a heuristic divide-and-conquer strategy can be adapted to the quantum setting so as to improve qubit efficiency while preserving the optimization capability to a reasonable extent. The proposed method decomposes a single CVRP into multiple traveling salesman problems (TSPs) by the sweeping-based clustering method, searches for the sector configuration with the smallest angle sum by Grover’s search algorithm, and then solves each sector-wise TSP with the QAOA aided by the gravitational search algorithm. Experiments on five benchmark datasets show that the proposed approach attains feasible solutions within 3.4 to 12.7% of the reinforcement-learning baseline on the main test set. These results suggest that the proposed approach serves as a plausible quantum heuristic framework for constrained routing optimization, with the advantage of reducing the qubit burden by decomposing the original problem into smaller subproblems.
Many relevant problems in industrial settings result in NP-hard optimization problems, such as the Capacitated Vehicle Routing Problem (CVRP) or its reduced variant, the Travelling Salesperson Problem (TSP). Even with today's most powerful classical algorithms, the CVRP is challenging to solve classically. Quantum computing may offer a way to improve the time to solution, although the question remains open as to whether Noisy Intermediate-Scale Quantum (NISQ) devices can achieve a practical advantage compared to classical heuristics. The most prominent algorithms proposed to solve combinatorial optimization problems in the NISQ era are the Quantum Approximate Optimization Algorithm (QAOA) and the more general Variational Quantum Eigensolver (VQE). However, implementing them in a way that reliably provides high-quality solutions is challenging, even for toy examples. In this work, we discuss decomposition and formulation aspects of the CVRP and propose an application-driven way to measure solution quality. Considering current hardware constraints, we reduce the CVRP to a clustering phase and a set of TSPs. For the TSP, we extensively test both QAOA and VQE and investigate the influence of various hyperparameters, such as the classical optimizer choice and strength of constraint penalization. Results of QAOA are generally of limited quality because the algorithm does not reach the energy threshold for feasible TSP solutions, even when considering various extensions such as recursive and constraint-preserving mixer QAOA. On the other hand, the VQE reaches the energy threshold and shows a better performance. Our work outlines the obstacles to quantum-assisted solutions for real-world optimization problems and proposes perspectives on how to overcome them.
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 computing (QC) is expected to solve incredibly difficult problems, including finding optimal solutions to combinatorial optimization problems. However, to date, QC alone is still far to demonstrate this capability except on small-sized problems. Hybrid approaches where QC and classical computing work together have shown the most potential for solving real-world scale problems. This work aims to show that we can enhance a classical optimization algorithm with QC so that it can overcome this limitation. We present a new hybrid quantum-classical tabu search (HQTS) algorithm to solve the capacitated vehicle routing problem (CVRP). Based on our prior work, HQTS leverages QC for routing within a classical tabu search framework. The quantum component formulates the traveling salesman problem (TSP) for each route as a QUBO, solved using D-Wave's Advantage system. Experiments investigate the impact of quantum routing frequency and starting solution methods. While different starting solution methods, including quantum-based and classical heuristics methods, it shows minimal overall impact. HQTS achieved optimal or near-optimal solutions for several CVRP problems, outperforming other hybrid CVRP algorithms and significantly reducing the optimality gap compared to preliminary research. The experimental results demonstrate that more frequent quantum routing improves solution quality and runtime. The findings highlight the potential of integrating QC within meta-heuristic frameworks for complex optimization in vehicle routing problems.
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 Traveling Salesman Problem (TSP) is a fundamental challenge in combinatorial optimization, widely applied in logistics and transportation. As the size of TSP instances grows, traditional algorithms often struggle to produce high-quality solutions within reasonable timeframes. This study investigates the potential of the Quantum Approximate Optimization Algorithm (QAOA), a hybrid quantum-classical method, to solve TSP under realistic constraints. We adopt a QUBO-based formulation of TSP that integrates real-world logistical constraints reflecting operational conditions, such as vehicle capacity, road accessibility, and time windows, while ensuring compatibility with the limitations of current quantum hardware. Our experiments are conducted in a simulated environment using high-performance computing (HPC) resources to assess QAOA's performance across different problem sizes and quantum circuit depths. In order to improve scalability, we propose clustering QAOA (Cl-QAOA), a hybrid approach combining classical machine learning with QAOA. This method decomposes large TSP instances into smaller sub-problems, making quantum optimization feasible even on devices with a limited number of qubits. The results offer a comprehensive evaluation of QAOA's strengths and limitations in solving constrained TSP scenarios. This study advances quantum optimization and lays groundwork for future large-scale applications.
Quantum computing (QC) is expected to solve incredibly difficult problems, including finding optimal solutions to combinatorial optimization problems. However, to date, QC alone has still been unable to demonstrate this capability except for small-sized problems. Hybrid approaches, where QC and classical computing work together, have shown the most potential for solving real-world-scale problems. This work aims to show that we can enhance a classical optimization algorithm with QC so that it can overcome this limitation. We present a new Hybrid Quantum-classical Tabu Search (HQTS) algorithm to solve the Capacitated Vehicle Routing Problem (CVRP). Based on our prior work, HQTS leverages QC for routing within a classical tabu search framework. The quantum component formulates the Traveling Salesman Problem (TSP) for each route as a Quadratic Unconstrained Binary Optimization (QUBO) and solves it using D-Wave’s Advantage system. Experiments investigate the impact of quantum routing frequency and starting solution methods. Across different starting solution methods, including quantum-based and classical heuristics, it shows minimal overall impact. HQTS achieved optimal or near-optimal solutions for several CVRP problems, outperforming other hybrid CVRP algorithms and significantly reducing the optimality gap relative to preliminary research. The experimental results demonstrate that more frequent quantum routing improves solution quality and runtime. The findings highlight the potential of integrating QC within meta-heuristic frameworks for complex optimization in vehicle routing problems.