Vous trouverez ici le corrigé du TP sur le problème du voyageur de commerce.

Le fichier "instance_pvc.txt" contient les données relatives à l’instance traitée, ici une ville de 6 sommets dont les distances sont indiquées dans la matrice "d" (avec la convention que d[i,j] vaut 1000 si l’arête entre les villes i et j n’existe pas).

Le fichier "modele_pour_instance_pvc.mod" contient une modélisation par les arêtes du problème de voyageur de commerce, mais comme le modèle devrait contenir toutes les contraintes interdisant les sous-tours (il y en a un nombre exponentiel), ce modèle n’est valable que pour l’instance présentée pour laquelle il suffit d’interdire le sous-tour 1-2-3-1.

Pour lancer la résolution avec glpk, la syntaxe est :

glpsol —model modele_pour_instance_pvc.mod —data instance_pvc.txt