Routing auf OSM-Daten - Abseits der A30 Diskussion

Mi Dez 19 14:18:05 CET 2018

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 at zz.de
        UTF-8 Test: The 🐈 ran after a 🐁, but the 🐁 ran away