Gibt es eine Möglichkeit, das Google Maps-API zu verwenden, um eine "optimierte" Route mit einer Reihe von Wegpunkten zurückzuerhalten (mit anderen Worten, eine Lösung, die dem Problem des reisenden Verkäufers entspricht), Oder gibt es immer die Route mit den Punkten in der angegebenen Reihenfolge zurück?Optimales Karten-Routing mit Google Maps
Es gibt sie immer in der Reihenfolge.
Also ich denke, Sie müssten die Entfernung (oder Zeit) zwischen jedem Paar von Punkten, eins nach dem anderen finden, dann lösen Sie das Problem des reisenden Verkäufers selbst. Vielleicht könnten Sie Google Maps davon überzeugen, diese Funktion hinzuzufügen. Ich denke, was eine "gut genug" Lösung ausmacht hängt davon ab, was Sie tun und wie schnell es sein muss.
Ihre Antwort ist jetzt nicht korrekt. Google unterstützt jetzt das TSP-Problem. Die kostenlose Version von Google Map enthält Start, Ende und 8 Mittelpunkte. (total 10 Punkte) Ich hoffe, du redest wieder für spätere Benutzerreferenz :) – hqt
In einem typischen TSP-Problem, die Annahme ist, kann man direkt zwischen zwei beliebigen Punkten reisen. Für Landstraßen ist dies nie der Fall. Wenn Google eine Route zwischen zwei Punkten berechnet, führt es eine heuristische Spanning-Tree-Optimierung durch und erreicht in der Regel einen nahezu optimalen Pfad.
Um eine TSP-Route zu berechnen, müsste man zuerst Google bitten, die paarweise Distanz zwischen jedem Knoten im Graphen zu berechnen. Ich denke, das erfordert n * (n-1)/2 calcs. Man könnte dann diese Distanzen nehmen und eine TSP-Optimierung an ihnen vornehmen.
OpenStreetMaps.org hat eine Java WebStart Anwendung, die tun kann, was Sie wollen. Natürlich werden die Berechnungen clientseitig ausgeführt. Das Projekt ist Open Source und kann einen Blick wert sein.
Suchen Sie nach einem optimalen Weg zwischen den Standorten oder nach der optimalen Fahrtroute? Wenn Sie nur die Punkte bestellen möchten, wenn Sie die GPS-Koordinaten erhalten, wird es ein sehr einfaches Problem.
Wie bekommst du den "ziemlich nahen optimalen Pfad" von der API zurück? Ich kann immer nur Punkte in der Reihenfolge erhalten, in der ich sie eingegeben habe. – Soldarnal
Google wird die Punkte nicht bestellen. Der optimale Pfad, den Google berechnet, ist die Entfernung zwischen den beiden Punkten. Wie viele Wege gibt es, um von New York nach Kalifornien zu kommen? Fast unendlich. Google wird Ihnen eine gute Route finden, die wahrscheinlich in der Nähe liegt, aber möglicherweise eine kürzere Route. – brianegge
Gerade gefunden http://gebweb.net/optimap/ Es sieht gut aus und einfach. Online-Version mit Google Maps.
Wow, erstaunliche Seite und froh, dass es so lange online war - das wird einem Freund von großem Nutzen sein !!! – DPSSpatial
Es gibt eine Option in Google Maps API DirectionsRequest namens optimizeWaypoints, die tun sollte, was Sie wollen. Dies kann jedoch nur bis zu 8 Wegpunkte passieren.
Alternativ gibt es eine Open-Source-Bibliothek (MIT-Lizenz), die Sie mit dem Google Maps-API verwenden können, um eine optimale Route (bis zu 15 Standorte) oder eine Route in der Nähe des optimalen Bereichs (bis zu 100 Standorte) zu erhalten.
Siehe http://code.google.com/p/google-maps-tsp-solver/
Sie die Bibliothek in Aktion sehen können bei www.optimap.net
Es gibt eine ganze Diskussion auf dieser Idee auf Slashdot: http://ask.slashdot.org/article.pl?sid=08/ 01/09/2311215 – brianegge