CALENDRIER

décembre 2018
L M M J V S D
          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
31            

Partager cet événement

Enregistrer cet événement

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

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

Prix
gratuit

Contact
Marilyne Lavoie
Site Web

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

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

Catégories


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?