décembre 2018
          01 02
03 04 05 06 07 08 09
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30

Partager cet événement

Enregistrer cet événement

Séminaire du GERAD : Sequential search for the multi-depot vehicle routing problem

Mardi 13 février 2018
Débute à 10:45


Marilyne Lavoie
Site Web

2920, chemin de la Tour
Montréal, QC Canada
H3T 1N8

514 343-6111
Site Web | Itinéraire et carte


Consulté 599 fois
Séminaire du GERAD : Sequential search for the multi-depot vehicle routing problem

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!

© École Polytechnique de Montréal
Bottin | Plan du site | Recherche | Conditions | Besoin d'aide?