Multi-Neighborhood Search is based on the composition of multiple local search neighborhoods. With respect to a single neighborhood, it provides a better connectivity in the search space and gives access to different search patterns, while also reducing the risk of getting stuck in a particular region of the search space. In this thesis, we present a methodological approach to design Multi-Neighborhood Search methods under a stochastic framework. Neighborhoods are balanced through fixed rates and internal biases. We also investigate the use of reinforcement learning for the adaptive tuning of neighborhood rates. We discuss the interaction with the search space, the objective function and the metaheuristic that guides the search. We validate our approach on four challenging combinatorial problems spanning various domains: the Minimum Interefence Frequency Assignment Problem, the Sports Timetabling Problem, the Healthcare Routing and Scheduling Problem, and the Capacitated Dispersion Problem. To solve them, we design Multi-Neighborhood Search methods that utilize from three to six distinct neighborhoods each, some of them originally conceived. We use Simulated Annealing as the metaheuristic that guides the search. We compare our results on instances from benchmark datasets and we show that Multi-Neighborhood Search outperforms quite consistently the state-of-the-art methods from the literature. Furthermore, we demonstrate through experimental results on the Sports Timetabling Problem and the Examination Timetabling Problem that the method's robustness can be enhanced with reinforcement learning. Finally, we replicate the schemes from Multi-Neighborhood Search to the matheuristic Construct, Merge, Solve and Adapt (CMSA), including the use of reinforcement learning, to shape the Multi-Constructor CMSA, that we apply to the Maximum Disjoint Dominating Sets Problem. Moreover, we also employ CMSA to solve a real-world Bus Driver Scheduling Problem with complex break constraints.

Multi-Neighborhood Search is based on the composition of multiple local search neighborhoods. With respect to a single neighborhood, it provides a better connectivity in the search space and gives access to different search patterns, while also reducing the risk of getting stuck in a particular region of the search space. In this thesis, we present a methodological approach to design Multi-Neighborhood Search methods under a stochastic framework. Neighborhoods are balanced through fixed rates and internal biases. We also investigate the use of reinforcement learning for the adaptive tuning of neighborhood rates. We discuss the interaction with the search space, the objective function and the metaheuristic that guides the search. We validate our approach on four challenging combinatorial problems spanning various domains: the Minimum Interefence Frequency Assignment Problem, the Sports Timetabling Problem, the Healthcare Routing and Scheduling Problem, and the Capacitated Dispersion Problem. To solve them, we design Multi-Neighborhood Search methods that utilize from three to six distinct neighborhoods each, some of them originally conceived. We use Simulated Annealing as the metaheuristic that guides the search. We compare our results on instances from benchmark datasets and we show that Multi-Neighborhood Search outperforms quite consistently the state-of-the-art methods from the literature. Furthermore, we demonstrate through experimental results on the Sports Timetabling Problem and the Examination Timetabling Problem that the method's robustness can be enhanced with reinforcement learning. Finally, we replicate the schemes from Multi-Neighborhood Search to the matheuristic Construct, Merge, Solve and Adapt (CMSA), including the use of reinforcement learning, to shape the Multi-Constructor CMSA, that we apply to the Maximum Disjoint Dominating Sets Problem. Moreover, we also employ CMSA to solve a real-world Bus Driver Scheduling Problem with complex break constraints.

Multi-Neighborhood Search for Combinatorial Optimization

ROSATI, ROBERTO MARIA
2024

Abstract

Multi-Neighborhood Search is based on the composition of multiple local search neighborhoods. With respect to a single neighborhood, it provides a better connectivity in the search space and gives access to different search patterns, while also reducing the risk of getting stuck in a particular region of the search space. In this thesis, we present a methodological approach to design Multi-Neighborhood Search methods under a stochastic framework. Neighborhoods are balanced through fixed rates and internal biases. We also investigate the use of reinforcement learning for the adaptive tuning of neighborhood rates. We discuss the interaction with the search space, the objective function and the metaheuristic that guides the search. We validate our approach on four challenging combinatorial problems spanning various domains: the Minimum Interefence Frequency Assignment Problem, the Sports Timetabling Problem, the Healthcare Routing and Scheduling Problem, and the Capacitated Dispersion Problem. To solve them, we design Multi-Neighborhood Search methods that utilize from three to six distinct neighborhoods each, some of them originally conceived. We use Simulated Annealing as the metaheuristic that guides the search. We compare our results on instances from benchmark datasets and we show that Multi-Neighborhood Search outperforms quite consistently the state-of-the-art methods from the literature. Furthermore, we demonstrate through experimental results on the Sports Timetabling Problem and the Examination Timetabling Problem that the method's robustness can be enhanced with reinforcement learning. Finally, we replicate the schemes from Multi-Neighborhood Search to the matheuristic Construct, Merge, Solve and Adapt (CMSA), including the use of reinforcement learning, to shape the Multi-Constructor CMSA, that we apply to the Maximum Disjoint Dominating Sets Problem. Moreover, we also employ CMSA to solve a real-world Bus Driver Scheduling Problem with complex break constraints.
11-mar-2024
Inglese
Inglese
Multi-Neighborhood Search is based on the composition of multiple local search neighborhoods. With respect to a single neighborhood, it provides a better connectivity in the search space and gives access to different search patterns, while also reducing the risk of getting stuck in a particular region of the search space. In this thesis, we present a methodological approach to design Multi-Neighborhood Search methods under a stochastic framework. Neighborhoods are balanced through fixed rates and internal biases. We also investigate the use of reinforcement learning for the adaptive tuning of neighborhood rates. We discuss the interaction with the search space, the objective function and the metaheuristic that guides the search. We validate our approach on four challenging combinatorial problems spanning various domains: the Minimum Interefence Frequency Assignment Problem, the Sports Timetabling Problem, the Healthcare Routing and Scheduling Problem, and the Capacitated Dispersion Problem. To solve them, we design Multi-Neighborhood Search methods that utilize from three to six distinct neighborhoods each, some of them originally conceived. We use Simulated Annealing as the metaheuristic that guides the search. We compare our results on instances from benchmark datasets and we show that Multi-Neighborhood Search outperforms quite consistently the state-of-the-art methods from the literature. Furthermore, we demonstrate through experimental results on the Sports Timetabling Problem and the Examination Timetabling Problem that the method's robustness can be enhanced with reinforcement learning. Finally, we replicate the schemes from Multi-Neighborhood Search to the matheuristic Construct, Merge, Solve and Adapt (CMSA), including the use of reinforcement learning, to shape the Multi-Constructor CMSA, that we apply to the Maximum Disjoint Dominating Sets Problem. Moreover, we also employ CMSA to solve a real-world Bus Driver Scheduling Problem with complex break constraints.
Multi-Neighborhood; Local Search; Metaheuristics; Optimization
SCHAERF, Andrea
ESSENI, David
Università degli Studi di Udine
File in questo prodotto:
File Dimensione Formato  
Tesi_Rosati_2024-02-16.pdf

accesso aperto

Dimensione 12.08 MB
Formato Adobe PDF
12.08 MB Adobe PDF Visualizza/Apri

I documenti in UNITESI sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.14242/164709
Il codice NBN di questa tesi è URN:NBN:IT:UNIUD-164709