Dans ce mémoire, nous présentons une méthode de résolution du problème de tournées de véhicules grâce à une approche polyèdrale. Un état de l'art est fait sur la connaissance du polyèdre correspondant aux solutions de ce probleme et de nouvelles inégalités valides (et induisant des facettes) sont présentées pour ce polyèdre. Nous décrivons ensuite des heuristiques pour la séparation des contraintes les plus importantes ainsi qu'un algorithme de "Branchement et Coupe" qui nous permet d'améliorer les résultats connus pour la résolution exacte du problème de tournées.

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.