Hilfe bei der Auswahl eines geeigneten Routingmoduls

16

Ich baue ein Routenplanungssystem auf, aber ich muss noch entscheiden, welche zugrunde liegende Routing-Engine ich verwenden werde. Bisher habe ich pgrouting und neo4j gefunden.

Ich habe mein Streckennetz in einer postgresql / postgis-Datenbank (aus einem Shapefile importiert). Ich habe Abfragen gemacht, um Knoten zu extrahieren (Endpunkte von Wegen, an denen Sie eine Entscheidung treffen müssen, in welche Richtung oder in Sackgassen) und um Kanten zu extrahieren (die oft aus mehreren aufeinanderfolgenden Wegen bestehen). Alle meine Kanten sind bidirektional.

Mein Hauptziel ist es, Routen in diesem Netzwerk mit einem A-Stern-Algorithmus zu berechnen, bei dem Entfernung = Kosten.

Mein Gefühl sagt mir, dass eine Graph-Datenbank wie neo4j der richtige Weg ist (wie es scheint, für diesen Zweck gemacht zu sein), aber sie scheinen nicht standardmäßig A-Star zu unterstützen und es gibt auch keinen wirklichen Sinn für Geometrie . Es scheint besser für soziale Netzwerke geeignet zu sein als für Karten.

  • Würde das Verfugen meine Bedürfnisse erfüllen?
  • Ist es schnell genug für On-the-Fly-Abfragen (+ -2000 Knoten, + -4000 Kanten)? Normalerweise wäre dies ein paar ms für A-Star, aber ich bin nicht sicher über diese Implementierung in SQL.
  • Gibt mir das Verfugen eines A-Sterns eine Liste von Knoten und Kanten?
  • In den meisten Beispielen, die ich über das Verfugen sehe, stelle ich fest, dass es normalerweise eine Liste von Befehlen nach der Berechnung der Route gibt (wie "An X nach links abbiegen, usw."). Produziert Pgrouting dies oder stammt es von einem anderen System?

Hoffentlich kann mir jemand einige Informationen über das zu wählende System geben. Neo4j, Pgrouting oder ein anderes System.

pgrouting routing mrg
quelle
3
Ich denke, dass die meisten Routing-Algorithmen nicht mit einem "Sinn für Geometrie" arbeiten, sondern ein geometrisches Attribut berechnet und als Kosten verwendet wird (dh Entfernungsmaß einer Polylinie). Ich habe Neo4j noch nie benutzt, aber es sieht wirklich gut aus und ich werde es vielleicht bald benutzen. Ich habe mir nur die Dokumentation angesehen und es scheint möglich zu sein, A-Star zu verwenden: docs.neo4j.org/chunked/stable/graph-algo.html docs.neo4j.org/chunked/stable/… pgRouting ist ebenfalls in der Lage, und Ich bin ein großer Fan davon. Es wäre interessant, die Leistung dieser beiden Lösungen zu vergleichen.
Allan Adair
Zunächst würde ich vorschlagen, urbansim als Open-Source -Landnutzungsmodell zu betrachten. Was Ihre Routing-Frage betrifft, wenn dies eine Planungsanwendung ist, dann würde ich vorschlagen, zuerst Software wie TransCAD, CUBE, PLANAR oder EMME / 2 auf Funktionalität und Benutzeroberfläche zu prüfen. Normalerweise geben sie 1 oder 2 Stunden Demo-CDs ihrer Software heraus (Software, die Sie ein oder zwei Stunden lang ausführen können, um ein Gefühl dafür zu bekommen). Wenn Sie etwas für die Online- oder Desktop-Nutzung erstellen möchten, schauen Sie sich pgRouting an. Aus Erfahrung ist es jedoch manchmal nicht so einfach, wie der Workshop / das Tutorial es darstellt.
Dassouki
Ich habe mit A-Star-Arbeiten angefangen und es ist großartig! Es beantwortet meine ersten 3 Fragen mit Ja. Ich frage mich immer noch, ob jemand hier etwas über das Generieren ausführlicher Navigationsanweisungen weiß. Gibt es ein Werkzeug, das mit einer Injektion zusammenarbeitet, die aus der Ausgabe der berechneten Route ausführliche Anweisungen generiert ("Nach 200 m links abbiegen, usw.")?
mrg

Antworten:

8

Ich untersuche derzeit das gleiche Problem wie Sie, um einen Forschungsbericht zu verfassen. Bevor ich anfing, diese beiden Datenbanken zu testen, hatte ich die gleiche Annahme wie Sie. Diese Neo4j-Grafikdatenbank wäre die perfekte Lösung für diese Art von Problem. Und teilweise ist es das, aber mit vielen Problemen.

