# Learning to Solve Vehicle Routing Problems: A Survey

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 58 of its 120 references that are in the map.
- First posted on arXiv 5 May 2022.

## Builds on (most cited first, 30 of 58)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Prioritized Experience Replay](https://mlsanity.com/paper/1511.05952/) (2015)
- [Counterfactual Multi-Agent Policy Gradients](https://mlsanity.com/paper/1705.08926/) (2017)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [Learning to Perform Local Rewriting for Combinatorial Optimization](https://mlsanity.com/paper/1810.00337/) (2018)
- [A Survey and Critique of Multiagent Deep Reinforcement Learning](https://mlsanity.com/paper/1810.05587/) (2018)
- [Learning Improvement Heuristics for Solving Routing Problems](https://mlsanity.com/paper/1912.05784/) (2019)
- [Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances](https://mlsanity.com/paper/2012.10658/) (2020)
- [Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observability](https://mlsanity.com/paper/1703.06182/) (2017)
- [Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/1911.09539/) (2019)
- [Strong mixed-integer programming formulations for trained neural networks](https://mlsanity.com/paper/1811.08359/) (2018)
- [Learning to Delegate for Large-scale Vehicle Routing](https://mlsanity.com/paper/2107.04139/) (2021)
- [Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer](https://mlsanity.com/paper/2110.02544/) (2021)
- [NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem](https://mlsanity.com/paper/2110.07983/) (2021)
- [Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning](https://mlsanity.com/paper/2004.01608/) (2020)

## Built on by (most cited first, 16 of 16)

- [GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-time](https://mlsanity.com/paper/2312.08224/) (2023)
- [DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization](https://mlsanity.com/paper/2309.14032/) (2023)
- [RouteFinder: Towards Foundation Models for Vehicle Routing Problems](https://mlsanity.com/paper/2406.15007/) (2024)
- [Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvement](https://mlsanity.com/paper/2403.15180/) (2024)
- [CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention](https://mlsanity.com/paper/2412.00346/) (2024)
- [AlphaRouter: Quantum Circuit Routing with Reinforcement Learning and Tree Search](https://mlsanity.com/paper/2410.05115/) (2024)
- [Routing Arena: A Benchmark Suite for Neural Routing Solvers](https://mlsanity.com/paper/2310.04140/) (2023)
- [A Neural Separation Algorithm for the Rounded Capacity Inequalities](https://mlsanity.com/paper/2306.17283/) (2023)
- [A Hierarchical Destroy and Repair Approach for Solving Very Large-Scale Travelling Salesman Problem](https://mlsanity.com/paper/2308.04639/) (2023)
- [Learning to repeatedly solve routing problems](https://mlsanity.com/paper/2212.08101/) (2022)
- [Reinforcement Learning for Solving the Pricing Problem in Column Generation: Applications to Vehicle Routing](https://mlsanity.com/paper/2504.02383/) (2025)
- [Pivoting Retail Supply Chain with Deep Generative Techniques: Taxonomy, Survey and Insights](https://mlsanity.com/paper/2403.00861/) (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)
- [A Coalition Game for On-demand Multi-modal 3D Automated Delivery System](https://mlsanity.com/paper/2412.17252/) (2024)
- [Graph Reduction with Unsupervised Learning in Column Generation: A Routing Application](https://mlsanity.com/paper/2504.08401/) (2025)
- [OPTIC-ER: A Reinforcement Learning Framework for Real-Time Emergency Response and Equitable Resource Allocation in Underserved African Communities](https://mlsanity.com/paper/2508.12943/) (2025)

## Abstract (arXiv)

This paper provides a systematic overview of machine learning methods applied to solve NP-hard Vehicle Routing Problems (VRPs). Recently, there has been a great interest from both machine learning and operations research communities to solve VRPs either by pure learning methods or by combining them with the traditional hand-crafted heuristics. We present the taxonomy of the studies for learning paradigms, solution structures, underlying models, and algorithms. We present in detail the results of the state-of-the-art methods demonstrating their competitiveness with the traditional methods. The paper outlines the future research directions to incorporate learning-based solutions to overcome the challenges of modern transportation systems.