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 précédents
 
  1. Whiler a dit :

    @ 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

  2. Whiler a dit :

    (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

  3. Whiler a dit :

    (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

  4. Whiler a dit :

    @ 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

  5. Whiler a dit :

    (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

  6. Whiler a dit :

    (arrow) Mise à jour : Version 1.4.9

    • Automatisation de n exécutions d’optimisation avec conservation du meilleur résultat obtenu

    Répondre

  7. Whiler a dit :

    (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

  8. Juju a dit :

    Super merci pour ton boulot ça m’aide de plus en plus !!!

    Répondre

  9. Whiler a dit :

    (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

  10. Whiler a dit :

    (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

  11. Whiler a dit :

    (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

Commentaires précédents
 

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 »