Einfache Routensuche mit OSM-Daten

1. Wir beschaffen die Daten:

Wir holen die Innenstadt von Köln ab (ca. 40Mb):

wget -O data.osm http://www.overpass-api.de/api/xapi?map?bbox=6.938,50.920,6.978,50.951

2. Wir erzeugen einen Routing-Graphen:

Die OSM-Datei enthält in dieser Reihenfolge Einträge für Changesets, für Nodes, für Ways und für Relationen. Wir interessieren uns nur für die Nodes und die Ways.

  1. Zu jedem OSM-Objekt sammeln wir die Attribute im Hash %attr und verwerfen sie am Ende des Objektes.
  2. Beim Einlesen einer Node speichern wir die Koordinaten dieser Node in den Hashes %lon und %lat.
  3. Beim Einlesen eines Ways speichern wir die Liste der Nodes, aus denen der Way besteht, im Array @nodeIds.
  4. Nach dem Einlesen eines Ways erfolgt die eigentliche Arbeit:
    • aus den Attributen wird bestimmt, ob dieser Way für uns überhaupt interessant ist; uninteressante Ways werden verworfen.
    • aus den Attributen wird bestimmt, wie schnell wir auf dem Way unterwegs sind, und zwar getrennt nach Vorwärts- und Rückwärtsrichtung: wenn wir Einbahnstraßen berücksichtigen, ist die Geschwindigkeit in Rückwärtsrichtung 0.
    • Danach wird der Way in Teilstücke zerschnitten, für jedes Teilstück wird die Länge berechnet, aus Länge und Geschwindigkeit die Länge in Zeiteinheiten, sodann diese Graphkante ausgegeben als Datensatz mit den Ids der beiden Knoten und der berechneten Länge (sowie der Quelle der Daten, also Id des Ways, die Richtung und den benutzten Abschnitt des Ways). Außerdem wird je benutzter Node ein Datensatz mit den Koordinaten dieser Node geschrieben.

Die gleiche Datenvorverarbeitung und der gleiche Routing-Graph werden auch von der einfachen Erreichbarkeitsanalyse genutzt.

Diesen Ablauf implementiert das Perl-Skript analyze.pl” (~60 Zeilen Code).

Wir rufen das Skript auf:

./analyze.pl <data.osm >database.csv

Und erhalten eine Textdarstellung des Routing-Graphen in der Datei database.csv (~2.1Mb).

Der Graph enthält Knoten mit Id und Koordinaten:

node n743325638 6.9722186 50.9463142

und gerichtete Kanten mit Angabe der verbundenen Knoten, der Entfernung, und der Quelle der Daten, bestehend aus OSM-Way-Id, Richtung und Segmentnummer: 

arc n743325638 n743325592 10.0407049925005 w59865404 f 0

3. Wir suchen eine Route:

Wir benutzen eine Datenstruktur, die für jeden Knoten folgende Daten enthält:

  • die Länge der besten Route vom Startknoten bis zu diesem Knoten (%pastDistance);
  • der Vorgängerknoten auf der besten Route (%predecessor);
  • eine untere Grenze der Entfernung zum Zielknoten (%futureDistance).

Ein weiterer Hash %estimatedDistance enthält die Summe aus %pastDistance und %futureDistance, aber nur für die Knoten, die zur Bearbeitung anstehen. Die untere Grenze der Entfernung zum Zielknoten futureDistance berechnen wir aus der Luftlinien-Entfernung und der minimalen Geschwindigkeit.

Wir setzen die pastDistance des Startknotens auf 0, berechnen die futureDistance und nehmen ihn als einzigen Knoten in die Bearbeitungsliste auf. Die Bearbeitungsliste besteht zu Anfang nur aus dem Startknoten. Alle übrigen Knoten haben (implizit) ein pastDistance von Unendlich.

Aus der Bearbeitungsliste entnehmen wir jeweils den Knoten mit der geringsten Summe aus Länge des (bisher) kürzesten Pfades zu diesem Knoten und der geschätzten Entfernung von diesem Knoten bis zum Zielknoten. Zweimal Lesen hilft.

Wir verfolgen alle von diesem Knoten ausgehenden Kanten und bestimmen das pastDistance der erreichten Knoten als Summe aus dem pastDistance des Ausgangsknotens und der Länge der jeweils benutzen Kante. Falls der erreichte Knoten bereits ein pastDistance hatte, bekommt er als neues pastDistance das Minimum aus altem und neuem Wert.

Wenn wir einen Knoten zum ersten Male erreichen oder wenn wir eine bessere Route zu ihm gefunden haben, berechnen wir die Gesamtdistanz estimatedDistance (wieder) und nehmen den Knoten (wieder) in unsere Bearbeitungsliste auf. Außerdem speichern wir den gerade bearbeiteten Knoten als Vorgänger nach %predecessor.

Diesen Ablauf wiederholen wir, bis unsere List nur noch Knoten enthält, für die die geschätzte Gesamtentfernung größer oder gleich der bisher bekannten besten Entfernung zum Zielknoten (pastDistance) ist oder die Liste leer ist.

Wenn der Zielknoten einen Vorgänger in predecessor hat, können wir die Vorgängerkette zurücklaufen zum Startknoten und erhalten die gesuchte Route in umgekehrter Reihenfolge.

Diesen Ablauf implementiert das Perl-Skript routing.pl” (~110 Zeilen Code).

Wir rufen das Skript mit Start- und Zielposition auf:

./routing.pl 50.9364 6.9493 50.9402 6.9564 <database.csv >routing.txt

und erhalten das Ergebnis der Routensuche in der Datei “routing.txt” (~12Kb).

Diese enthält den Startknoten start und den Zielknoten goal (letzterer nur bei Erfolg, sonst nogoal), jeweils mit Angabe der Koordinaten: 

start 6.9492976 50.9364097
goal  6.9564016 50.9401804

Außerdem die zur Route gehörenden Kanten route und die Kanten auf den besten Wegen zu den Knoten, die nicht auf der Route liegen best: 

route 6.9564016 50.9401804 6.9564111 50.9402424
best  6.9533500 50.9388801 6.9533046 50.9388989

4. Wir machen das Ergebnis der Analyse sichtbar:

Dazu dient uns eine HTML-Seite routing.htm (~180 Zeilen HTML und JavaScript).

Wir legen diese HTML-Seite routing.htm und das Ergebnis der Routensuche routing.txt in ein Verzeichnis auf einem Webserver, rufen die Seite auf, und erfreuen uns des Ergebnisses. Und danach dürfen wir spielen.

5. Einschränkungen:

Die wenigen Codezeilen implementieren natürlich nur eine rudimentäre Routensuche. Beispiele für Einschränkungen sind:

  • Bei Flächen (area=yes) laufen wir nur am Rand entlang;
  • Nutzungsbeschränkungen (access=*) und Abbiegerestriktionen werden ignoriert.
  • Weil Ways an jedem einzelnen node aufgetrennt werden, hat der Graph mehr Knoten und Kanten als nötig; dies verlangsamt den Algorithmus.
  • Ein binär gespeicherter Graph wird schneller eingelesen.
  • Die Bearbeitungsliste wird für jeden Knoten neu sortiert. Eine geschickte Datenstruktur beschleunigt die Suche erheblich.

Diese Liste ist nicht vollständig.

Diese Routensuche wurde im Rahmen des Verzehrs einer weiteren Ecke Almkäse
in Verbindung mit dem Genuss eines weiteren Glases Rotwein entwickelt.
Der Quellcode ist öffentlich zugänglich.