Abstract FR:

Le problème du voyageur de commerce, note TSP, consiste à trouver un parcours de longueur minimum que doit emprunter un voyageur pour visiter une et une seule fois chaque ville s'il démarre de la ville de son domicile et y revient en fin de parcours. Dans ce mémoire, nous étudions une généralisation de ce problème. Si on regroupe les villes par pays, on s'intéresse a un parcours de longueur minimum qui visite une et une seule ville de chaque pays. Cette généralisation est ainsi appelée problème du voyageur de commerce international, note ITSP.