# Graph Reinforcement Learning for Operator Selection in the ALNS Metaheuristic

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 27 references that are in the map.
- First posted on arXiv 28 Feb 2023.

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

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (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)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/1911.09539/) (2019)
- [Analytics and Machine Learning in Vehicle Routing Research](https://mlsanity.com/paper/2102.10012/) (2021)
- [Large Neighborhood Search based on Neural Construction Heuristics](https://mlsanity.com/paper/2205.00772/) (2022)

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

- [New Adaptive Mechanism for Large Neighborhood Search using Dual Actor-Critic](https://mlsanity.com/paper/2601.11414/) (2026)
- [RACL: Reasoning-Agent Control Layers for Continuous Metaheuristic Learning](https://mlsanity.com/paper/2606.20142/) (2026)
- [LLM-Guided Graph Generation for Structure-Based Local Improvement Methods](https://mlsanity.com/paper/2608.13333/) (2026)

## Abstract (arXiv)

ALNS is a popular metaheuristic with renowned efficiency in solving combinatorial optimisation problems. However, despite 16 years of intensive research into ALNS, whether the embedded adaptive layer can efficiently select operators to improve the incumbent remains an open question. In this work, we formulate the choice of operators as a Markov Decision Process, and propose a practical approach based on Deep Reinforcement Learning and Graph Neural Networks. The results show that our proposed method achieves better performance than the classic ALNS adaptive layer due to the choice of operator being conditioned on the current solution. We also discuss important considerations such as the size of the operator portfolio and the impact of the choice of operator scales. Notably, our approach can also save significant time and labour costs for handcrafting problem-specific operator portfolios.