# Deep Reinforcement Learning for Solving the Heterogeneous Capacitated Vehicle Routing Problem

arXiv: https://arxiv.org/abs/2110.02629 · HTML: https://mlsanity.com/paper/2110.02629/

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 65 references that are in the map.
- First posted on arXiv 6 Oct 2021.

## Builds on (most cited first, 16 of 16)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [BERT4Rec: Sequential Recommendation with Bidirectional Encoder Representations from Transformer](https://mlsanity.com/paper/1904.06690/) (2019)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Order Matters: Sequence to sequence for sets](https://mlsanity.com/paper/1511.06391/) (2015)
- [Learning to Perform Local Rewriting for Combinatorial Optimization](https://mlsanity.com/paper/1810.00337/) (2018)
- [Learning Improvement Heuristics for Solving Routing Problems](https://mlsanity.com/paper/1912.05784/) (2019)
- [Behavior Sequence Transformer for E-commerce Recommendation in Alibaba](https://mlsanity.com/paper/1905.06874/) (2019)
- [Deep Reinforcement Learning for Multi-Agent Systems: A Review of Challenges, Solutions and Applications](https://mlsanity.com/paper/1812.11794/) (2018)
- [Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problems](https://mlsanity.com/paper/2012.10638/) (2020)
- [Multimodal Transformer with Multi-View Visual Representation for Image Captioning](https://mlsanity.com/paper/1905.07841/) (2019)
- [Deep Reinforcement Learning for Routing a Heterogeneous Fleet of Vehicles](https://mlsanity.com/paper/1912.03341/) (2019)

## Built on by (most cited first, 30 of 31)

- [Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt](https://mlsanity.com/paper/2310.18264/) (2023)
- [MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Experts](https://mlsanity.com/paper/2405.01029/) (2024)
- [Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillation](https://mlsanity.com/paper/2210.07686/) (2022)
- [Multi-Task Learning for Routing Problem with Cross-Problem Zero-Shot Generalization](https://mlsanity.com/paper/2402.16891/) (2024)
- [Learning Large Neighborhood Search Policy for Integer Programming](https://mlsanity.com/paper/2111.03466/) (2021)
- [Learning to Solve Routing Problems via Distributionally Robust Optimization](https://mlsanity.com/paper/2202.07241/) (2022)
- [Efficient Neural Neighborhood Search for Pickup and Delivery Problems](https://mlsanity.com/paper/2204.11399/) (2022)
- [Learning to Handle Complex Constraints for Vehicle Routing Problems](https://mlsanity.com/paper/2410.21066/) (2024)
- [Learning to Solve Vehicle Routing Problems: A Survey](https://mlsanity.com/paper/2205.02453/) (2022)
- [DL-DRL: A double-level deep reinforcement learning approach for large-scale task scheduling of multi-UAV](https://mlsanity.com/paper/2208.02447/) (2022)
- [Learning to Solve Multiple-TSP with Time Window and Rejections via Deep Reinforcement Learning](https://mlsanity.com/paper/2209.06094/) (2022)
- [URS: A Unified Neural Routing Solver for Cross-Problem Zero-Shot Generalization](https://mlsanity.com/paper/2509.23413/) (2025)
- [Neural Airport Ground Handling](https://mlsanity.com/paper/2303.02442/) (2023)
- [PARCO: Parallel AutoRegressive Models for Multi-Agent Combinatorial Optimization](https://mlsanity.com/paper/2409.03811/) (2024)
- [Learning for routing: A guided review of recent developments and future directions](https://mlsanity.com/paper/2507.00218/) (2025)
- [Efficient Neural Combinatorial Optimization Solver for the Min-max Heterogeneous Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/2507.21386/) (2025)
- [SPACE: Unifying Symmetric and Asymmetric Routing Problems for Generalist Neural Solver](https://mlsanity.com/paper/2605.24484/) (2026)
- [Deep Reinforcement Learning for Multi-Truck Vehicle Routing Problems with Multi-Leg Demand Routes](https://mlsanity.com/paper/2401.08669/) (2024)
- [DeepMDV: Global Spatial Matching for Multi-depot Vehicle Routing Problems](https://mlsanity.com/paper/2411.17080/) (2024)
- [Enhancing the Cross-Size Generalization for Solving Vehicle Routing Problems via Continual Learning](https://mlsanity.com/paper/2510.10262/) (2025)
- [Rethinking Constraint Awareness for Efficient State Embedding of Neural Routing Solver](https://mlsanity.com/paper/2605.10122/) (2026)
- [Baseline-Free Policy Optimization for Neural Combinatorial Optimization](https://mlsanity.com/paper/2606.10321/) (2026)
- [Playing hide and seek: tackling in-store picking operations while improving customer experience](https://mlsanity.com/paper/2301.02142/) (2023)
- [Multi-Start Team Orienteering Problem for UAS Mission Re-Planning with Data-Efficient Deep Reinforcement Learning](https://mlsanity.com/paper/2303.01963/) (2023)
- [Prioritized League Reinforcement Learning for Large-Scale Heterogeneous Multiagent Systems](https://mlsanity.com/paper/2403.18057/) (2024)
- [Learn to Solve Vehicle Routing Problems ASAP: A Neural Optimization Approach for Time-Constrained Vehicle Routing Problems with Finite Vehicle Fleet](https://mlsanity.com/paper/2411.04777/) (2024)
- [Multi-Action Self-Improvement for Neural Combinatorial Optimization](https://mlsanity.com/paper/2510.12273/) (2025)
- [Deep Reinforcement Learning for Solving the Fleet Size and Mix Vehicle Routing Problem](https://mlsanity.com/paper/2512.24251/) (2025)
- [Critic-Free Deep Reinforcement Learning for Maritime Coverage Path Planning on Irregular Hexagonal Grids](https://mlsanity.com/paper/2603.28385/) (2026)
- [Vehicle-as-Prompt: A Unified Deep Reinforcement Learning Framework for Heterogeneous Fleet Vehicle Routing Problem](https://mlsanity.com/paper/2604.05195/) (2026)

## Abstract (arXiv)

Existing deep reinforcement learning (DRL) based methods for solving the capacitated vehicle routing problem (CVRP) intrinsically cope with homogeneous vehicle fleet, in which the fleet is assumed as repetitions of a single vehicle. Hence, their key to construct a solution solely lies in the selection of the next node (customer) to visit excluding the selection of vehicle. However, vehicles in real-world scenarios are likely to be heterogeneous with different characteristics that affect their capacity (or travel speed), rendering existing DRL methods less effective. In this paper, we tackle heterogeneous CVRP (HCVRP), where vehicles are mainly characterized by different capacities. We consider both min-max and min-sum objectives for HCVRP, which aim to minimize the longest or total travel time of the vehicle(s) in the fleet. To solve those problems, we propose a DRL method based on the attention mechanism with a vehicle selection decoder accounting for the heterogeneous fleet constraint and a node selection decoder accounting for the route construction, which learns to construct a solution by automatically selecting both a vehicle and a node for this vehicle at each step. Experimental results based on randomly generated instances show that, with desirable generalization to various problem sizes, our method outperforms the state-of-the-art DRL method and most of the conventional heuristics, and also delivers competitive performance against the state-of-the-art heuristic method, i.e., SISR. Additionally, the results of extended experiments demonstrate that our method is also able to solve CVRPLib instances with satisfactory performance.