Multi-Neighborhood Search for Combinatorial Optimization

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.