Hybrid Learning and Optimization methods for solving Capacitated Vehicle Routing Problem

Monit Sharma, Hoong Chuin Lau

This paper, titled "Hybrid Learning and Optimization methods for solving Capacitated Vehicle Routing Problem," explores a cutting-edge intersection of classical optimization, deep reinforcement learning, and quantum computing.

TL;DR

The authors propose a hybrid framework that uses Reinforcement Learning (Soft Actor-Critic) to automatically tune the finicky penalty parameters of Augmented Lagrangian Methods (ALM). This approach significantly improves the efficiency and accuracy of solving the Capacitated Vehicle Routing Problem (CVRP) in both classical and quantum-enhanced settings.

What Problem Does This Paper Address?

The Capacitated Vehicle Routing Problem (CVRP) is a logistical nightmare. Imagine a fleet of trucks with limited capacity that must deliver goods to a set of customers and return to a central depot. The goal is to find the shortest possible routes while ensuring no truck is overloaded and every customer is visited exactly once. Because it is "NP-hard," the number of possible route combinations explodes as you add more customers, making it impossible to solve perfectly for large scales.

A common tool for this is the Augmented Lagrangian Method (ALM). ALM works by turning hard constraints (like "don't exceed truck capacity") into "penalties" added to the objective function. However, ALM is notoriously sensitive: if your penalty parameters are too low, the solver produces illegal routes; if they are too high, the solver becomes unstable or finds poor-quality solutions. Traditionally, these parameters require tedious manual tuning by experts for every new problem.

Methods

The researchers developed four distinct solvers to compare how different technologies handle the CVRP:

  1. C-ALM (Classical): The baseline. A standard ALM that uses heuristic rules to update penalties.
  2. RL-C-ALM (RL-Tuned Classical): Here, a Soft Actor-Critic (SAC) reinforcement learning agent is trained to look at the features of a specific CVRP instance (like customer density and demand variance) and predict the optimal starting penalty parameters.
  3. Q-ALM (Quantum-Enhanced): This replaces the classical subproblem solver with a Variational Quantum Eigensolver (VQE). The routing subproblem is translated into a QUBO (Quadratic Unconstrained Binary Optimization) format, which can be solved on quantum hardware or simulators.
  4. RL-Q-ALM (RL-Tuned Quantum): The "full hybrid" version, where the RL agent tunes the parameters for the quantum-powered solver.

The "secret sauce" is the RL agent’s reward function, which incentivizes finding feasible solutions that are as close as possible to the Best Known Solution (BKS) while penalizing long runtimes.

Datasets

The study evaluated the solvers across three tiers of data:

  • Light Instances: 50 custom-generated small problems (5–8 customers) designed to fit within the qubit limits of current quantum simulators.
  • Synthetic Medium-Scale: 35 larger instances (10–40 customers) used to test how well the classical RL-tuned version scales.
  • Standard CVRPLIB Benchmarks: 14 world-standard instances (like the "A" and "E" series) used in the optimization community to ensure the results are comparable to existing literature.

Key Insights and Ideas

  • Proactive vs. Reactive Tuning: Traditional ALM updates penalties during the optimization process (reactive). The authors found that "front-loading" the intelligence—having an RL agent pick the best starting values before the solver begins (proactive)—leads to much more stable and faster convergence.
  • Quantum Viability: The paper demonstrates that quantum-enhanced ALM is not just a theory; it can match classical solution quality on small-scale problems.
  • The "Aha" Moment on Feasibility: The RL agent learned that being "overly aggressive" with penalties can actually hurt feasibility. By balancing cost and constraint violations in the reward function, the agent discovered a "sweet spot" that human tuners often miss.

Key Results

  • Superior Accuracy: On synthetic datasets, RL-C-ALM outperformed the manually tuned version in 78% of instances.
  • Significant Gap Reduction: On the standard benchmark A-n33-k6, the RL-tuned solver reduced the optimality gap from 14.42% down to 4.98%.
  • Efficiency Gains: RL-C-ALM was generally faster, completing synthetic runs in an average of 775 seconds compared to 868 seconds for the baseline.
  • The Quantum Tax: While RL-Q-ALM achieved 98% optimality on small instances, it was significantly slower than classical methods (e.g., 166 seconds vs. <1 second) due to the overhead of simulating quantum circuits.

Limitations and Future Work

The primary limitation is quantum scalability. Current quantum simulators and hardware (NISQ devices) can only handle very small customer sets (up to ~8) before the "qubit footprint" becomes too large or the noise becomes overwhelming.

The authors suggest several paths forward:

  • Graph Neural Networks (GNNs): Using GNNs to allow the RL agent to better understand the spatial relationships between customers.
  • Hardware Deployment: Moving from simulators to actual noisy intermediate-scale quantum hardware to test error mitigation techniques.
  • Generalization: Testing if an RL agent trained on CVRP can "transfer" its knowledge to solve other routing variants, like those with time windows or multiple depots.

Summary updated

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.
BibTeX
@inproceedings{sharma2026hybrid,
  author = {Monit Sharma and Hoong Chuin Lau},
  title = {{Hybrid Learning and Optimization methods for solving Capacitated Vehicle Routing Problem}},
  booktitle = {QC+AI},
  year = {2026},
  doi = {10.1007/978-3-032-17625-7\_2},
}
Figure