Frontiers in Artificial Intelligence

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

Jayaraja A, Senthil Kumaran U

Published Oct 1, 2026• 0 citations

Abstract

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.

DOI: 10.3389/frai.2026.1900887

Related papers

Reinforcement Learning based Quantum Approximate Optimization Algorithm for Vehicle Routing Problem.

Md. Aqib Aman, Fardin Azam Sakib

Reinforcement Learning–based Quantum Approximate Optimization Algorithm (QAOA-RL) is used to solve the Vehicle Routing Problem (VRP) by transforming it into a Quadratic Unconstrained Binary Optimization (QUBO) form. The RL agent learns to optimize QAOA parameters for better route selection. Results show that QAOA-RL achieves a lower total cost compared to exact ILP and heuristic Greedy Search methods. Although the training time is higher, the solution quality improves significantly for larger problem sizes. This study highlights QAOA-RL as a scalable and promising hybrid quantum–classical approach for real-world logistics optimization.

Transportation research procediaJan 1, 20260 citations

Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors

Ioannis D. Leonidas, Alexander Dukakis, Tan, Benjamin +1 more

The vehicle routing problem with time windows (VRPTW) is a common optimization problem faced within the logistics industry. In this work, we explore the use of a previously-introduced qubit encoding scheme to reduce the number of binary variables, to evaluate the effectiveness of NISQ devices when applied to industry relevant optimization problems. We apply a quantum variational approach to a testbed of multiple VRPTW instances ranging from 11 to 3964 routes. These intances were formulated as quadratic unconstrained binary optimization (QUBO) problems based on realistic shipping scenarios. We compare our results with standard binary-to-qubit mappings after executing on simulators as well as various quantum hardware platforms, including IBMQ, AWS (Rigetti), and IonQ. These results are benchmarked against the classical solver, Gurobi. Our approach can find approximate solutions to the VRPTW comparable to those obtained from quantum algorithms using the full encoding, despite the reduction in qubits required. These results suggest that using the encoding scheme to fit larger problem sizes into fewer qubits is a promising step in using NISQ devices to find approximate solutions for industry-based optimization problems, although additional resources are still required to eke out the performance from larger problem sizes.

arXiv:2306.08507Jun 14, 20231 citation

Potential Energy Savings from Quantum Computing-Based Route Optimization

Ayush Nadiger, Adriana Caraeni, Katie Schouten

We investigate the potential of the Quantum Approximate Optimization Algorithm (QAOA) for reducing energy consumption in route planning, a key challenge in logistics due to the NP-hard nature of the Traveling Salesman and Vehicle Routing Problems. By encoding route optimization as a Quadratic Unconstrained Binary Optimization (QUBO) problem and implementing QAOA circuits at depth p = 3-5 alongside classical baselines of Simulated Annealing (SA) and Genetic Algorithms (GA), we perform systematic benchmarks on Euclidean graphs of sizes N = 5, 10, and 20. Our results demonstrate that QAOA attains higher solution quality with approximation ratios of 0.953 (N = 5), 0.921 (N = 10), and 0.903 (N = 20), outperforming SA and GA by 2.7-4.4%. Wall-clock runtimes for QAOA are 2-3x faster than SA across all tested sizes, and energy consumption measurements reveal a three-order-of-magnitude reduction, remaining in the picojoule range versus nanojoules for classical methods. Translating these gains to real-world logistics suggests an 8.2% improvement in routing efficiency could save approximately 2.62 EJ of fuel annually in the U.S., avoiding nearly 1.94 x 10^8 tonnes of CO2 emissions. These findings highlight QAOA's promise as a fast, energy-efficient optimizer for sustainable logistics applications and underscore its potential role in next-generation fleet-management systems.

arXiv:2604.16718Apr 17, 20260 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.08785Quantum Information ProcessingJul 29, 202424 citations

Hybrid Quantum Reinforcement Learning with QAOA for Improved Vehicle Routing Optimization

T. Satyanarayana Murthy, B. Swathi Sowmya, Santhosh Voruganti +3 more

Vehicle Routing Problem (VRP) is one of the most complex NP-hard combinatorial optimization problem in transportation and logistics that requires a dynamic solution approach. In this paper we present a new hybrid approach that combines the Quantum Approximate Optimization Algorithm (QAOA) into the QRL policy network, instead of the usual variational layers, QAOA mixing and cost Hamiltonian layers. This enhancement enables the agent to exploit problem specific particular quantum correlations when learning policies, and so richer exploration of the routing solution space. The QAOA-augmented QRL framework shows quicker convergence in training and can tackle larger VRP instances that are beyond the reach of Grover's Adaptive Search (GAS) and Quantum Reinforcement Learning (QRL) approaches. Experiments on standard VRP instances demonstrate better solutions, fewer episodes to converge and good memory usage on near term quantum hardware simulators. These findings demonstrate QAOA- integrated QRL as a viable approach to scalable, high quality quantum-assisted combinatorial optimization.

arXiv:2605.01574May 2, 20260 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.01614May 2, 20253 citations