Scientific Program > Talks by Speaker > Gauthier Jean Bertrand

Defining rich neighborhoods while maintaining efficient marginal updates of intermediate solutions plays a key role in producing successful heuristics. The sequential search paradigm has proven to be a worthy competitor to the lexicographic search paradigm when tackling single depot vehicle routing problems. The lexicographic search produces a search tree of a neighborhood by expanding move possibilities across the lexicographic ordering of edges contained in the current solution. As the possibilities are explored, segments of path tested for the gain criterion are longer by construction. The idea of the lexicographic search is that once infeasibility is observed, the longer routes remaining in the exploration must also be infeasible and the search can be halted. In contrast, the sequential search halts the exploration of the search tree via a distance sorted neighbor list such that the gain criterion is utilized during the local search. In both cases, the search tree is therefore explored exhaustively although the sequential search is more malleable when it comes to incorporating gain criterion goals because the latter is innately part of the paradigm. The seminal paper is used as a starting point for the multi-depot vehicle routing problem study. The behavior of both search paradigms is studied on classical moves such as 2-opt, 3-opt, or-opt, string exchange, swap and relocation. The analysis is based on benchmark instances from the literature.