Solving Capacitated Vehicle Routing Problem with Quantum Alternating Operator Ansatz and Column Generation

• URL: http://arxiv.org/abs/2503.17051v1
• Date: Fri, 21 Mar 2025 11:09:48 GMT
• Title: Solving Capacitated Vehicle Routing Problem with Quantum Alternating Operator Ansatz and Column Generation
• Authors: Wei-hao Huang, Hiromichi Matsuyama, Yu Yamashiro,
• Abstract summary: This study proposes a hybrid quantum-classical approach to solving the Capacitated Vehicle Routing Problem (CVRP)<n>It integrates the Column Generation (CG) method with the Quantum Alternating Operator Ansatz (QAOAnsatz)<n> Experimental results on small-scale CVRP instances show that QAOAnsatz converges more quickly to optimal routes than the standard QAOA approach.
• Score: 1.474723404975345
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This study proposes a hybrid quantum-classical approach to solving the Capacitated Vehicle Routing Problem (CVRP) by integrating the Column Generation (CG) method with the Quantum Alternating Operator Ansatz (QAOAnsatz). The CG method divides the CVRP into the reduced master problem, which finds the best combination of the routes under the route set, and one or more subproblems, which generate the routes that would be beneficial to add to the route set. This method is iteratively refined by adding new routes identified via subproblems and continues until no improving route can be found. We leverage the QAOAnsatz to solve the subproblems. Our algorithm restricts the search space by designing the QAOAnsatz mixer Hamiltonian to enforce one-hot constraints. Moreover, to handle capacity constraints in QAOAnsatz, we employ an Augmented Lagrangian-inspired method that obviates the need for additional slack variables, reducing the required number of qubits. Experimental results on small-scale CVRP instances (up to 6 customers) show that QAOAnsatz converges more quickly to optimal routes than the standard QAOA approach, demonstrating the potential of this hybrid framework in tackling real-world logistical optimization problems on near-term quantum hardware.

Related papers

• Efficient Neural Combinatorial Optimization Solver for the Min-max Heterogeneous Capacitated Vehicle Routing Problem [44.53289422887474]
  Existing NCO solvers typically select a vehicle and its next node to visit at each decoding step, but often make myopic decoding decisions and overlook key properties of MMHCVRP.<n>To better address these limitations, we propose ECHO, an efficient NCO solver.<n>ECHO outperforms state-of-the-art NCO solvers across varying numbers of vehicles and nodes, and exhibits well-performing generalization across both scales and distribution patterns.
  arXiv  Detail & Related papers  (2025-07-28T23:38:33Z)
• Decentralized Optimization on Compact Submanifolds by Quantized Riemannian Gradient Tracking [45.147301546565316]
  This paper considers the problem of decentralized optimization on compact submanifolds.<n>We propose an algorithm where agents update variables using quantized variables.<n>To the best of our knowledge, this is the first algorithm to achieve an $mathcalO (1/K)$ convergence rate in the presence of quantization.
  arXiv  Detail & Related papers  (2025-06-09T01:57:25Z)
• QUEST: QUantum-Enhanced Shared Transportation [0.3749861135832073]
  We present textbfQUEST (Quantum-Enhanced Shared Transportation)<n>We formulate the pairing of windbreakers and windsurfers as a mixed-integer quadratic problem (MIQP)<n>We verify the solution classically via the Hungarian Algorithm, a Gurobi-based solver, and brute-force enumeration of binary vectors.<n>Our quantum implementation successfully recovers the optimal assignment identified by the classical methods.
  arXiv  Detail & Related papers  (2025-05-12T21:19:19Z)
• Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction [44.67050228129961]
  We present a Transformer-based framework for Constraint Satisfaction Problems (CSPs) CSPs find use in many applications and thus accelerating their solution with machine learning is of wide interest. We propose ConsFormer, a self-supervised framework that leverages a Transformer as a solution refiner.
  arXiv  Detail & Related papers  (2025-02-18T16:51:01Z)
