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.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00004978 |
| Date | 12 July 1996 |
| Creators | Bouali, Djawad |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0133 seconds