A New Adaptation Mechanism of the ALNS Algorithm Using Reinforcement Learning

Hajar Boualamia (), Abdelmoutalib Metrane (), Imad Hafidi () and Oumaima Mellouli ()
Additional contact information
Hajar Boualamia: University Sultan Moulay Slimane
Abdelmoutalib Metrane: Cadi Ayyad University
Imad Hafidi: University Sultan Moulay Slimane
Oumaima Mellouli: University Sultan Moulay Slimane

SN Operations Research Forum, 2025, vol. 6, issue 3, 1-26

Abstract: Abstract 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.

Keywords: Capacitated vehicle routing problem; Adaptive large neighborhood search; Reinforcement learning; Q-learning; Operator selection (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s43069-025-00513-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:snopef:v:6:y:2025:i:3:d:10.1007_s43069-025-00513-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/43069

DOI: 10.1007/s43069-025-00513-1

Access Statistics for this article

SN Operations Research Forum is currently edited by Marco Lübbecke

More articles in SN Operations Research Forum from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().