Hybrid Learning and Optimization methods for solving Capacitated Vehicle Routing Problem

Monit Sharma, Hoong Chuin Lau · 2025

Read Hybrid Learning and Optimization methods for solving Capacitated Vehicle Routing Problem by Monit Sharma, Hoong Chuin Lau (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-15262.txt.

Introduction

Monit Sharma and Hoong Chuin Lau let a learning agent tune a classical logistics solver in a 2025 operations research paper. The capacitated vehicle routing problem asks how a fleet with limited loads should serve customers at minimum cost, and it is NP-hard. Augmented Lagrangian solvers perform well only when their penalty parameters are tuned carefully, a chore that resists automation.

Their hybrid wraps deep reinforcement learning around the solver: a soft actor-critic agent reads instance features and constraint violations, then sets penalty values on the fly. Two solver variants are tested, a classical one and a quantum-enhanced one whose subproblems become binary optimization problems solved by a variational quantum eigensolver. On synthetic and benchmark instances, the learned tuning beats hand-tuned penalties with fewer iterations, and the agent optimizes feasibility and cost jointly.

Catalog record

CREATORMonit Sharma, Hoong Chuin Lau
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE69 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-15262

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Hybrid Learning and Optimization methods for solving Capacitated Vehicle Routing Problem Monit Sharma, Hoong Chuin Lau Abstract The Capacitated Vehicle Routing Problem (CVRP) is a fundamental NP-hard problem in logistics. Augmented Lagrangian Methods (ALM) for solving CVRP performance depends heavily on well-tuned penalty parameters. In this paper, we propose a hybrid optimization approach that integrates deep reinforcement learning (RL) to automate the selection of penalty parameter values within both classical (RL-C-ALM) and quantum-enhanced (RL-Q-ALM) ALM solvers. Using Soft Actor-Critic, our approach learns penalty values from CVRP instance features and constraint violations. In RL-Q-ALM, subproblems are encoded as QUBOs and solved using Variational Quantum Eigensolvers (VQE). The agent learns across episodes by maximizing solution feasibility and minimizing cost. Experiments show that RL-C-ALM outperforms manually tuned ALM on synthetic and benchmark CVRP instances, achieving better solutions with fewer iterations. Also, RL-Q-ALM matches classical solution quality on small instances but incurs higher runtimes due to quantum overhead. Our results highlight the potential of combining RL with classical and quantum solvers for scalable, adaptive combinatorial optimization 1 1 1 Code available at: https://github.com/SMU-Quantum/adaptive_quantum_cvrp . 1 Introduction The Capacitated Vehicle Routing Problem (CVRP) is a canonical problem in combinatorial optimization, with extensive applications across logistics, transportation, and supply chain design [ 1 ] . Given a set of geographically distributed customers and a fleet of identical-capacity vehicles, the objective is to determine a set of vehicle routes, each starting and ending at a central depot, such that each customer is visited exactly once, vehicle capacities are not exceeded, and the total cost, typically the aggregate travel distance, is minimized [ 2 , 3 ] . Despite decades of algorithmic development, CVRP remains computationally challenging due to its combinatorial structure and NP-hardness [ 4 ] . Exact approaches, such as branch-and-cut, quickly become impractical as the number of customers grows [ 5 , 6 ] , while heuristic and metaheuristic methods provide tractable approximations at the expense of optimality guarantees [ 7 , 8 ] . Recent years have seen the emergence of data-driven methods, including reinforcement learning (RL), for solving routing problems by learning instance-aware heuristics [ 9 , 10 ] . In parallel, quantum optimization, via variational quantum algorithms and quantum annealing, has been proposed as a future-facing paradigm for solving hard discrete problems [ 11 ] , albeit currently limited by hardware constraints [ 12 ] . In this work, we explore the integration of RL and quantum optimization within a classical optimization framework based on the Augmented Lagrangian Method (ALM) [ 13 , 14 ] . We propose and systematically evaluate four solvers for CVRP: • C-ALM: a classical ALM approach adapted for CVRP, handling routing and capacity constraints via Lagrangian multipliers and penalty terms; • RL-C-ALM: an RL-guided ALM where a learned policy selects penalty parameters to accelerate convergence and improve solution quality; • Q-ALM: a quantum-enhanced ALM wherein subproblems are mapped to QUBOs and solved via the Variational Quantum Eigensolver (VQE) [ 15 ] ; • RL-Q-ALM: a novel fusion of RL and quantum solvers, where RL selects parameters for a quantum-powered ALM loop. This study benchmarks these paradigms on synthetic and standard CVRP datasets [ 16 ] , assessing solution quality, feasibility, convergence, and scalability. Our contributions provide insights into the comparative utility of RL and quantum components, and establish a robust framework for hybrid optimization under realistic constraints. 1.1 The Capacitated Vehicle Routing Problem Let V=\{0,1,\dots,n\} denote the set of nodes, where 0 is the depot and \{1,\dots,n\} are customers. Each customer i\in\{1,\dots,n\} has a nonnegative demand d_{i} , and each of the |K| vehicles has identical capacity Q . The travel cost between nodes i and j is denoted c_{ij} . A feasible CVRP solution comprises a set of routes such that: 1. Each customer is visited exactly once by a single vehicle; 2. Each vehicle starts and ends at the depot; 3. The total demand on each route does not exceed Q . The objective is to minimize the total cost of all vehicle routes. We present a three-index vehicle-flow ILP formulation with Miller-Tucker-Zemlin (MTZ) subtour elimination constraints, following [ 1 ] . Decision variables. x_{ijk}=\begin{cases}1&\text{if vehicle }k\text{ travels from node }i\text{ to node }j,\\ 0&\text{otherwise}\end{cases}\quad\forall i,j\in V,i\neq j,\forall k\in K u_{ik}=\text{cumulative load on vehicle }k\text{ just after visiting customer }i,\quad\forall i\in\{1,\dots,n\},\forall k\in K Objective. \min\sum_{k\in K}\sum_{i\in V}\sum_{\begin{subarray}{c}j\in V\\ j\neq i\end{subarray}}c_{ij}x_{ijk} Constraints. (Customer visit) \displaystyle\quad\sum_{k\in K}\sum_{\begin{subarray}{c}i\in V\\ i\neq j\end{subarray}}x_{ijk}=1, \displaystyle\forall j\in\{1,\dots,n\} (1) (Depot depart) \displaystyle\quad\sum_{j=1}^{n}x_{0jk}=1, \displaystyle\forall k\in K (2) (Depot return) \displaystyle\quad\sum_{i=1}^{n}x_{i0k}=1, \displaystyle\forall k\in K (3) (Flow conservation) \displaystyle\quad\sum_{\begin{subarray}{c}i\in V\\ i\neq j\end{subarray}}x_{ijk}=\sum_{\begin{subarray}{c}l\in V\\ l\neq j\end{subarray}}x_{jlk}, \displaystyle\forall j\in\{1,\dots,n\},\forall k\in K (4) (Capacity) \displaystyle\quad\sum_{i=1}^{n}d_{i}\sum_{\begin{subarray}{c}j\in V\\ j\neq i\end{subarray}}x_{ijk}\leq Q, \displaystyle\forall k\in K (5) (MTZ subtour elimination) \displaystyle\quad u_{ik}+d_{j}\leq u_{jk}+Q(1-x_{ijk}), \displaystyle\forall i,j\in\{1,\dots,n\},i\neq j,\forall k\in K (6) \displaystyle\quad d_{i}\leq u_{ik}\leq Q, \displaystyle\forall i\in\{1,\dots,n\},\forall k\in K (7) \displaystyle\quad u_{ik}\geq d_{i}\sum_{j=0}^{n}x_{jik}, \displaystyle\forall i\in\{1,\dots,n\},\forall k\in K (8) Constraint ( 6 ) enforces that if vehicle k travels from i to j , then the load at j must be at least the load at i plus j ’s demand. Constraint ( 7 ) bounds the load variables, and ( 8 ) ensures that u_{ik} is activated only if customer i is visited by vehicle k . Together, these eliminate disconnected subtours as well as enforce vehicle capacity along routes. Strictly speaking therefore, constraint ( 5 ) is redundant; however it can still be useful to tighten the LP relaxation. Domain. x_{ijk}\in\{0,1\},\quad\forall i,j\in V,i\neq j,\forall k\in K;\quad u_{ik}\in\mathbb{R}_{+},\quad\forall i\in\{1,\dots,n\},\forall k\in K Complexity. The CVRP is strongly NP-hard [ 4 ] . Its search space grows factorially with the number of customers and combinatorially with the number of vehicles. As a result, exact algorithms become computationally intractable for instances beyond moderate sizes (e.g., n\geq 50 ), motivating the need for approximation, learning-based, and hybrid strategies. While this paper focuses on the canonical single-depot CVRP for clarity and benchmarking, the problem is part of a broader family of VRPs, including Time Windows (VRPTW) [ 17 ] , Multiple Depots (MDVRP) [ 18 ] , and Split Deliveries (SDVRP) [ 19 ] . Advances in solving the base CVRP often transfer to these richer variants, providing foundational tools for real-world logistics optimization. 1.2 Hybrid Solvers for the Capacitated Vehicle Routing Problem This paper investigates four distinct paradigms for solving the Capacitated Vehicle Routing Problem (CVRP), emphasizing a rigorous comparative evaluation under a unified experimental framework. The approaches differ in their computational foundations, ranging from classical optimization to quantum computing, and offer insights into the capabilities and limitations of emerging hybrid solvers. 1. Classical Augmented Lagrangian Method (C-ALM): A deterministic, penalty-based optimization approach that formulates CVRP as a constrained problem and employs augmented Lagrangian techniques to enforce routing and capacity constraints. 2. Quantum-Augmented Lagrangian Method (Q-ALM): A hybrid algorithm that retains the classical ALM framework but replaces the subproblem solver with quantum optimization. Specifically, each routing subproblem is reformulated as a Quadratic Unconstrained Binary Optimization (QUBO) instance and solved using quantum variational algorithms such as the Variational Quantum Eigensolver (VQE) [ 20 ] or the Quantum Approximate Optimization Algorithm (QAOA) [ 21 ] . 3. Reinforcement Learning–Tuned Classical ALM (RL-C-ALM): A learning-augmented solver in which a deep RL agent learns to adjust penalty parameters and Lagrange multipliers for ALM.

Read the complete text