We formulate capacitated vehicle routing as a colored permutation problem: each of the K vehicles selects a disjoint partial permutation, and the sum of these K submatrices forms a full n × n permutation matrix that assigns everycustomer to exactly one visit position. This representation requires no explicit load register (and hence no extra qubits) beyondthe routing variables. In contrast, prior quantum encodings introduce an explicit capacity/load representation with O(Q) or O(log Q) additional qubits for capacity Q [1, 2]. Our construction is designed to satisfy the kernel requirement of the Constraint-Enhanced QAOA (CE-QAOA) framework [3], making the resulting VRP instances compatible with its feasibility- and finite-shot guarantees [4, 5]. On the full benchmark suite of [6], our p = 1 CE–QAOA implementation recovers the certified optimum for every instance, without decomposition. All results are fully reproducible from the companion artifact archive in Ref. [7].
We formulate capacitated vehicle routing as a colored permutation problem: each of the K vehicles selects a disjoint partial permutation, and the sum of these K submatrices forms a full n × n permutation matrix that assigns everycustomer to exactly one visit position. This representation requires no explicit load register (and hence no extra qubits) beyondthe routing variables. In contrast, prior quantum encodings introduce an explicit capacity/load representation with O(Q) or O(log Q) additional qubits for capacity Q [1, 2]. Our construction is designed to satisfy the kernel requirement of the Constraint-Enhanced QAOA (CE-QAOA) framework [3], making the resulting VRP instances compatible with its feasibility- and finite-shot guarantees [4, 5]. On the full benchmark suite of [6], our p = 1 CE–QAOA implementation recovers the certified optimum for every instance, without decomposition. All results are fully reproducible from the companion artifact archive in Ref. [7].
Abstract We formulate a global-position colored-permutation encoding for the capacitated vehicle routing problem. Each of the K vehicles selects a disjoint partial permutation, and the sum of these K color layers forms a full n × n permutation matrix that assigns every customer to exactly one visit position. On the benchmark suite of [1], our end-to-end pipeline recovers the independently verified optima. This representation uses n2K binary decision variables arranged as K color layers over a common permutation structure, while vehicle capacities are enforced by weighted sums over the entries of each color class—requiring no explicit load register, and hence no extra logical qubits, beyond the routing variables. In contrast, prior quantum encodings introduce an explicit capacity/load representation with O(Q) or O(logQ) additional qubits for capacity Q [2, 3, 4, 5]. Our construction is designed to exploit the Constraint-Enhanced QAOA (CE-QAOA) framework [6] together with its encoded-manifold analyses [6, 7, 8]. Building on our recent requirements analysis of quantum utility in CVRP [9], we develop a routing optimization formulation that directly targets one of the main near-term bottlenecks, namely the additional logical-qubit cost of vehicle labels and explicit capacity constraints. Our proposal shows strong algorithmic performance in addition to qubit efficiency. All results are fully reproducible from the companion artifact archive in Ref. [10]. The feasibility oracle introduced in Alg. 3 may also be of independent interest as a reusable polynomial-time decoding and certification primitive for quantum and quantum-inspired routing pipelines.1
We formulate a global-position colored-permutation encoding for the capacitated vehicle routing problem. Each of the K vehicles selects a disjoint partial permutation, and the sum of these K color layers forms a full n×n permutation matrix that assigns every customer to exactly one visit position. This representation uses n2K binary decision variables arranged as K color layers over a common permutation structure, while vehicle capacities are enforced by weighted sums over the entries of each color class, requiring no explicit load register and hence no extra logical qubits beyond the routing variables. In contrast, many prior quantum encodings introduce an explicit capacity or load representation with additional qubits. Our construction is designed to exploit the Constraint-Enhanced QAOA framework together with its encoded-manifold analyses. Building on a requirements-based view of quantum utility in CVRP, we develop a routing optimization formulation that directly targets one of the main near-term bottlenecks, namely the additional logical-qubit cost of vehicle labels and explicit capacity constraints. Our proposal shows strong algorithmic performance in addition to qubit efficiency. On a standard benchmark suite, our end-to-end pipeline recovers the independently verified optima. The feasibility oracle may also be of independent interest as a reusable polynomial-time decoding and certification primitive for quantum and quantum-inspired routing pipelines.
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.
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.
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.