Self-adapting LNS minimizing expected time to improvement, applied to the vehicle routing problem

Large Neighbourhood Search (LNS) has been used successfully to solve many optimization problems. LNS proceeds by successive relaxations and reconstructions of an initial solution. One natural extension to LNS consists in Adaptive LNS, a process in which the relaxations and reconstructions methods are adapted or changed during the search. This allows the search to naturally diversify more and try different heuristics. But few such methods have been investigated in the literature. This thesis will explore the existing methods and possible frameworks for an adaptive mechanism, as well as propose a statistically-founded selection meta-heuristic and several implementations to test this meta-heuristic, called ALNS-TTI. To test and evaluate this adaptive LNS mechanism, we will apply it to several variants of the Vehicle Routing Problem. We will see that ALNS-TTI, within the specific framework proposed in this thesis, performs better than a random selection procedure but fails to outperform the best existing methods.