# Large Neighborhood Search based on Neural Construction Heuristics

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 10 references that are in the map.
- First posted on arXiv 2 May 2022.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/1911.09539/) (2019)
- [Learning to Solve Vehicle Routing Problems with Time Windows through Joint Attention](https://mlsanity.com/paper/2006.09100/) (2020)

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

- [Graph Reinforcement Learning for Operator Selection in the ALNS Metaheuristic](https://mlsanity.com/paper/2302.14678/) (2023)
- [Large Neighborhood Search meets Iterative Neural Constraint Heuristics](https://mlsanity.com/paper/2603.20801/) (2026)
- [SPO: Discovering Adaptive Large Neighborhood Search Operators via Stackelberg Program Optimization](https://mlsanity.com/paper/2609.31179/) (2026)

## Abstract (arXiv)

We propose a Large Neighborhood Search (LNS) approach utilizing a learned construction heuristic based on neural networks as repair operator to solve the vehicle routing problem with time windows (VRPTW). Our method uses graph neural networks to encode the problem and auto-regressively decodes a solution and is trained with reinforcement learning on the construction task without requiring any labels for supervision. The neural repair operator is combined with a local search routine, heuristic destruction operators and a selection procedure applied to a small population to arrive at a sophisticated solution approach. The key idea is to use the learned model to re-construct the partially destructed solution and to introduce randomness via the destruction heuristics (or the stochastic policy itself) to effectively explore a large neighborhood.