Optimale Karte Routing mit Google Maps

Question

Gibt es eine Möglichkeit, die Google Maps-API eine „optimierte“ Route eine Reihe von Wegpunkten gegeben, um wieder (in anderen Worten, eine „gut genug“ Lösung für das Reiseproblem), oder ist es immer kehrt die Route mit den Punkten in der angegebenen Reihenfolge?

Answer 1

Es gibt ihnen immer in Ordnung.

Also ich glaube, Sie den Abstand finden müßten (oder Zeit) zwischen jedem Paar von Punkten, einen nach dem anderen, lösen dann das Reiseproblem selbst. Vielleicht könnten Sie Google Maps überzeugen, obwohl diese Funktion hinzuzufügen. Ich denke, was eine „gut genug“ Lösung hängt davon ab, was Sie tun und wie schnell muss es sein.

Answer 2

Es gibt eine Option in Google Maps API Directions genannt optimizeWaypoints, das tun sollten, was Sie wollen. Dies kann nur behandeln bis zu 8 Wegpunkte, though.

Alternativ gibt es ein Open-Source (MIT Lizenz) Bibliothek, die Sie mit der Google Maps API verwenden können, um eine optimale zu erhalten (bis zu 15 Stellen) oder ziemlich nahe optimal (bis zu 100 Standorte) Weg.

Siehe http://code.google.com/p/google- Karten-TL-Löser /

Sie können die Bibliothek in Aktion bei www.optimap.net

Answer 3

In einem typischen TSP Problem ist die Annahme einer direkt zwischen zwei beliebigen Punkten reisen kann. Für die Oberflächenstraßen ist dies nie der Fall. Wenn Google eine Route zwischen zwei Punkten berechnet, es hat eine heuristische Spanning-Tree-Optimierung, und in der Regel mit einem ziemlich nah an optimalem Weg kommt.

einen TSP Route zu berechnen, würde man zuerst Google bitten, um den paarweise Abstand zwischen jedem Knoten in dem Graphen zu berechnen. Ich denke, das n * erfordert (n-1) / 2 calcs. Man könnte dann die Abstände nehmen und eine TSP-Optimierung mit ihnen ausführen.

OpenStreetMaps.org hat eine Java WebStart Anwendung, die tun können, was Sie wollen. Natürlich werden die Berechnungen Client-Seite wird ausgeführt. Das Projekt ist Open Source und kann einen Blick wert sein.

Versuchen Sie, einen optimalen geradlinigen Weg zwischen den Standorten oder der optimale Fahrtroute zu finden? Wenn Sie nur die Punkte bestellen möchten, wenn Sie die GPS-Koordinaten bekommen, wird es ein sehr einfaches Problem.

Answer 4

gefunden Nur http://gebweb.net/optimap/ Es ist schön und einfach aussieht. Online-Version unter Verwendung von Google Maps.

Answer 5

Google hat eine fertige Lösung für Reisen Salesman Problem. Es ist OR-Werkzeuge (Google Operations Research-Tools), finden Sie hier: https: // Entwickler .google.com / Optimierung / Routing / tsp

Was Sie brauchen im Grunde zu tun ist, zwei Dinge:

• Holen Sie sich die Abstände zwischen je zwei Punkten mit Google Maps API: https://developers.google.com/maps/documentation/distance-matrix/start

• Dann werden Sie die Abstände in einem Array mit dem OR-Tools und es wird eine sehr-gute Lösung für Sie (für bestimmte Fälle mit Millionen von Knoten haben Lösungen gefunden worden garantiert wird innerhalb von 1% einer optimalen Tour).

Sie können auch, dass beachten Sie:

  

Neben Lösungen zur klassischen Reisen Salesman finden   Problem, OR-Tools bietet auch Methoden für allgemeinere Typen von   TSPs, einschließlich der folgenden:

•   

  Asymmetrische Kostenprobleme - Die traditionelle TSP ist symmetrisch: der Abstand von Punkt A nach Punkt B entspricht den Abstand von Punkt B zu   die Kosten für den Versand Artikel von Punkt A jedoch Punkt A zum Punkt B   möglicherweise nicht die Kosten der gleich ihnen von Punkt B Versand A.-zu-Punkt   OR-Tools können auch Probleme behandeln, die asymmetrisch Kosten haben.

•   

  Preissammel TSPs, bei denen der Nutzen von einem Besuch Knoten entstehen

•   

  TSP mit Zeitfenstern

Weiterführende Links:

• OR-Tools bei Github: https://github.com/google/or-tools
• Erste Schritte: https://developers.google.com/optimization/introduction/get_started