Problème du voyageur de commerce – wTSP » & pourquoi j’n’écrirais pas ça ?

Avr 08

Problème du voyageur de commerce – wTSP

Delphi

Après avoir réussi à modifier mes coordonnées dans Google Latitude, j’ai eu envie de voir comment on pouvait optimiser un trajet entre plusieurs points…

Le problème me semblait complexe, mais je n’imaginais pas encore à quel point

Heureusement, j’ai très rapidement trouvé de la documentation concernant ce classique problème, plus communément appelé : problème du voyageur de commerce^W.

J’ai également trouvé un projet déjà écrit en Delphi qui m’a permis de l’implémenter sans finalement, vraiment comprendre tout ce qui se passait… les algorithmes génétiques n’étant clairement pas ma tasse de café…. Vous pouvez visiter le site Web de l’auteur sur cette page.

L’application que j’ai faite me permet de charger un fichier KML^W, généré avec Google Earth ayant la structure suivante :

Un répertoire qui contient :
- des repères

wTSP

Je charge alors le fichier KML en récupérant le nom, les coordonnées GPS et l’altitude de chaque repère dans une liste (l’altitude n’est pas utilisée pour le calcul des distances).

Je calcule ensuite les distances entre chaque position. Chaque distance correspond à l’écart entre la ligne qui l’affiche et la position précédente. La première ligne est calculé en utilisant la dernière position.

Ce calcul est effectué en prenant une valeur constante pour le rayon équatorial :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

function CalculateDistance(dFromLatitude, dFromLongitude, dToLatitude, dToLongitude: Double): Double;
const
EARTH_RADIUS = 6378; // Rayon équatorial : 6 378,137

function ArcCosWithZero(dValue: Double): Double;
var
dCheck: Double;
begin
dCheck := sqrt(-dValue*dValue+1);
if (dCheck = 0) then
dCheck := 0.0000000001;

Result := -ArcTan(dValue / dCheck) + (Pi / 2);
end;

begin
// Degrés en radians
dFromLatitude := dFromLatitude / 180 * Pi;
dFromLongitude := dFromLongitude / 180 * Pi;
dToLatitude := dToLatitude / 180 * Pi;
dToLongitude := dToLongitude / 180 * Pi;

//Distance = Rayon * | arccos[ sin(LatA).sin(LatB)+cos(LatA).cos(LatB).cos(LonA-LonB) ] |
// Rayon équatorial : 6 378,137
Result := EARTH_RADIUS * ArcCosWithZero(Sin(dFromLatitude)*Sin(dToLatitude)+Cos(dFromLatitude)*Cos(dToLatitude)*Cos(dFromLongitude - dToLongitude));
end;

Ensuite, grâce à l’algorithme et au code source de l’application de Troels, j’optimise les distances entre les différents repères :

Calcul du chemin le plus court

Pour finalement réafficher la liste dans l’ordre trouvé :

Résultats wTSP

Si cette application vous intéresse, vous pouvez la télécharger depuis ce lien. Vous pouvez également trouver un exemple du type de fichier KML attendu par l’application.

Cette application est développée avec Embarcadero Delphi XE.

Rédigé par Whiler \\ Tags : coloration syntaxique, Delphi, données, Embarcadero, freeware, localisation, script

27 réponses pour “Problème du voyageur de commerce – wTSP”

Whiler a dit : Le 13 avril 2011 à 0 h 13 mn
@ Juju : j’ai ajouté une case à cocher pour ne plus permuter la première position. Etant donné l’algorithme utilisé, c’est ce que je peux faire de mieux… sinon, il faudrait tout recasser/repenser…
- Donc, cela te permet de mettre Toulouse en première position…
- Ensuite, à ta place, je ne mettrais pas Paris dans la liste…
- Je lancerais l’optimisation…. (je mémoriserais la distance trouvée, je mélangerais et relancerais l’optimisation… plusieurs fois de suite…) Je le ferais plusieurs fois car l’algo ne trouve pas forcément la meilleure solution à tous les coups… donc… en mélangeant et relançant plusieurs fois.. on finit généralement par tomber dessus ou un trajet qui n’est pas si mal… cela dit, rien n’est garanti et je n’ai pas contrôlé avec autant de villes…
- Ensuite, je chargerais en plus un autre KML qui contiendrait Paris… (il s’ajoute à la liste existante)
- Puis je jouerais en glissant-déposant les villes pour ajuster le trajet et connaitre les distances
- Tu peux également en supprimer en cochant les villes à supprimer, puis en cliquant sur la croix Effacer
- Finalement, je sauvegarderais, puis je lancerais Google Earth pour visualiser le trajet obtenu (tu peux ensuite, dans wTSP, redéplacer une ville, resauvegarder et recliquer sur le bouton Voir KML… sans quitter Google Earth qui propose alors de recharger le fichier )
Répondre
Whiler a dit : Le 13 avril 2011 à 9 h 00 mn
(arrow) Mise à jour : Version 1.4.6
- Ajout de nouveaux boutons :
  - Pour décaler la liste vers le haut
  - Pour décaler la liste vers le bas
  - Pour inverser l’ordre de la liste
