Welche Algorithmen berechnen die Richtungen von Punkt A nach Punkt B auf einer Karte?

Question

Wie schlagen Kartenanbieter (wie Google oder Yahoo! Maps) Wegbeschreibungen vor?

Ich meine, sie verfügen wahrscheinlich über reale Daten in irgendeiner Form, sicherlich einschließlich Entfernungen, aber vielleicht auch Dinge wie Fahrgeschwindigkeiten, Vorhandensein von Gehwegen, Zugfahrpläne usw. Aber nehmen wir an, die Daten hätten ein einfacheres Format, z. B. einen sehr großen gerichteten Graphen mit Kantengewichten, die die Entfernungen widerspiegeln. Ich möchte in der Lage sein, schnell die Richtung von einem beliebigen Punkt zu einem anderen zu berechnen. Manchmal liegen diese Punkte nahe beieinander (innerhalb einer Stadt), manchmal weit auseinander (quer durchs Land).

Graph-Algorithmen wie der Dijkstra-Algorithmus funktionieren nicht, weil der Graph riesig ist. Glücklicherweise werden heuristische Algorithmen wie A* wahrscheinlich funktionieren. Unsere Daten sind jedoch sehr strukturiert, und vielleicht könnte eine Art von abgestuftem Ansatz funktionieren? (Speichern Sie z. B. vorberechnete Richtungen zwischen bestimmten, weit voneinander entfernten "Schlüsselpunkten" sowie einige lokale Richtungen. Dann werden die Richtungen für zwei weit entfernte Punkte lokale Richtungen zu einem Schlüsselpunkt, globale Richtungen zu einem anderen Schlüsselpunkt und dann wieder lokale Richtungen beinhalten).

Welche Algorithmen werden in der Praxis tatsächlich verwendet?

PS. Diese Frage wurde durch die Entdeckung von Macken in Online-Kartenanleitungen motiviert. Entgegen der Dreiecksungleichung denkt Google Maps manchmal, dass X-Z dauert länger und ist weiter als die Verwendung eines Zwischenpunkts wie in X-Y-Z . Aber vielleicht optimieren sie ihre Laufwege auch für einen anderen Parameter?

PPS. Hier ist ein weiterer Verstoß gegen die Dreiecksungleichheit, der (für mich) darauf schließen lässt, dass sie eine Art abgestuften Ansatz verwenden: X-Z 対 X-Y-Z . Ersterer scheint den prominenten Boulevard de Sebastopol zu nutzen, auch wenn er etwas abgelegen ist.

bearbeiten : Keines dieser Beispiele scheint mehr zu funktionieren, aber zum Zeitpunkt des ursprünglichen Beitrags funktionierten beide.

Answer 1

Ich spreche als jemand, der 18 Monate lang bei einem Kartierungsunternehmen gearbeitet hat und dabei auch den Routing-Algorithmus entwickelt hat... ja, Dijkstra's funktioniert, mit ein paar Änderungen:

• Anstatt zu tun Dijkstra's einmal von der Quelle zum Ziel, beginnen Sie an jedem Ende und erweitern beide Seiten, bis sie sich in der Mitte treffen. Dadurch entfällt etwa die Hälfte der Arbeit (2*pi*(r/2)^2 gegenüber pi*r^2).
• Um zu vermeiden, dass Sie die Seitengassen jeder Stadt zwischen Ihrem Ausgangs- und Zielort erkunden müssen, können Sie mehrere Kartendatenebenen verwenden: Eine Ebene "Autobahnen", die nur Autobahnen enthält, eine Ebene "Nebenstraßen", die nur Nebenstraßen enthält, und so weiter. Dann erkunden Sie nur kleinere Abschnitte der detaillierteren Ebenen und erweitern diese nach Bedarf. Natürlich lässt diese Beschreibung eine Menge Details aus, aber Sie verstehen die Idee.

Mit entsprechenden Modifikationen können Sie sogar in einem sehr vernünftigen Zeitrahmen quer durchs Land fahren.

Answer 2

Diese Frage war in den letzten Jahren ein aktives Forschungsgebiet. Die Hauptidee ist, eine Vorverarbeitung in der Grafik einmal zu beschleunigen todo folgende Abfragen . Mit diesen zusätzlichen Informationen können Reiserouten sehr schnell berechnet werden. Trotzdem, Dijkstras Algorithmus ist die Grundlage für alle Optimierungen.

Arachnid beschrieb die Verwendung der bidirektionalen Suche und der Kantenbeschneidung auf der Grundlage hierarchischer Informationen. Diese Beschleunigungstechniken funktionieren recht gut, aber die neuesten Algorithmen übertreffen diese Techniken bei weitem. Mit den aktuellen Algorithmen kann ein kürzester Pfad in deutlich weniger Zeit berechnet werden als eine Millisekunde auf einem kontinentalen Straßennetz. Eine schnelle Implementierung des unveränderten Algorithmus von Dijkstra benötigt etwa 10 Sekunden .

Der Artikel Entwicklung schneller Routenplanungsalgorithmen gibt einen Überblick über die Fortschritte der Forschung auf diesem Gebiet. Weitere Informationen finden Sie in den Referenzen des Papiers.

