Hola Matthias, On Tue, Dec 18, 2018 at 09:47:57PM +0100, Matthias Marquardt wrote:

Moin,

... ich möchte versuchen etwas mehr Licht in das Dunkel "wie funktioniert eigentlich das Routing auf Basis von OSM-Daten" bringen...

Um zu bewerten, ob etwas "richtig" oder "falsch" ist, muss man leider tief in den Source Code jeder einzelnen Engine blicken... Ein Blick unter die Haube bei GraphHopper fördert die Tatsache zu Tage, dass für das PKW-Routing im Standard auf den von dem Entwickler getauften 'Contraction Hierarchies' Algorithmus zurück gegriffen wird - dieser bietet eine unglaublich gute Performance wenn es darum geht quer durch den ganzen Kontinent zu routen... Diese Performance hat aber ihren Preis - ganz konkret bedeutet das, dass im 'CH-Mode' GraphHopper komplette die TurnRestrictions (AbbiegeHinweise) ignoriert.

Das ist aber eben kein attribute der Contracted Hierarchies. OSRM benutzt die auch und kann die Abbiegebeschränkungen. Das hat was mit Aufwand im Preprozessieren zu tun.

Es gibt für GraphHopper gute Gründe dies so zu tun - aber man muss eben (leider) wissen, für welchen Preis man sich diese Performance einkauft. Natürlich kennt & kann GraphHipper auch mit anderen Routing Algorithmen betrieben werden - aber dass muss eben jeder (der seine eigene Instanz betreibt) selbst konfigurieren und einreichten...

Ich nehme OSRM wie im github. Welche attribute wie in den Graph einfliessen kommt bei OSRM aus dem profile das in "lua" geschrieben ist. Also durchaus lesbar für jeden der mal 3 Zeilen Basic geschrieben hat. Da gibt es profiles für car, foot, bicycle und co. OSRM benutze ich vermutlich seit 7 Jahren oder so für alle möglichen Anwendungsfälle und das Zeugs funktioniert einfach. Ich nehme das "Standard" car profile für mein routing überwachung.

Natürlich bringt einem diese ganzen Algorithmus-Optimierungen bei den kurzen Strecken, über die sich hier die letzten Tage über die Tastatur heiß geschrieben wird überhaupt nix :-/

Jein - Der Punkt ist das du eine Routing Engine haben willst die funktioniert ohne das ich klicken muss und auch akzeptabel schnell ist. Nur um mal zu zeigen was ich derzeit berechne: Cluster Gütersloh checked with 4290 routes Cluster Rheda-Wiedenbrück checked with 1806 routes Cluster Harsewinkel checked with 930 routes Cluster Langenberg checked with 210 routes Cluster Rietberg checked with 1722 routes Cluster Verl checked with 420 routes Cluster Halle Westf. checked with 272 routes Cluster Steinhagen/Brockhagen checked with 306 routes Cluster Herzebrock-Clarholz checked with 552 routes Cluster A33 checked with 0 routes Cluster A2 checked with 1332 routes Cluster Delbrück checked with 812 routes Cluster Bielefeld checked with 4290 routes Cluster Oelde checked with 552 routes Cluster Bad Oeynhausen checked with 1260 routes Sind insgesamt ~18700 routen - alle 2 Stunden. Im moment läuft das so ~4 Minuten. Datensenke ist eine PostGIS Datenbank die die Geometrien, Dauer und Länge aller bisher berechneten Routen hält und eben die Knoten und Cluster die ich Teste. Vorprozessieren der Daten für OSRM (nrw pbf extract) dauert so [info] extraction finished after 71.9247s [info] Preprocessing : 497.628 seconds also rund ~10 Minuten (600 Sekunden). In der ganzen Pipeline sind aber noch viele andere tools so das ich etwa 90 Minuten Prozessierung für alles habe. OSRM und Routing ist da nur ein Bruchteil.

Also um es "kurz" zu machen - wenn Routing Engine1 einen "passenden" Weg ausspuckt, bedeutet dies leider nicht, dass das Tagging in OSM passt - eben sowenig, wenn Routing Engine2 einen falschen weg ausspuckt - alle Engines interpretieren die OSM-Tags die wir vergeben... Der eine implementiert A, der andere implementiert B - ein dritter A & B... und der vierte natürlich K (weil's "besser" ist)

Man suche eine Routing Engine die möglichst viel der OSM Attributierung unterstützt. Und da sehe ich im moment OSRM relativ weit vorne wie wir ja an diesem Vergleich wieder sehen. OSRM kann eben barrier, Abbiege- beschränkungen, lanes/surface als Attribut für die Durchschnittsgeschwindigkeit auf Straßen. Das sind dinge die MAPS.ME und OSMAnd auch benutzen um routen zu ermitteln.

Tatsächlich sollten wir versuchen das Tagging den Tatsachen entsprechend in OSM umzusetzen - ob alle Engines die richtigen Schlüsse (aus den vergebenen Tags) ziehen muss man den Entwicklern der Engines überlassen... Es ist aber auch so, dass man es mit bestimmten Tags einer Engine einfacher machen kann als einer anderen...

... und zu Guter letzt, sei nochmals erwähnt das zumindest GraphHopper Eure updates nicht OnTheFly verarbeitet - sondern zwischen Eurer Änderung und einer Änderung im Routing verhalten schon einige Tage vergehen können :-/

Deshalb mache ich ja meine "überwachung" der Routingfähigkeit der Karte alle 2 Stunden auf eigenen Extrakten. Ich will schnell mitbekommen wenn jemand in OWL Autobahnen oder wichtige Bundes/Land/Kreisstraßen vom routing abschneidet. Das hat so manches mal verhindert das hier ganze Inseln entstanden sind. Und mich interessieren typischerweise auch nicht die "absoluten routen" sondern wenn sich etwas ändert. Das absolute routing kann auch auf Fehler hindeuten, von daher macht es Sinn das mit einem Wachen Auge sich anzusehen. Oft ist das einfach partiell fehlende Attributierung die absurde routen erzeugt. (Die Nebenstraße die ein lanes=2 hat wird bevorzugt vor der Kreisstraße die kein lanes Attribut hat z.b.) Spannender finde ich aber die Deltas - D.h. mit einem mal werden alle Routen zu einem bestimmten Punkt 500m länger. Wenn man sich das dann ansieht ist es meist offensichtlich das irgendwas an den Daten kaputt gegangen ist. Und genau das überwache ich auch - D.h. werden routen +-30m länger kürzer dann gibts eine Mail. Damit triggern kleine Topologieänderungen nicht sofort eine mail, aber sollten Straßen unpassierbar sein kriege ich das mit. Flo -- Florian Lohoff f@zz.de UTF-8 Test: The 🐈 ran after a 🐁, but the 🐁 ran away