A Deep Reinforcement Learning-based Large Neighborhood Search for Capacitated Vehicle Routing Problems

Large Neighborhood Search (LNS) is a widely used metaheuristic for solving complex combinatorial optimization problems, iteratively destroying and repairing parts of the solution to explore promising regions. In this paper, we introduce LNS-RL, an extension of LNS that enhances the search process by integrating a Deep Reinforcement Learning-based destroy operator. Our approach employs a Graph Attention Network (GAT) to capture spatial relationships among nodes and routes, trained using Proximal Policy Optimization (PPO). Experiments on Capacitated Vehicle Routing Problem (CVRP) benchmarks show that LNS-RL outperforms traditional LNS methods and surpasses state-of-the-art learning-based LNS approaches. Notably, incorporating route-level metrics into LNS-RL yields greater improvements compared to using node features alone. These results highlight the effectiveness of attention mechanisms and reinforcement learning, as well as the benefits of simultaneously integrating route- and node-level knowledge in LNS, which enhances information propagation during the search process, leading to more impactful destroy operator in complex routing problems.