Routing auf OSM-Daten - Abseits der A30 Diskussion

Matthias Marquardt marquardt24 at gmail.com
Di Dez 18 21:47:57 CET 2018


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.

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...

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 :-/

Wer einwenig tiefer in die Welt der Algorithmen einrauchen möchte kann dies
hier tun -
https://www.graphhopper.com/blog/2017/08/14/flexible-routing-15-times-faster/


Warum kann es wichtig sein, dass man zugunsten der Performance auf einige
"Details" verzichtet? - An der Uni-Heidelberg beschäftigt man sich unter
anderem mit dem Thema Katastrophenschutz - dort wurden diverse Algorithmen
entwickelt (die dann auch wieder in GraphHopper geflossen sind), die es
ermöglichen für z.B. Rettungsfahrzeuge "Erreichbarkeiten & Zeiten" auf
Basis von OSM-Daten zu errechnen - also wie weit kann z.B. ein Krankenwagen
von einem bestimmten Ort aus in 25min fahren? Das kann man zwar für
Krankenhäuser auch einmal "fix" berechnen (und die Laufzeit ist dann auch
egal) - aber im Fall von Erdbeben, Großfeuern etc. ist es zusätzlich
notwendig gewisse Gebiete "zu sperren"... Und spätestens jetzt ist es
essentiell das man sehr schnell 1000'de von möglichen Routen und Strecken
auf einmal zu berechen... Deswegen kommt man (aka GraphHopper) auf so
"merkwürdige" Ideen...

Andere Routing-Engines haben möglicherweise "andere" Optimierungen - oder
aber sind nur für relativ kurze Strecken zu gebrauchen - manche sind auch
recht gut dokumentiert und man kann nachlesen, welche OSM-Attribute welche
rolle spielen - Valhalla z.B. -
https://wiki.openstreetmap.org/wiki/OSM_tags_for_routing/Valhalla

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)

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 :-/

Grüße
Matthias
<http://about.me/matthiasmarquardt>


Mehr Informationen über die Mailingliste OSM