home	accès étudiants

Le problème du voyageur du commerce

GraphStream

GraphStream est un outil pour la modélisation, le traitement et la visualisation de graphes. Même si cet outil est orienté vers le traitement de graphes dynamiques, on peut l'utiliser pour des problèmes statiques, tels que le problème classique du voyageur de commerce (TSP). GraphStream est une bibliothèque de classes Java.

Pour instaler GraphStream :

1. Se rendre sur le site de GraphStream et télécharger GraphStream 0.4.2
2. Consulter la documentation en ligne
3. Modifier votre environnement (variable CLASSPATH ou options de projet Eclipse) de telle sorte que les classes de graphstream.jar soient accsessibles.

Instances

TSPLIB est une bibliothèque d'instances de TSP et problèmes similaires utilisées pour comparer les différents algorithmes de résolution. Nous avons choisi les instances suivantes de TSPLIB :

Les instances choisies sont euclidiennes, c-à-d chaque ville est un point sur le plan et la distance entre deux villes est la distance euclidienne entre les points correspondants (arrondie au nombre entier le plus proche). Cet archive contient les instances en format TSP et DGS. Le format TSP est documenté ici. Les fichiers DGS représentent des graphes complets, chaque sommet possède des attributs x et y (les coordonnées de la ville) et chaque arête possède un attribut length (la longueur).

Solution optimale de kroA100

Pour charger et visualiser une instance, on peut se servir du programme suivant  (on passe le nom du fichier dgs en argument de la ligne de commande):

import org.miv.graphstream.io.*;
import org.miv.graphstream.graph.*;

public class TestTSP
{  public static void main(String[] args) 
   {  Graph g = new CheckedGraph();  
      GraphReader gr = new GraphReaderDGS(g);
      try
      {  gr.begin(args[0]);
         while(gr.nextStep());
      }
      catch(Exception e)
      {  e.printStackTrace();
         return;
      }      
      g.display(false);	
   }
}

Si vous voulez tester autres instances de TSPLIB, vous pouvez utiliser le convertisseur TSPtoDGS.java. Utilisation :

export LANG=en_US
java TSPtoDGS fichier.tsp fichier.dgs

Attention : le programme marche uniquement pour des instances euclidiennes dans le plan (EDGE_WEIGHT_TYPE: EUC_2D).

Travail demandé

En gros, trouver une solution aussi bonne qu'on peut. Implémenter un algorithme de parcours itératif (descente multi-start, GRASP, recuit simulé ou recherche tabou). Tester et comparer différentes structures de voisinage, différents algorithmes gloutons pour la solution initiale, différents paramètres, etc.

Compétition

Les programmes seront testés sur une instance inconnue de taille ne dépassant pas 300 villes. Chaque programme aura à sa disposition un des coeurs d'un Intel(R) Core(TM)2 Duo à 2.6GHz dédié pendant un certain temps (probablement une dizaine de minutes). Ce temps écoulé, le programme sera arrêté et la meilleure solution trouvée sera retenue. En cas d'égalité entre deux programmes, celui qui a trouvé la solution plus tôt sera classé premier.

Afin de faciliter le test automatique, respecter les règles suivantes :

• Fournir un fichier tsp.jar qui contient vos classes et fichiers sources. Préciser la ligne de commande à utiliser, par exemple

  java -Xmx1024m -cp tsp.jar:/chemin/vers/graphstream.jar tsp.MaClassePrincipale instance.dgs
  

• Ne pas ouvrir des fenêtres, ne pas utiliser IHM. Le programme sera exécuté sans environnement graphique.
• Le programme doit afficher les solutions sur la sortie standard sous forme

  V1
  V2
  ...
  Vn
  

  où Vi est le numéro de la i-ème ville visité. Cet affichage doit se faire à chaque amélioration de la solution trouvée car le résultat retenu sera la meilleure solution affichée avant l'interruption du programme.
• Le programme doit afficher sur la sortie standard uniquement les solutions trouvées car sa sortie sera redirigée et analysé automatiquement. Tout message de diagnostique, débougage, etc, doit être affiché sur l'erreur standard.
• Avant d'envoyer votre fichier tsp.jar, faire le test suivant. Mettre les fichiers tsp.jar, graphstream.jar, tspanalyze.jar et un fichier instance dans le même répertoire et exécuter

  java -cp tsp.jar:graphstream.jar MaClassePrincipale instance.dgs | java -cp tspanalyze.jar:graphstream.jar tspanalyze.Analyzer instance.dgs
  

  Si vos solutions s'affichent bien et s'il n'y a pas d'exceptions, votre programme est prêt à passer le test.

Le classement des programmes sera publié sur cette page. Le TP sera noté en fonction de ce classement et du rapport.

A rendre

Envoyer par mail à stefan dot balev at univ dash lehavre dot fr

• un rapport en format pdf décrivant les différents possibilités testées, les choix retenus avec justification (2-3 pages)
• le code (voir plus haut)