Scholarlink

<p>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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

A New Adaptation Mechanism of the ALNS Algorithm Using Reinforcement Learning

  • 期刊论文

  • 发表日期：

    2025年7月30日

查看全文
  • Hajar Boualamia,
  • Abdelmoutalib Metrane,
  • Imad Hafidi,
  • Oumaima Mellouli

摘要

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.