Répondre
Whiler a dit : Le 13 avril 2011 à 12 h 00 mn
(arrow) Mise à jour : Version 1.4.7
- Possibilité de directement charger des fichiers en les glissant-déposant sur l’exécutable ou par ligne de commande
- Possibilité de directement charger des fichiers en les glissant-déposant sur la liste des positions
- Sauvegarde des derniers paramètres utilisés
Répondre
Whiler a dit : Le 13 avril 2011 à 12 h 15 mn
@ Juju : Pour votre trajet Toulouse-Paris (sans tenir compte des villes/régions intermédiaires…), je procéderais ainsi :
- je prends ma liste avec Toulouse mais sans Paris…
- je l’optimise
- je la sauvegarde avec la meilleure optimisation trouvée
- j’efface tout (menu contextuel)
- je charge ma liste avec toutes les villes, dont Paris, mais pas Toulouse
- je mets Paris en premier
- je l’optimise
- j’inverse l’ordre
- je sauvegarde
- j’efface à nouveau tout
- je charge la sauvegarde avec Toulouse
- puis je charge la sauvegarde avec Paris
- puis je supprime les villes en doublon pour les chemins qui se chevauchent …
En admettant que le meilleur chemin a été trouvé… il en existe 2 possibles pour un même point de départ….
Par exemple, on peut avoir :
- Toulouse, Nantes, Paris, Strasbourg
- Toulouse, Strasbourg, Paris, Nantes
Du coup, si les chemins ne se chevauchent pas…
Pour les avoir dans le même ordre, sur l’une des deux sauvegardes, je clique sur le bouton Inverser puis sur le bouton Décaler vers le bas…
Ensuite, on peut sauvegarder et recharger les deux fichiers…

J’espère que cette méthode vous apportera une solution adéquate

Répondre
Whiler a dit : Le 13 avril 2011 à 18 h 56 mn
(arrow) Mise à jour : Version 1.4.8
- Le bouton Mélanger mélange encore mieux la liste des positions (la première position n’est mélangée que si la case à cocher est décochée)
- Mise à jour de l’ordre des tabulations
Répondre
Whiler a dit : Le 14 avril 2011 à 0 h 30 mn
(arrow) Mise à jour : Version 1.4.9
- Automatisation de n exécutions d’optimisation avec conservation du meilleur résultat obtenu
Répondre
Whiler a dit : Le 14 avril 2011 à 1 h 30 mn
(arrow) Mise à jour : Version 1.4.10
- Menu contextuel :
  - Export des positions cochées dans le presse-papier au format CSV (Séparateur : ";")
  - L’insertion des milieux est maintenant basée sur les cases à cocher de la liste des positions et non plus sur les lignes sélectionnées
Répondre
Juju a dit : Le 15 avril 2011 à 1 h 02 mn
Super merci pour ton boulot ça m’aide de plus en plus !!!

Répondre
Whiler a dit : Le 15 avril 2011 à 1 h 15 mn
@ Juju :

Répondre
Whiler a dit : Le 15 avril 2011 à 1 h 30 mn
(arrow) Mise à jour : Version 1.4.11
- Suppression du répertoire en racine dans les sauvegardes de fichier Google Earth
- Nombre de positions dans la liste mis à jour lors de suppressions
Répondre
Whiler a dit : Le 15 avril 2011 à 2 h 00 mn
(arrow) Mise à jour : Version 1.4.12
- Mise à jour des éléments des sauvegardes des fichiers Google Earth :
  - Trajet et visite en premiers
  - Une visite affiche sa durée dans sa description (au lieu de la distance comme dans le trajet)
Répondre
Whiler a dit : Le 24 avril 2011 à 20 h 08 mn
(arrow) Mise à jour : Version 2.0.0
- Intégration avec wLatitude pour les mises à jour automatiques (nécessite l’application wLatitude en version 1.1 minimum).
Répondre