Das erste Problem ist, dass A-Star nur implementiert wird, wenn Sie eine eingebettete Datenbank verwenden, nicht über die REST-API (Server). Wenn Sie Neo4j mit der REST-API verwenden möchten, wird nur der Dijkstra-Algorithmus unterstützt. Das zweite Problem ist der Hardwarespeicherbedarf für Neo4j. Für das Routing (Dijkstra) in "größeren" Netzwerken benötigen Sie viel RAM. Für großes Netzwerk meine ich so etwas wie die Größe der deutschen OSM- Straßendatenbank. Ich habe meine Tests auf einem 6-GB-RAM-Server durchgeführt (das ist alles, was ich derzeit habe) und nur kleinere Netzwerke konnten ohne OutOfMemory-Ausnahmefehler geroutet werden. "Kleine" Netze in meinen Testfällen sind beispielsweise OSM-Straßendatenbanken für Österreich oder Kroatien. Gleichzeitige Abfragen habe ich noch nicht mit Neo4j getestet.

Alle diese Probleme gibt es bei pgRouting nicht. Speicher ist kein solches Problem, aber gleichzeitige Abfragen erhöhen den Speicherbedarf. Wenn Sie beispielsweise zwei gleichzeitige Anforderungen haben, wird die doppelte Menge an Speicher benötigt. Dies war auch für einen deutschen OSM-Datensatz kein Problem, da pgRouting alle gleichzeitigen Anforderungen problemlos weiterleitet.

Leistung: In den meisten Fällen übertrifft Neo4j pgRouting. Aber nur, wenn genügend Speicher für den angegebenen Datensatz vorhanden ist und sich alle Knoten und Beziehungen im Speicher befinden (Hot Start). Die Zunahme / Abnahme der Leistung hängt von vielen Faktoren ab, hauptsächlich jedoch von der Größe des Netzwerks und der Entfernung (Hops) zwischen Quell- und Zielknoten.

Ihre Netzwerkgröße ist recht klein, sodass Sie keine Probleme mit dem Arbeitsspeicher haben sollten. Wahrscheinlich ist Neo4j keine schlechte Wahl, aber Sie müssen sich an ein "kleines" anderes Datenmodell anpassen als in Standardrelationsdatenbanken.

Um Ihnen Fragen zu beantworten:

  • In pgRouting müssen Sie sich nicht um die bereits implementierte AStar-Implementierung in SQL kümmern.
  • Ja, mit pgRouting können Sie eine Liste von Knoten und Kanten erstellen
  • Ich glaube nicht, dass pgRouting Ihnen solche Informationen liefern kann, ohne einige benutzerdefinierte Abfragen zu umgehen. Aber vielleicht irre ich mich, vielleicht hat jemand dies getan und kann Ihnen bei dieser Frage weiterhelfen.

Ich weiß nicht, ob es Ihnen direkt helfen wird, aber einer der schnellsten Routing-Server, den ich gefunden habe, ist osm2po . Es funktioniert mit OSM-Datenmengen und ist ziemlich schnell. Derzeit ist nur dijkstra implementiert, aber der Entwickler hat auch AStar angekündigt. Ich hoffe, dass Ihnen etwas davon hilft. :)

Mario Miler
quelle
Es ist gut, von jemandem zu hören, der beide Systeme tatsächlich getestet hat. Mittlerweile habe ich viel mehr Erfahrung mit dem Verfugen. Ich habe festgestellt, dass pgrouting das gesamte Diagramm für jede Abfrage erstellt und daher für große Netzwerke (Größe in Deutschland) ziemlich langsam ist, sodass ich nicht verstehe, warum für pgrouting weniger Speicher als für Neo4j erforderlich ist. Mein nächster Versuch wird sein, den gesamten Graphen in RAM zu statisieren und darauf zu routen (mit neo4j, nx_spatial usw.), um eine schnellere Antwort für das Echtzeitrouting zu gewährleisten.
23.
Ja, je größer der Graph ist, desto größer ist der Unterschied zwischen pgrouting und neo4j. Wenn Sie den gesamten Graphen speichern, ist dies wahrscheinlich die schnellste Lösung, keine Frage. Neo4j ist ziemlich schnell, wenn alle Grafiken in den Speicher geladen sind. Ich weiß nichts über nx_spatial, ich habe es nicht getestet, aber vielleicht werde ich es tun. Ich glaube, dass es sogar Neo4j übertreffen könnte. Diese Lösung ist jedoch gut, wenn sie für Ihre Anwendung akzeptabel ist.
Mario Miler
1
@mrg nicht sicher, ob es für Sie immer noch ein Problem ist, aber es gibt OSRM (C ++) und GraphHopper (Java). Beide skalieren auf weltweite Graphen und zB braucht GraphHopper unter 1GB für Deutschland (wo ich der Autor von bin)
Karussell
Karussell, danke für die Info! Ich hatte bereits OSRM gefunden, aber GraphHopper ist neu für mich.
mrg
0

Sie können sich auch unser RW Net 4-Paket ansehen (www.routeware.dk). Mit A * kann der kürzeste Pfad direkt aus einer SHP-Datei berechnet werden. Das Basispaket zu 500 € scheint für Ihre Bedürfnisse ausreichend zu sein.

Uffe Kousgaard
quelle
Vielen Dank für Ihre schnelle Antwort, aber mein Projekt befindet sich noch in einer Phase, in der ich nicht sicher bin, ob es sich lohnt, jetzt Geld auszugeben. Außerdem habe ich mich intensiv mit meinen Daten befasst, so dass bisher Unbekanntes in Angriff genommen wurde.
Mrg