Retour aux activités
Séminaire du GERAD

Sequential search for the multi-depot vehicle routing problem


13 fév. 2018   10h45 — 12h00

Jean-Bertrand Gauthier Université Johannes Gutenberg de Mayence, Allemagne

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!

Jacques Desrosiers responsable


Salle 4488
Pavillon André-Aisenstadt
Campus de l'Université de Montréal
2920, chemin de la Tour Montréal QC H3T 1J4 Canada

Axes de recherche

Application de recherche