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 8 avril 2011 à 22 h 30 mn
(arrow) Mise à jour : Version 1.1
– permet de directement charger des fichiers KML contenus dans un fichier ZIP
~~– un click sur l’entête de la colonne Nom permet d’inverser les cases à cocher des lignes~~

Répondre
Whiler a dit : Le 9 avril 2011 à 1 h 00 mn
(arrow) Mise à jour : Version 1.2
– ajout du temps de calcul
– bouton pour mélanger les positions

Répondre
Whiler a dit : Le 9 avril 2011 à 3 h 15 mn
(arrow) Mise à jour : Version 1.3
– optimisation du temps de calcul
– valeurs par défaut accrues

Répondre
philgoodgood a dit : Le 9 avril 2011 à 9 h 13 mn
Bonjour,
@whiler : bon c’est une première étape … bravo
maintenant voilà un autre algo « Algorithme_de_Dijkstra » … et après tu nous fais un p’tit prog de calcul d’itinéraire en IdF

Répondre
Whiler a dit : Le 9 avril 2011 à 11 h 00 mn
@ philgoodgood : Salut,

Intéressant comme article !
Les différentes étapes de programmation sont très bien expliquées…
Le gros problème dans ce contexte, c’est d’avoir les données à traiter

Répondre
Whiler a dit : Le 10 avril 2011 à 16 h 15 mn
(arrow) Mise à jour : Version 1.4
– Génération de fichiers Google Earth (*.kml) avec le chemin le plus court

Répondre
Whiler a dit : Le 10 avril 2011 à 23 h 00 mn
(arrow) Mise à jour : Version 1.4.1
– Prise en charge du format KMZ (chargement et sauvegarde)

Répondre
Whiler a dit : Le 11 avril 2011 à 13 h 45 mn
(arrow) Mise à jour : Version 1.4.2
– Tri sur entête de colonne
– Menu contextuel (click droit) pour sélectionner et supprimer des positions

Répondre
Whiler a dit : Le 11 avril 2011 à 19 h 00 mn
(arrow) Mise à jour : Version 1.4.3
– Ajout d’une visite pour naviguer entre les différentes coordonnées dans les fichiers sauvegardés

Répondre
Whiler a dit : Le 12 avril 2011 à 13 h 45 mn
(arrow) Mise à jour : Version 1.4.4
- Ajout de fonctionnalités au menu contextuel :
  - Copier coordonnées : Copie les coordonnées de la position sous le curseur dans le presse-papier
  - Insérer milieu : Insére les coordonnées du point au milieu de deux coordonnées sélectionnées
Répondre
Juju a dit : Le 12 avril 2011 à 21 h 08 mn
Salut, est-ce possible de définir le trajet le plus court en fixant obligatoirement une ville d’arrivé ? Exemple: je pars de Toulouse je veux arriver à Paris en passant par 100 villes en utilisant le trajet le plus court.

Merci pour ta réponse

Julien

Répondre
Whiler a dit : Le 12 avril 2011 à 21 h 14 mn
Salut,

Ce n’est actuellement pas possible… faut que je réfléchisse à la question…
pour voir s’il est possible de permettre de fixer des villes…

S’il n’y a que la ville d’arrivée (et pas celle de départ)… on peut déjà le faire en lançant l’optimisation.. puis en utilisant le bouton Décaler afin que la ville d’arrivée se retrouve dernière…

Mais je vais étudier la question…

Merci pour le message

Répondre
Juju a dit : Le 12 avril 2011 à 21 h 48 mn
Merci pour ta reponse.

Répondre
Juju a dit : Le 12 avril 2011 à 22 h 56 mn
Re,

en fait mon problème est un peu plus complexe.

J’ai une liste de 250 villes environ. Une ville de départ Toulouse et une d’arrivée Paris. Je dois parmi les 250 faire le parcours le plus optimal en en choisissant 100. J’ai 6 butés géographique imposées du style (au moins une ville au nord du 49°N, a l’est du 7°E …).

C’est pas évident et ton programme me met déjà un peu sur quelques pistes.

Merci encore !

Répondre
Whiler a dit : Le 13 avril 2011 à 0 h 00 mn
(arrow) Mise à jour : Version 1.4.5
- Un double-click sur une position ouvre une page Google Maps sur la position cliquée
- Ajout d’une case à cocher pour fixer la première position
- Temps de la visite améliorée
Répondre