Gibt es neuere Routing-Algorithmen (als Dijkstra, A *) in GIS-Datenbanken?

Es gibt Arbeiten wie Reach for A * von Microsoft-Forschern und Highway Hierarchies von Sanders und Schtolz (wenn ich den Namen richtig schreibe) von der Uni Karlsruhe . Beide reduzieren die Berechnungsreihenfolge erheblich und beschleunigen die Verarbeitung in großen Diagrammen um das Tausendfache (siehe Ergebnisse in den verknüpften Dokumenten). Die letztere Arbeit führte zu Open Source Routing Machine , die leider nicht populär genug und nicht angepasst ist (ich konnte es nicht kompilieren, obwohl ich mich sehr bemüht habe).

Gleichzeitig bieten die von mir ausprobierten Datenbanken Spatialite und PgRouting laut Dokumentation nur Dijkstra- und A * -Algorithmen an. Ich habe noch nicht einmal die erwähnte bidirektionale Suche gesehen, was meiner Erfahrung nach doppelt so viel Rechenzeit spart.

Gibt es bessere Algorithmen für Datenbanken oder andere Anwendungen?

Die Wahrheit ist, dass die meisten Menschen eine benutzerdefinierte Variante des A * -Algorithmus verwenden. Sie werden dies bei den meisten "großen Typen" sehen (ich kann nicht sagen, wer sie in einem öffentlichen Forum sind, aber ich kann Ihnen sagen, dass Sie wahrscheinlich einen von ihnen verwenden - garantiert), bei denen die Änderung der Heuristik erfolgt sehr abhängig von den Datensätzen, die sie verwenden.

Sie haben bereits eine Verfugung erwähnt , die ich als "traditionelle" Option betrachten würde. Es ist gut für einfache Routing-Algorithmen und für die meisten Probleme. Es ist auch einfach zu bedienen und verwendet eine traditionelle Datenbank im Backend.

Es hängt jedoch wirklich vom Umfang und der Art des Problems ab, das Sie lösen möchten, und das Routing ist ein Grafikproblem .

Auch hier haben die "Großen" normalerweise eine Menge Daten, die mit ihrer Grafik verknüpft sind (z. B. Verkehrsdaten, Busrouten, Gehwege), die sich auf den Routing-Algorithmus auswirken. Diese werden als multimodale Reiseplaner bezeichnet (bei denen Sie auch die Wahl zwischen verschiedenen "Modi" haben - keine Radwege - nur öffentliche Verkehrsmittel - so etwas). Sie können denken , wie auch die Reiseplanung eine Zeit sensibles Thema wird (dh , wenn Sie zu Fuß zurück , ein paar Kanten zurück, können Sie die U - Bahn fangen , die Sie zu Ihrem Ziel nimmt nach vorn als viel schneller , wenn Sie gerade versucht , die Kanten vorwärts zu navigieren mit den niedrigsten Kosten).

Die "Großen" speichern ihre Daten nicht in einer herkömmlichen Datenbank, sondern verwenden vorberechnete Graphen (willkommene Hadoop / Mapreduce-Cluster!). Wie Sie sich vorstellen können, werden diese Diagramme sehr groß. Daher kann es eine Herausforderung sein, die Kanten benachbarter Diagramme zu verbinden.

Wie auch immer, ich würde Ihnen empfehlen, sich einige multimodale Routing-Diagrammprojekte anzusehen:

Graphserver fällt mir ein. Nicht viel Dokumentation, aber viel reine Codierung (AFAIK, ich glaube, MapQuest verwendet eine Variante dieses Projekts für einige seiner Routing-Produkte).

Eine weitere Option wäre der OpenTripPlanner , hinter dem viele clevere Leute stecken (einschließlich Leute von Graphserver).

Ich bin nicht sicher, ob es neuer ist, aber pgRouting hat einen Shooting-Star-Algorithmus :

Der Shooting-Star-Algorithmus ist der neueste pgRouting-Algorithmus für kürzeste Wege. Seine Spezialität ist, dass es von Link zu Link routet, nicht von Vertex zu Vertex, wie es Dijkstra- und A-Star-Algorithmen tun. Auf diese Weise können beispielsweise Beziehungen zwischen Links definiert und einige andere vertexbasierte Algorithmusprobleme wie „parallele Links“ behoben werden, die dieselbe Quelle und dasselbe Ziel haben, aber unterschiedliche Kosten verursachen.

Die Network Analyst-Erweiterung von ESRI verwendet den von Ihnen erwähnten hierarchischen Ansatz , um die Lösungszeiten zu begrenzen:

Das Auffinden des genauen kürzesten Pfads in einem bundesweiten Netzwerk-Dataset ist aufgrund der großen Anzahl von Kanten, die durchsucht werden müssen, zeitaufwändig. Um die Leistung zu verbessern, können Netzwerk-Datasets die natürliche Hierarchie in einem Transportsystem modellieren, bei dem das Fahren auf einer Autobahn dem Fahren auf lokalen Straßen vorzuziehen ist. Sobald ein hierarchisches Netzwerk erstellt wurde, wird eine Modifikation des bidirektionalen Dijkstra verwendet, um eine Route zwischen einem Ursprung und einem Ziel zu berechnen.

Auf der ESRI-Site finden Sie ein sehr detailliertes Whitepaper mit Beispielen zu diesem Ansatz. Sie müssen sich jedoch anmelden, um ihn herunterzuladen (Whitepaper "Hierarchische Routen in ArcGIS Network Analyst").

Die Kontraktionshierarchie ist ein sehr schneller Algorithmus:

• http://algo2.iti.kit.edu/1087.php

Dieser Algorithmus ist RAM-freundlich, wenn eine Abfrage ausgeführt wird (um einen kontrahierten Graphen zu halten, ist etwas mehr RAM sowie eine massive Vorverarbeitung erforderlich).

Es gibt einige andere Algorithmen - einschließlich derjenigen, die das Routing für öffentliche Verkehrsmittel lösen:

• http://i11www.iti.uni-karlsruhe.de/members/thomas_pajor/publications

Microsoft macht auch einige Nachforschungen:

• http://research.microsoft.com/en-us/people/dadellin/

(Daniel Delling kommt auch aus Karlsruhe)

Sie erhalten eine schöne Einführung und einen Überblick über die verfügbaren Algorithmen:

• http://i11www.iti.uni-karlsruhe.de/teaching/sommer2012/routenplanung/index

Achtung: deutsche (!) Vorträge. Aber zumindest können die Überschriften Ihnen helfen, mehr Informationen (ALT, Arc-Flags, CHASE, ...) oder die angehängte Literatur zu erhalten!

aktualisieren

GraphHopper implementiert nun Kontraktionshierarchien und auch andere Algorithmen. Sie können die Demo auch ausprobieren .