Routage optimal des cartes avec Google Maps

StackOverflow https://stackoverflow.com/questions/337607

  •  22-07-2019
  •  | 
  •  

Question

Existe-t-il un moyen d'utiliser l'API Google Maps pour récupérer un message "optimisé"? route étant donné un ensemble de points de passage (en d’autres termes, une solution "assez satisfaisante" au problème du voyageur voyageur), ou renvoie-t-il toujours la route avec les points dans l’ordre spécifié?

Était-ce utile?

La solution

Il leur donne toujours dans l'ordre.

Je pense donc que vous devriez trouver la distance (ou le temps) entre chaque paire de points, un à la fois, puis résoudre le problème du vendeur voyageur vous-même. Vous pourriez peut-être convaincre Google Maps d’ajouter cette fonctionnalité. Je suppose que ce qui constitue un "assez bon" La solution dépend de ce que vous faites et de sa rapidité.

Autres conseils

L'option DirectionsRequest de l'API Google Maps, appelée optimWaypoints, devrait faire ce que vous voulez. Cela ne peut cependant gérer que 8 points de cheminement.

Il existe également une bibliothèque open source (licence MIT) que vous pouvez utiliser avec l'API Google Maps pour obtenir un itinéraire optimal (jusqu'à 15 emplacements) ou assez proche de l'itinéraire optimal (jusqu'à 100 emplacements).

Voir http://code.google.com/p/google- maps-tsp-solver /

Vous pouvez voir la bibliothèque en action à l'adresse www.optimap.net

.

Dans un problème typique de TSP, on suppose qu’on peut se rendre directement entre deux points quelconques. Pour les routes de surface, ce n'est jamais le cas. Lorsque Google calcule un itinéraire entre deux points, il effectue une optimisation heuristique du spanning tree et génère généralement un chemin assez proche de l'optimum.

Pour calculer un itinéraire TSP, il faut d’abord demander à Google de calculer la distance par paire entre chaque nœud du graphique. Je pense que cela nécessite n * (n-1) / 2 calcs. On pourrait alors prendre ces distances et procéder à une optimisation du TSP.

OpenStreetMaps.org a une application Java WebStart qui peut faire ce que vous voulez. Bien sûr, les calculs sont exécutés côté client. Le projet est open source et vaut peut-être le détour.

Essayez-vous de trouver un tracé optimal en ligne droite entre les emplacements ou l’itinéraire optimal? Si vous souhaitez simplement commander les points, si vous pouvez obtenir les coordonnées GPS, cela devient un problème très facile.

Nous venons de trouver http://gebweb.net/optimap/ , c'est très simple. Version en ligne utilisant google maps.

Google propose une solution adaptée au problème de Travel Salesman. C’est OR-Tools (outils de recherche opérationnelle de Google) que vous pouvez trouver ici: https: // développeurs .google.com / optimisation / routage / tsp

Ce que vous devez faire est essentiellement 2 choses:

Vous pouvez également noter que:

  

En plus de trouver des solutions au vendeur itinérant classique   Problème, OR-Tools fournit également des méthodes pour des types plus généraux de   Les FST, y compris les suivants:

  •   

    Problèmes de coût asymétriques - Le TSP traditionnel est symétrique: la distance entre le point A et le point B est égale à la distance entre le point B et   point A. Toutefois, les frais d’expédition des articles du point A au point B   pourrait ne pas correspondre au coût de leur expédition du point B au point A.   OU-Tools peut également gérer des problèmes ayant des coûts asymétriques.

  •   

    Les PST à collectionner les prix, qui tirent des avantages des nœuds visiteurs

  •   

    TSP avec fenêtres temporelles

Liens supplémentaires:

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top