mlsanityData to 14 Oct 2026

New Adaptive Mechanism for Large Neighborhood Search using Dual Actor-Critic

arXiv 2601.11414 ↗First posted 16 Jan 2026cs.GT cs.LGcited by 1

On the map: Deep reinforcement learning methods → RL for games and combinatorial optimization

Abstract (arXiv)

Adaptive Large Neighborhood Search (ALNS) is a widely used heuristic method for solving combinatorial optimization problems. ALNS explores the solution space by iteratively using destroy and repair operators with probabilities, which are adjusted by an adaptive mechanism to find optimal solutions. However, the classic ALNS adaptive mechanism does not consider the interaction between destroy and repair operators when selecting them. To overcome this limitation, this study proposes a novel adaptive mechanism. This mechanism enhances the adaptability of the algorithm through a Dual Actor-Critic (DAC) model, which fully considers the fact that the quality of new solutions is jointly determined by the destroy and repair operators. It effectively utilizes the interaction between these operators during the weight adjustment process, greatly improving the adaptability of the ALNS algorithm. In this mechanism, the destroy and repair processes are modeled as independent Markov Decision Processes to guide the selection of operators more accurately. Furthermore, we use Graph Neural Networks to extract key features from problem instances and perform effective aggregation and normalization to enhance the algorithm's transferability to different sizes and characteristics of problems. Through a series of experiments, we demonstrate that the proposed DAC-ALNS algorithm significantly improves solution efficiency and exhibits excellent transferability.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods. Builds on 6 of its 31 references that are in the map. First posted on arXiv 16 Jan 2026.

Builds on

6 of 31 references.

References · 6

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 333
  3. 2022A2C is a special case of PPOcited by 16
  4. 2022Online Control of Adaptive Large Neighborhood Search using Deep Reinforcement Learningcited by 6
  5. 2018The Electric Two-echelon Vehicle Routing Problemcited by 4
  6. 2023Graph Reinforcement Learning for Operator Selection in the ALNS Metaheuristiccited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026SPO: Discovering Adaptive Large Neighborhood Search Operators via Stackelberg Program Optimizationcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2021Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs
  2. 2026DRAGON: LLM-Driven Decomposition and Reconstruction Agents for Large-Scale Combinatorial Optimization
  3. 2025HyP-ASO: A Hybrid Policy-based Adaptive Search Optimization Framework for Large-Scale Integer Linear Programs
  4. 2026Reinforcement Learning Methods for Neighborhood Selection in Local Search
  5. 2024Toward Automated Algorithm Design: A Survey and Practical Guide to Meta-Black-Box-Optimization
  6. 2024Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective
  7. 2025ASAP: Exploiting the Satisficing Generalization Edge in Neural Combinatorial Optimization
  8. 2023COMBHelper: A Neural Approach to Reduce Search Space for Graph Combinatorial Problems