Y a-t-il un moyen d'utiliser l'API Google Maps pour retrouver un itinéraire "optimisé" en fonction d'un ensemble de waypoints (en d'autres termes, une solution "assez bonne" au problème du voyageur de commerce)? ou renvoie-t-il toujours la route avec les points dans l'ordre spécifié?Acheminement optimal des cartes avec Google Maps
Il leur donne toujours dans l'ordre. Donc, je pense que vous devez trouver la distance (ou le temps) entre chaque paire de points, un par un, puis résoudre vous-même le problème du vendeur itinérant. Vous pourriez peut-être convaincre Google Maps d'ajouter cette fonctionnalité. Je suppose que ce qui constitue une solution «assez bonne» dépend de ce que vous faites et à quelle vitesse il doit être.
votre réponse ne corrige pas maintenant. Google prend désormais en charge le problème de TSP. La version gratuite de google map comprend le début, la fin et 8 points intermédiaires. (Totalement 10 points) J'espère que vous éditer à nouveau pour la référence de l'utilisateur plus tard :) – hqt
Dans un problème typique de TSP, l'hypothèse est que l'on peut voyager 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 de l'arbre traversant et trouve généralement un chemin relativement proche de l'optimal. Pour calculer une route TSP, il faut d'abord demander à Google de calculer la distance par paire entre chaque nœud dans le graphique. Je pense que cela nécessite n * (n-1)/2 calcs. On pourrait alors prendre ces distances et effectuer une optimisation TSP sur eux.
OpenStreetMaps.org a une application Java WebStart qui peut faire ce que vous voulez. Bien sûr, les calculs sont effectués côté client. Le projet est open source et peut valoir le coup d'oeil. Essayez-vous de trouver un chemin optimal en ligne droite entre les emplacements, ou l'itinéraire de conduite optimal? Si vous voulez juste commander les points, si vous pouvez obtenir les coordonnées GPS, cela devient un problème très facile.
Comment obtenez-vous le chemin "assez proche du chemin optimal" de l'API? Je peux seulement récupérer des points dans l'ordre où je les ai inscrits. – Soldarnal
Google ne commandera pas les points. Le chemin optimal que Google calcule est la distance entre les deux points. Combien de voies y a-t-il entre New York et la Californie? Près de l'infini. Google vous trouvera une bonne route, probablement proche de l'optimum, mais il se peut qu'il y ait une route plus courte. – brianegge
Juste trouvé http://gebweb.net/optimap/ Il a l'air agréable et facile. Version en ligne en utilisant google maps.
Wow site incroyable et heureux qu'il a été en ligne si longtemps-ce sera d'une grande utilité à un de mes amis !!! – DPSSpatial
Il existe une option dans Google Maps API DirectionsRequest appelée optimizeWaypoints, qui devrait faire ce que vous voulez. Cela ne peut toutefois gérer que jusqu'à 8 waypoints. Il est également possible d'utiliser 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 très proche de l'optimal (jusqu'à 100 emplacements).
Voir http://code.google.com/p/google-maps-tsp-solver/
Vous pouvez voir la bibliothèque en action à www.optimap.net
Il y a toute une discussion sur cette idée sur Slashdot: http://ask.slashdot.org/article.pl?sid=08/ 01/09/2311215 – brianegge