Bonjour Mon ami et voila l'enace du probleme voyageur de comerce:
I/ Définition du problème
On traitera le cas euclidien (les distances entre sommets sont euclidiennes). Etant donné un graphe non orienté, des distances euclidiennes sur les arêtes, trouver le circuit hamiltonien de somme des distances minimale.
Exemple (il sera utilisé pour la mise au point des programmes):
12 villes.
Sommets extrêmités des arêtes, distance :
1 2 3; 1 4 11; 1 5 3; 2 5 4; 2 8 4; 2 10 5; 3 7 3; 3 10 3; 3 11 1; 4 7 2; 4 9 3 ; 4 12 4; 5 8 8; 6 8 2; 6 10 1; 6 11 3; 7 9 4; 7 12 3; 8 10 2; 9 12 2; 11 12 6.
II/ Modèle linéaire
variables de décision : les sommets i et j sont ils voisins? Si oui, xij =1. sinon, xij = 0 (attention à la symétrie : une seule variable par arête).
Contraintes : tout sommet a exactement 2 voisins.
Objectif : f(x) = somme des distances des arêtes choisies.
III/ Utilisation du format model de glpk pour écrire ce modèle linéaire du PVC.
Voir doc de glpk.
IV/ Evaluation, Séparation
Vérifiez l'existence de sous tours dans la solution trouvée par programmation linéaire. Si S est un sous ensemble de solutions, la valeur de la solution trouvée est donc une évaluation par défaut de f sur S: g(S).
Quelles contraintes ajouter pour éliminer tous les sous-tours possibles? Combien y en a t'il?
Méthode de Séparation basée sur l'existence d'un sous tour: Soit un sous tour constitué de k arêtes a1, ...,ak. Toute solution du PVC doit avoir au moins une de ces variables à 0. Comme il est souhaitable que les sous ensembles de solution soient disjoints, il ne suffit pas d'annuler une variable par branche. Une solution consiste à opter pour une séparation asymétrique:
branche 1 : on ne prend pas a1
branche 2 : on prend a1 mais pas a2
branche 3 : on prend a1 et a2 mais pas a3
etc...
branche k : on prend a1, ...a(k-1) mais pas ak.
Montrez que les sous-ensembles ainsi obtenus forment bien une partition de l'ensemble de départ.
Tout n'est pas résolu pour autant. Il reste en particulier à choisir le sous-tour (il y en a forcément plusieurs par solution irréalisable). Dans l'algorithme générique SEP, le moment où l'évaluation est faite peut changer. Vous choisirez d'évaluer un noeud de l'arborescence des sous-ensemble de solution dès sa construction (c'est à dire dès la phase de séparation du noeud « père »). Enfin, il y a aussi le choix du noeud sur lequel séparer. Vous choisirez votre méthode. La plus simple est la recherche arborescente « en profondeur », mais elle peut avoir des inconvénients. Lesquels? Un compromis souvent efficace consiste à choisir parmi les derniers noeuds créés (issus d'un même père) celui de meilleure évaluation.
V/ Mise en oeuvre avec GLPK.
Note préliminaire : il existe toujours une solution optimale entière des PL rencontrés. Cependant il se peut que GLPK nous donne une solution fractionnaire également optimale. Pour éviter cela, on pourra déclarer dans le modèle les variables comme binaires. Ceci conduira GLPK à faire, de temps en temps, une courte recherche arborescente pour trouver une solution entière.
a) Effectuez la résolution « à la main » sur de petits exemples :
utilisation de glpsol pour l'évaluation
récupération de la solution à partir du fichier résultat de glpsol. choix d'un sous-tour
modification du PL en éditant le fichier de départ pour chaque branche issue de la séparation.
b) Écrivez un programme qui :
1.
INIT :
1.
entre les données du problème à partir de Graphstream, crée un fichier model
2.
éventuellement fixe la valeur de l'évaluation par excès fbar
2.
EVAL : appelle GLPK sur le PL courant, récupère la valeur et les variables non nulles
3.
SEPAR :
1.
détecte les sous-tours s'ils existent (sinon stérilise le noeud et met à jour fbar), en choisis un
2.
pour chaque noeud issu de la séparation, rajoute automatiquement au PL courant les fixations de variables correspondantes.
4.
CHOIX : choisit le noeud sur lequel séparer, suivant la méthode choisie
5.
conserve les données nécessaires de chaque noeud pendant de l'arborescence.
Rappel : un noeud de l'arborescence peut être : stérile (ne peut contenir de solution optimale, ou sa meilleure solution est connue) ; pendant : il n'a pas encore fait l'objet d'une séparation ; traité : il a été évalué et séparé. Seuls les noeuds pendants sont conservés.
Note : L'algorithme est simple dans son principe. Faites attention aux détails techniques. Par exemple, le lien entre les variables du PL tel qu'il est enregistré par GLPK et les arêtes du graphe initial (indispensable pour détecter les sous-tours). Egalement, les infos à conserver pour un noeud pendant, et bien sûr la gestion correcte de l'ensemble des noeuds pendants.
VI/ Interprétation des résultats
Il s'agit de comparer les résultats obtenus avec ceux obtenus par diverses heuristiques.
La méthode « à la main » n'est utilisable que pour des graphes de petite taille (une dizaine de sommets). Au delà, la méthode doit être stoppée (par exemple après avoir évalué NbP noeuds pendants, où NbP est de l'ordre de 10 ou 20).
La méthode utilisant les routines de GLPK permet de traiter de plus grands graphes, mais il n'est pas certain qu'elle permette de résoudre des problèmes de la TSPLIB. Le mieux est de fixer là encore une limite pour NbP, mais cette limite peut être de quelques milliers (on peut aussi fixer un temps maximum, par exemple 15 minutes).
Si avant cette limite, une solution optimale a été trouvée, on peut directement la comparer avec la solution trouvée par heuristique : écart absolu, écart relatif, temps de résolution pour les deux méthodes.
Sinon, la méthode SEP doit retourner une borne min (comment la calculer dans ce cas?) et une borne max (valeur courante de fbar), qui peuvent être comparées avec la valeur trouvée par la ou les heuristiques.
Enfin, pour accélérer la résolution (ou pour améliorer la meilleure solution trouvée jusque là), on peut utiliser la meilleure valeur trouvée par heuristique pour initialiser fbar (partie INIT de l'algorithme SEP).
Comment creer site internet commercial
