# Neural Networks for Local Search and Crossover in Vehicle Routing: A Possible Overkill?

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 27 references that are in the map.
- First posted on arXiv 9 Sep 2022.

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

- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Learning to Perform Local Rewriting for Combinatorial Optimization](https://mlsanity.com/paper/1810.00337/) (2018)
- [Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhood](https://mlsanity.com/paper/2012.10384/) (2020)
- [NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem](https://mlsanity.com/paper/2110.07983/) (2021)
- [Deep Policy Dynamic Programming for Vehicle Routing Problems](https://mlsanity.com/paper/2102.11756/) (2021)
- [A concise guide to existing and emerging vehicle routing problem variants](https://mlsanity.com/paper/1906.06750/) (2019)

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

- [Cross-Problem Learning for Solving Vehicle Routing Problems](https://mlsanity.com/paper/2404.11677/) (2024)
- [Heuristics for Vehicle Routing Problem: A Survey and Recent Advances](https://mlsanity.com/paper/2303.04147/) (2023)
- [Probing Neural Combinatorial Optimization Models](https://mlsanity.com/paper/2510.22131/) (2025)
- [Graph-SCP: Accelerating Set Cover Problems with Graph Neural Networks](https://mlsanity.com/paper/2310.07979/) (2023)
- [Discovering new robust local search algorithms with neuro-evolution](https://mlsanity.com/paper/2501.04747/) (2025)
- [Study of Robust Features in Formulating Guidance for Heuristic Algorithms for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/2508.06129/) (2025)

## Abstract (arXiv)

Extensive research has been conducted, over recent years, on various ways of enhancing heuristic search for combinatorial optimization problems with machine learning algorithms. In this study, we investigate the use of predictions from graph neural networks (GNNs) in the form of heatmaps to improve the Hybrid Genetic Search (HGS), a state-of-the-art algorithm for the Capacitated Vehicle Routing Problem (CVRP). The crossover and local-search components of HGS are instrumental in finding improved solutions, yet these components essentially rely on simple greedy or random choices. It seems intuitive to attempt to incorporate additional knowledge at these levels. Throughout a vast experimental campaign on more than 10,000 problem instances, we show that exploiting more sophisticated strategies using measures of node relatedness (heatmaps, or simply distance) within these algorithmic components can significantly enhance performance. However, contrary to initial expectations, we also observed that heatmaps did not present significant advantages over simpler distance measures for these purposes. Therefore, we faced a common -- though rarely documented -- situation of overkill: GNNs can indeed improve performance on an important optimization task, but an ablation analysis demonstrated that simpler alternatives perform equally well.