Plus court chemin

On vous donne un graphe orienté, avec des poids positifs sur les arcs et on veut trouver un plus court chemin entre deux sommets données. Résolvez ce problème par la programmation linéaire à l’aide d’AMPL. Le graphe représente le réseau routier de l’ile de Man. Les sommets sont les intersections et les arcs indiquent les rues, pondéré par le temps de franchissement. Pour les rues qui ne sont pas en sens unique, deux arcs sont présents. Comme il peut y avoir plusieurs routes en deux intersections fixé, on est en fait en présence d’un multigraphe. Ainsi les arcs sont identifiés par trois nombres, le numéro du sommet source, le numéro du sommet destination, et un identifiant d’arc, qui peut être un numéro entre 0 et 2 pour ce graphe.

L’entrée

Téléchargez tous les fichiers ici. (Attention, leur contenu a changé le 12 décembre)

man_v.tab

un fichier texte qui code les intersections de l’ile de Man, avec leur coordonnées GPS. Il comporte de l’ordre de 5000 sommets.

man_a.tab

un fichier texte qui code les rues de l’ile de Man. Il comporte de l’ordre de 12000 arcs. Le temps indiqué est en millisecondes.

visualize.html

un fichier à ouvrir dans votre navigateur pour visualiser une solution. Ce fichier nécessite une connexion Internet et lit un fichier visualize.js, avec les données à afficher.

visualize.py

un script Python qui permet de générer un fichier visualize.js pour la visualisation de votre solution. Il prend en argument de ligne de commande deux noms de fichier. D’abord le le fichier man_a.txt, puis un fichier contenant la sortie de AMPL. Dans ce dernier fichier seul les lignes de la forme x[int,int,int] = float sont pris en compte, et votre solution est extraite de ces lignes.

Vous pourriez alors générer une solution de la manière suivante, en mettant votre répertoire et nom de fichier à la place. Notez que le format d’affichage

ampl: cd /Users/durr/Documents/Enseignement/CentraleSupelecOPT/optim/data/man/;
ampl: model shortest_path.mod;
ampl: solve;
ampl: printf{(u,v,id) in A} "x[%i,%i,%i] = %f\n", u, v, id, x[u,v,id] > ampl_output.txt;

Puis dans un shell

./visualize.py man_v.tab ampl_output.txt > visualize.js

et finalement affichez le fichier visualize.html, par exemple par la commande

open visualize.html  # commande MacOSX

Lire le graphe

AMPL permet de lire les données à partir d’un fichier texte. D’ailleurs vous n’allez pas écrire un fichier shortest_path.dat, puisque les données sont essentiellement dans ces fichiers texte. Vous pouvez alors commencer votre fichier shortest_path.mod avec les lignes suivantes. Peut-être que vous devez indiquer les fichiers par leur chemin absolu. Pour plus d’information sur la syntaxe nous référons au chapitre sur les données du livre d’AMPL.

param source = 283492455;
param target = 283494345;
param multiplicity = 3;

set V;                    # vertices
set A within {V cross V cross 0..multiplicity-1}; # arcs
param longitude{V};
param latitude{V};
param time{A};

# modifiez ici en votre répertoire
cd /Users/durr/Documents/Enseignement/CentraleSupelecOPT/optim/data/man; 

table ManV IN "man_v.tab": V <- [V], longitude, latitude;
read table ManV;

table ManA IN "man_a.tab": A <- [arc_src, arc_dst, id], time;
read table ManA;

var x{A}, >= 0, <=1;

Votre programme linéaire

Les variables x[u,v] sont des variables caractéristiques de votre solution, dans le sens qu’ils sont mis à 1 pour les arcs (u,v) traversés par le plus court chemin que vous avez calculé. Pour la synataxe AMPL de votre modélisation vous pouvez vous inspirer de cet exemple.

Il n’est pas nécessaire d’indiquer binary pour ces variables, car toute solution point extrême à votre programme linéaire est entière. Plusieurs méthodes sont possibles pour prouver cette propriété. Essayez d’écrire une preuve.

La question

Quelle est la distance entre les sommets 283492455 et 283494345 dans le graphe ?

Notes

Si la programmation linéaire peut efficacement résoudre les problèmes de plus court chemin, il existe des algorithmes combinatoires dédiés plus efficaces, comme par exemple l’algorithme de Dijkstra implémenté par exemple ici.