Avr 08

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 (lol)

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

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 KMLW, généré avec Google Earth ayant la structure suivante :

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

wTSP

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

Calcul du chemin le plus court

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

Résultats wTSP

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.

Développé en Delphi

Share

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

Commentaires plus récents
 
  1. Whiler a dit :

    (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

  2. Whiler a dit :

    (arrow) Mise à jour : Version 1.2
    – ajout du temps de calcul
    – bouton pour mélanger les positions

    Répondre

  3. Whiler a dit :

    (arrow) Mise à jour : Version 1.3
    – optimisation du temps de calcul
    – valeurs par défaut accrues

    Répondre

  4. philgoodgood a dit :

    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 (lol)

    Répondre

  5. Whiler a dit :

    @ philgoodgood : Salut,

    Intéressant comme article ! (y)
    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 (lol)

    Répondre

  6. Whiler a dit :

    (arrow) Mise à jour : Version 1.4
    – Génération de fichiers Google Earth (*.kml) avec le chemin le plus court

    Google Earth

    Répondre

  7. Whiler a dit :

    (arrow) Mise à jour : Version 1.4.1
    – Prise en charge du format KMZ (chargement et sauvegarde)

    Répondre

  8. Whiler a dit :

    (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

  9. Whiler a dit :

    (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

  10. Whiler a dit :

    (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

  11. Juju a dit :

    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

  12. Whiler a dit :

    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 (y)

    Répondre

  13. Juju a dit :

    Merci pour ta reponse.

    Répondre

  14. Juju a dit :

    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

  15. Whiler a dit :

    (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

Commentaires plus récents
 

Laisser une réponse

(requis)

(requis)

*

Notifiez-moi les commentaires à venir via email. Vous pouvez aussi vous abonner sans commenter.

;) (lol) (y) |-( (hi) 8-) (angel) :s (clap) (bow) (tmi) (:| plus »

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.