Titre :  Sequential search for the multi-depot vehicle routing problem

Conférencier : Jean-Bertrand Gauthier – HEC Montréal, Canada

Defining rich neighborhoods while maintaining fast and efficient searches of these neighborhoods 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. Given a particular search branch, as the possibilities are explored, segments of path tested for the largest gain 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 branch can be pruned. 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 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, or-opt, string exchange, swap, and relocation. The analysis is based on benchmark instances from the literature.

---

Entrée gratuite.
Bienvenue à tous!