Probleme voyageur de commerce

Bonjour
merci d'abord pour votre repense; en fait c'est un TP . j'ai chercher dans google et j'ai trouver des codes sources pour ce probleme mais franchement je veux comprendre le probleme voyageur de commerce et faire un truc personel.
et pour ca je veux montrer l'existence d'une tell solution teheorique par la methode exacte (branch and bound) puis je veux implementer ma solution par un prog java .pour une autre solutions aussi heuristique je veux travailler avec la methode tabou de trouver une solution au depart et d'essayer a chaque fois d'ameliorer ma sollution.
bon pour la premier methode om peut formalisé le probleme comme suit:
soit G un graphe non oriente de l"esembles (1.....n)des sommets les villes et les arets se sont les trajets entre les viles; il s'ait de trouver un cycle hamiltonien de cout minimun (le cout est la distance entre deux ville adjacentes i et j est c[i,j]).
on a:
- i voisin de j implique que x(i;j) egal a 1 et sinon 0
- sum{k in 1..i-1,j in i+1..12} X[k,i]+sum{i in V, j in V}X[i,j]=2;
- fuction objectif a mimiser est sum{i in V, j in V} c[i,j]*x[i,j];
voila je me suit areter la.

merci d"avance de m'aider

Ton Msg:
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.
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).

Commentaires:

1) Etant donné un graphe non orienté ! dans ce cas on a un graphe non orienté donc il s'agiet de trouver un Cycle Hamiltonien et non pas un cercuit hamiltonien ;

2) tu veux aussi vérifier l'existance de sous-tours? tu veux dire quoi par sous-tours !!! tu parle d'un sous cycle ou quoi!!! la je pense que tu cherche la contrainte qui assure que le sous graphe trouver (solution) soit connexe et passe par tous les sommets ???

il faut bien comprendre les définitions suivantes:

A) Graphe /Cycle Hamiltonien : On dit qu'un graphe possède un cycle hamiltonien s'il existe un cycle passant une, et une seule fois, par chaque sommet => Un cycle hamiltonien d'un graphe G est un cycle élémentaire passant par tous les sommets de G. Un graphe est hamiltonien s'il possède un cycle hamiltonien comme sous-graphe.

B)Problème de voyageur de commerce PVC: étant donné un ensemble de villes séparées par des distances données, à trouver le plus court chemin qui relie toutes les villes.

pourrais-tu me donner l'enancé exacte (text complet sans modéfication) de ton problème :-)

on va aller step by step mon frère

Salutations;

« Il y a 10 types de personnes dans le mode, ceux qui comprennent l logique et les autres. »

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).