Die schnellsten bekannten Algorithmen verwenden keine Informationen über den hierarchischen Status der Straße in den Daten, d. h. ob es sich um eine Autobahn oder eine lokale Straße handelt. Stattdessen berechnen sie in einem Vorverarbeitungsschritt eine eigene Hierarchie, die zur Beschleunigung der Routenplanung optimiert ist. Diese Vorberechnung kann dann verwendet werden, um die Suche zu verfeinern: Weit von Start und Ziel entfernte langsame Straßen müssen bei Dijkstra's Algorithmus nicht berücksichtigt werden. Die Vorteile sind sehr gut Leistung und eine Korrektheit Garantie für das Ergebnis.

Die ersten optimierten Routenplanungsalgorithmen befassten sich nur mit statischen Straßennetzen, d. h. eine Kante im Graphen hat einen festen Kostenwert. Dies ist in der Praxis nicht zutreffend, da wir dynamische Informationen wie Staus oder fahrzeugabhängige Beschränkungen berücksichtigen wollen. Neuere Algorithmen können auch mit solchen Problemen umgehen, aber es gibt immer noch Probleme zu lösen und die Forschung geht weiter.

Wenn Sie die Entfernungen des kürzesten Weges benötigen, um eine Lösung für die folgende Aufgabe zu berechnen TSP dann sind Sie wahrscheinlich an Matrizen interessiert, die alle Entfernungen zwischen Ihren Quellen und Zielen enthalten. Hierfür könnten Sie Folgendes in Betracht ziehen Berechnung kürzester Wege von vielen zu vielen mit Hilfe von Autobahnhierarchien . Beachten Sie, dass dies in den letzten 2 Jahren durch neuere Ansätze verbessert wurde.

Answer 3

Es geht nur um die Verletzung der Dreiecksungleichheit, und ich hoffe, dass der zusätzliche Faktor, für den sie optimiert werden, gesunder Menschenverstand ist. Man will nicht unbedingt den kürzesten oder schnellsten Weg, denn das kann dazu führen chaos y Zerstörung . Wenn Sie möchten, dass Ihre Wegbeschreibungen die Hauptrouten bevorzugen, die für Lkw geeignet sind und die es verkraften können, dass jeder Fahrer, der einem Navigationsgerät folgt, auf ihnen unterwegs ist, können Sie die Ungleichheit des Dreiecks schnell verwerfen[1].

Wenn Y eine schmale Wohnstraße zwischen X und Z ist, sollten Sie die Abkürzung über Y nur verwenden, wenn der Benutzer ausdrücklich nach X-Y-Z fragt. Wenn er nach X-Z fragt, sollte er sich an die Hauptstraßen halten, auch wenn es etwas weiter ist und etwas länger dauert. Das ist vergleichbar mit Das Braesssche Paradoxon - Wenn jeder versucht, den kürzesten und schnellsten Weg zu nehmen, führt die daraus resultierende Überlastung dazu, dass es für niemanden mehr der schnellste Weg ist. Hier kommen wir von der Graphentheorie zur Spieltheorie.

[1] Tatsächlich stirbt jede Hoffnung, dass die erzeugten Entfernungen eine Entfernungsfunktion im mathematischen Sinne sind, wenn man Einbahnstraßen zulässt und die Symmetrieanforderung aufhebt. Auch der Wegfall der Dreiecksungleichung streut nur Salz in die Wunde.

Answer 4

Hier werden die schnellsten Routing-Algorithmen der Welt verglichen und auf ihre Korrektheit geprüft:

http://algo2.iti.uka.de/schultes/hwy/schultes_diss.pdf

Hier ist ein Google Tech Talk zu diesem Thema:

http://www.youtube.com/watch?v=-0ErpE8tQbw

Hier ist eine Implementierung des Highway-Hierarchies-Algorithmus, wie er von Schultes diskutiert wurde (derzeit nur in Berlin, ich schreibe die Schnittstelle und eine mobile Version ist ebenfalls in Arbeit):

http://tom.mapsforge.org/

Answer 5

Der derzeitige Stand der Technik in Bezug auf die Abfragezeiten für statische Straßennetze ist der von Abraham et al. vorgeschlagene Hub-Labelling-Algorithmus. http://link.springer.com/chapter/10.1007/978-3-642-20662-7_20 . Ein umfassender und hervorragend geschriebener Überblick über dieses Gebiet wurde kürzlich als technischer Bericht von Microsoft veröffentlicht http://research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf .

Die Kurzversion ist...

Der Hub-Labelling-Algorithmus liefert die schnellsten Abfragen für statische Straßennetze, benötigt aber eine große Menge an Speicherplatz (18 GiB) für die Ausführung.

Das Transitknoten-Routing ist etwas langsamer, benötigt aber nur etwa 2 GiB Speicherplatz und hat eine kürzere Vorverarbeitungszeit.

Kontraktionshierarchien bieten einen guten Kompromiss zwischen kurzen Vorverarbeitungszeiten, geringem Speicherplatzbedarf (0,4 GiB) und schnellen Abfragezeiten.

Kein einziger Algorithmus ist vollständig dominant...

Dieser Google Tech Talk von Peter Sanders könnte von Interesse sein

https://www.youtube.com/watch?v=-0ErpE8tQbw

Auch dieser Vortrag von Andrew Goldberg

https://www.youtube.com/watch?v=WPrkc78XLhw

Eine Open-Source-Implementierung von Kontraktionshierarchien ist auf der Website der Forschungsgruppe von Peter Sanders am KIT verfügbar. http://algo2.iti.kit.edu/english/routeplanning.php

Auch ein leicht zugänglicher Blog-Beitrag von Microsoft über die Verwendung des CRP-Algorithmus... http://blogs.bing.com/maps/2012/01/05/bing-maps-new-routing-engine/