A New Adaptation Mechanism of the ALNS Algorithm Using Reinforcement Learning

The Adaptive large neighborhood search (ALNS) has become a widely used strategy to solve various practical problems that are NP-hard. One of the challenges of this metaheuristic design is selecting operators and adjusting the parameters to fit a given objective. Our proposed work focuses on the selection of operators in the ALNS. The classical version of the ALNS chooses operators during the search process using the roulette wheel selection (RWS) mechanism. This mechanism is based on exploitation, while exploration is necessary due to the dynamic nature of evolutionary algorithms. To solve this problem, we provide in this paper an improved ALNS metaheuristic for the capacitated vehicle routing problem (CVRP) that ensures the balance between exploration and exploitation. The proposed method uses reinforcement learning, specifically the Q-learning algorithm instead of the RWS mechanism, to privilege the most successful operators. The Q-learning agent leverages the Q-Table to guide ALNS search agents, selecting operator pairs instead of separate choices per iteration, with updates via a reward-penalty mechanism. We apply the algorithm to 24 CVRP instances and 20 newly generated instances. According to parametric statistical tests, we approve that there is a significant improvement and that our method performs competitively with traditional ALNS while improving decision-making efficiency.