# Dynamic Partial Removal: A Neural Network Heuristic for Large Neighborhood Search

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 May 2020.

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

- [Analytics and Machine Learning in Vehicle Routing Research](https://mlsanity.com/paper/2102.10012/) (2021)
- [An Overview and Experimental Study of Learning-based Optimization Algorithms for Vehicle Routing Problem](https://mlsanity.com/paper/2107.07076/) (2021)
- [Solve routing problems with a residual edge-graph attention neural network](https://mlsanity.com/paper/2105.02730/) (2021)
- [Learning to Solve Multiple-TSP with Time Window and Rejections via Deep Reinforcement Learning](https://mlsanity.com/paper/2209.06094/) (2022)
- [Online Control of Adaptive Large Neighborhood Search using Deep Reinforcement Learning](https://mlsanity.com/paper/2211.00759/) (2022)
- [Hybrid Pointer Networks for Traveling Salesman Problems Optimization](https://mlsanity.com/paper/2110.03104/) (2021)
- [Combining Constructive and Perturbative Deep Learning Algorithms for the Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/2211.13922/) (2022)
- [Learning to Search for Vehicle Routing with Multiple Time Windows](https://mlsanity.com/paper/2505.23098/) (2025)
- [SPO: Discovering Adaptive Large Neighborhood Search Operators via Stackelberg Program Optimization](https://mlsanity.com/paper/2609.31179/) (2026)

## Abstract (arXiv)

This paper presents a novel neural network design that learns the heuristic for Large Neighborhood Search (LNS). LNS consists of a destroy operator and a repair operator that specify a way to carry out the neighborhood search to solve the Combinatorial Optimization problems. The proposed approach in this paper applies a Hierarchical Recurrent Graph Convolutional Network (HRGCN) as a LNS heuristic, namely Dynamic Partial Removal, with the advantage of adaptive destruction and the potential to search across a large scale, as well as the context-awareness in both spatial and temporal perspective. This model is generalized as an efficient heuristic approach to different combinatorial optimization problems, especially to the problems with relatively tight constraints. We apply this model to vehicle routing problem (VRP) in this paper as an example. The experimental results show that this approach outperforms the traditional LNS heuristics on the same problem as well. The source code is available at hrefhttps://github.com/water-mirror/DPRhttps://github.com/water-mirror/DPR.