Return to search

Heuristiques et approche polyedrale du probleme de voyageur de commerce international

Le probleme du voyageur de commerce, note TSP, consiste a trouver un parcours de longueur minimum que doit emprunter un voyageur pour visiter une et une seule fois chaque ville s'il demarre de la ville de son domicile et y revient en fin de parcours. Dans cette these, nous etudions une generalisation de ce probleme. Si on regroupe les villes par pays, on s'interesse a un parcours de longueur minimum qui visite une et une seule ville de chaque pays. Cette generalisation est ainsi appelee probleme du voyageur de commerce international, note ITSP. Le ITSP est un probleme NP-difficile. Dans une premiere partie, nous decrivons des heuristiques pour le ITSP et nous evaluons numeriquement une nouvelle heuristique pour le TSP basee sur des notions introduites par Glover. Nous decrivons une reduction polynomiale du ITSP au TSP et nous donnons une nouvelle formulation du ITSP en un programme lineaire en nombres entiers. La deuxieme partie est reservee a l'approche de resolution polyedrale. Nous definissons la relaxation graphique du ITSP et nous donnons des resultats sur la dimension et la structure faciale du polyedre associe. Nous etudions la relation polyedrale qui existe entre le ITSP et sa relaxation graphique et nous introduisons plusieurs classes de facettes du polytope du ITSP. L'etude polyedrale du ITSP nous a permis de developper un algorithme de branchement et de coupe pour sa resolution. Nous presentons des heuristiques et des algorithmes exacts pour la separation de certaines classes de facettes et nous donnons les principales modifications qu'il faut apporter a un algorithme de branchement et de coupe pour le TSP afin d'obtenir un tel algoritme pour le ITSP. Nous finissons cette etude en donnant quelques resultats numeriques et une anlyse de l'implantation que nous avons realisee.

Identiferoai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00004978
Date12 July 1996
CreatorsBouali, Djawad
Source SetsCCSD theses-EN-ligne, France
LanguageFrench
Detected LanguageFrench
TypePhD thesis

Page generated in 0.0014 seconds