Séminaire

Le 2 Février 2011, au LIPN, à 12:30, Prof. Gilbert Laporte (CIRRELT Montreal et HEC Chaire de recherche du Canada en distributique)

Titre : Le problème du voyageur de commerce : des origines à aujourd’hui


Résumé : Le problème du voyageur de commerce (PVC) consiste à déterminer un cycle ou un circuit hamiltonien de longueur minimale dans un graphe. Il s’agit sans aucun doute du problème d’optimisation combinatoire le plus célèbre. Dans cette présentation, je ferai un survol de l’histoire de ce problème dont les premières applications documentées datent peut-être du XVIIIe siécle. Je présenterai les principaux modèles et algorithmes proposés pour le PVC, en commençant par les travaux de Dantzig, Fulkerson et Johnson (1954) et en terminant par Concorde (Applegate et al., 2006) et son application à la résolution exacte d’une instance de 85,900 sommets (Applegate et al., 2009).


Evénement

Le 14 Juin 2011, au IHP

Journée Group Logistique et Transport