Quantum Routing Simplifies Vehicle Planning

Scientists Chinonso Onah and Kristel Michielsen at the Department of Physics present a qubit-efficient encoding using coloured-permutations, sharply reducing the number of logical qubits required to be compared to many existing quantum formulations. The method avoids explicit load registers by integrating vehicle capacities directly into the permutation structure, streamlining the optimisation process. The team’s pipeline achieves independently verified optimal solutions on standard benchmark tests and offers a reusable decoding primitive for both quantum and quantum-inspired routing applications.

Quantum encoding streamlines vehicle routing for larger problem sizes

Benchmark instances of the capacitated vehicle routing problem, with up to eight locations for two vehicles, are now solved. This exceeds the previous limit of five locations achievable with existing quantum methods. A new coloured-permutation encoding represents delivery routes using a permutation matrix, assigning each customer to a unique visit position. This approach streamlines calculations by integrating vehicle capacities directly into the permutation structure.

The capacitated vehicle routing problem (CVRP) is a fundamental challenge in logistics and operations research, involving the design of optimal routes for a fleet of vehicles to serve a set of customers with known demands, subject to vehicle capacity constraints. Traditionally, solving the CVRP, particularly for large-scale instances, requires substantial computational resources. Existing quantum algorithms for the CVRP often suffer from high qubit requirements, limiting their scalability. This new method addresses this limitation through a novel encoding scheme. The coloured-permutation encoding represents a route as an $n \times n$ permutation matrix, where $n$ is the number of customers. Each vehicle is assigned a ‘colour’, and the matrix is constructed such that each customer is visited by exactly one vehicle. The $K$ vehicles each select a disjoint partial permutation, and the sum of these $K$ colour layers forms a full permutation matrix. This representation utilises $n^2K$ binary decision variables arranged as $K$ colour layers over a common permutation structure. Crucially, vehicle capacities are enforced by weighted sums over the elements of the permutation matrix, eliminating the need for auxiliary qubits to track vehicle loads.

Unlike many prior quantum encodings, the method avoids needing additional logical qubits to represent vehicle loads, sharply reducing computational resources. A major advance in solving complex delivery problems using quantum computing techniques has been achieved. Beyond solving instances with up to eight locations and two vehicles, the method successfully tackled benchmarks previously intractable for existing quantum methods. The ‘coloured-permutation’ encoding integrates vehicle capacity directly into the computational structure, avoiding the need for extra qubits to track vehicle loads. Furthermore, the new approach uses a ‘feasibility oracle’, a reusable set of tools for verifying solutions, and operates within the Constraint-Enhanced QAOA framework, streamlining calculations. Analytical mechanisms detailed in accompanying documentation confirm the positive-filtering process underpinning the success, and the team’s pipeline independently verified optimal solutions on standard benchmark suites. The feasibility oracle is particularly valuable as it allows for efficient validation of candidate solutions, a critical step in quantum optimisation algorithms. This reusability extends the applicability of the work beyond purely quantum computation, potentially benefiting classical heuristic algorithms as well.

Constraint-Enhanced QAOA and the need for symbol-respecting mixers in delivery route optimisation

Optimising deliveries while respecting vehicle limits in the capacitated vehicle routing problem has long demanded significant computational power. This new qubit-efficient encoding offers a promising route towards tackling increasingly complex logistical challenges, but its current success hinges on a specific framework: Constraint-Enhanced QAOA. The authors acknowledge that fully realising quantum advantage requires not just algorithmic refinement, but also the development of ‘symbol-respecting mixers’. These are key for preserving the beneficial active dynamics within the QAOA framework and represent a vital area for further investigation.

The Quantum Approximate Optimisation Algorithm (QAOA) is a hybrid quantum-classical algorithm designed for solving combinatorial optimisation problems. Constraint-Enhanced QAOA builds upon this framework by incorporating problem-specific constraints directly into the quantum circuit, improving performance and solution quality. However, the effectiveness of QAOA, and particularly its constrained variants, is heavily dependent on the choice of ‘mixers’. Mixers are unitary operators that evolve the quantum state during the algorithm, and their design significantly impacts the algorithm’s ability to explore the solution space effectively. ‘Symbol-respecting mixers’ are a specific type of mixer designed to preserve the feasibility of solutions throughout the optimisation process, preventing the algorithm from getting stuck in invalid regions of the search space. Developing such mixers is a non-trivial task and remains an active area of research. The current implementation relies on carefully crafted mixers tailored to the coloured-permutation encoding, but generalising these mixers to other problem instances presents a significant challenge.

Representing routes as a permutation matrix, assigning each delivery to a unique position, streamlines calculations with this new encoding method for the capacitated vehicle routing problem. Vehicle capacity is integrated directly into the permutation structure using weighted sums, rather than requiring additional qubits to track vehicle loads, a common limitation in previous quantum approaches. This qubit efficiency enabled the team to independently verify optimal solutions on standard benchmark tests, exceeding prior limits of five locations. The resulting feasibility oracle offers a reusable component for both quantum and conventional routing applications. The implications of this work extend beyond simply increasing the size of solvable instances. By reducing the qubit overhead, this encoding brings quantum solutions to the CVRP closer to practical implementation on near-term quantum devices. Furthermore, the reusable feasibility oracle and the insights gained from the analytical mechanisms could inform the development of more efficient classical heuristics for solving the CVRP, bridging the gap between quantum and classical optimisation techniques.

The researchers developed a new method for encoding the capacitated vehicle routing problem, representing routes as a permutation matrix with up to five locations. This approach efficiently integrates vehicle capacity directly into the encoding, reducing the number of qubits needed compared to many previous quantum methods. The resulting framework successfully recovered independently verified optimal solutions on standard benchmark tests, demonstrating strong algorithmic performance. Additionally, the team created a reusable feasibility oracle that could benefit both quantum and classical routing pipelines.