• Solving Drone Routing Problems with Quantum Computing: A Hybrid Approach Combining Quantum Annealing and Gate-Based Paradigms [34.4581898633922]
  The proposed method, coined Quantum for Drone Routing (Q4DR), integrates the two most prominent paradigms in the field.<n>The efficacy of Q4DR is demonstrated through three use cases of increasing complexity.
  arXiv  Detail & Related papers  (2025-01-30T15:38:40Z)
• Digitized Counterdiabatic Quantum Algorithms for Logistics Scheduling [33.04597339860113]
  We propose digitized counterdiabatic quantum optimization (DCQO)algorithms for two scheduling problems.<n>For the job-shop scheduling problem, we aim at finding the optimal schedule for a robot executing a number of tasks under specific constraints.<n>For the traveling salesperson problem, the goal is to find the path that covers all cities and is associated with the shortest traveling distance.
  arXiv  Detail & Related papers  (2024-05-24T16:53:30Z)
• Improving Quantum and Classical Decomposition Methods for Vehicle Routing [2.4646794072984477]
  We propose an elaborate combination of two decomposition methods, namely graph shrinking and circuit cutting. Our results offer insights into the performance of algorithms for optimization problems within the constraints of current quantum technology.
  arXiv  Detail & Related papers  (2024-04-08T14:19:25Z)
• Graph-controlled Permutation Mixers in QAOA for the Flexible Job-Shop Problem [0.0]
  The Quantum Alternating Operator Ansatz provides an algorithmic framework for constrained, optimization solutions. As opposed to the better known standard QAOA protocol, the constraints of the optimization problem are built into the mixing layers of the ansatz circuit. We develop mixing operators for a wide range of scheduling problems including the flexible job shop problem.
  arXiv  Detail & Related papers  (2023-11-07T16:16:52Z)
• A Feasibility-Preserved Quantum Approximate Solver for the Capacitated Vehicle Routing Problem [3.0567007573383678]
  The Capacitated Vehicle Routing Problem (CVRP) is an NP-optimization problem (NPO) that arises in various fields including transportation and logistics. We present a new binary encoding for the CVRP, with an objective function of minimizing the shortest path that bypasses the vehicle capacity constraint of the CVRP. We discuss the effectiveness of the proposed encoding under the framework of the variant of the Quantum Alternating Operator Ansatz.
  arXiv  Detail & Related papers  (2023-08-17T05:14:43Z)
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
  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.
  arXiv  Detail & Related papers  (2023-06-14T13:44:35Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity. We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree. These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
  arXiv  Detail & Related papers  (2022-01-06T21:02:30Z)
• Applying quantum approximate optimization to the heterogeneous vehicle routing problem [0.7503129292751939]
  We investigate the potential use of a quantum computer to find approximate solutions to the heterogeneous vehicle routing problem. We find that the number of qubits needed for this mapping scales quadratically with the number of customers.
  arXiv  Detail & Related papers  (2021-10-13T15:38:25Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Low-Rank Sinkhorn Factorization [45.87981728307819]
  We introduce an explicit factorization of low rank couplings as a product of textitsub-coupling factors linked by a common marginal. We prove the non-asymptotic stationary convergence of this algorithm and illustrate its efficiency on benchmark experiments.
  arXiv  Detail & Related papers  (2021-03-08T13:18:45Z)
• A Quantum Annealing Approach for Dynamic Multi-Depot Capacitated Vehicle Routing Problem [5.057312718525522]
  This paper presents a quantum computing algorithm that works on the principle of Adiabatic Quantum Computation (AQC) It has shown significant computational advantages in solving optimization problems such as vehicle routing problems (VRP) when compared to classical algorithms. This is an NP-hard optimization problem with real-world applications in the fields of transportation, logistics, and supply chain management.
  arXiv  Detail & Related papers  (2020-05-26T01:47:39Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.