OpenStreetMap Routenplanung mit Valhalla

Für eine kleine Spielidee, bei der ein virtuelles Logistikunternehmen koordiniert werden muss, hatte ich die Idee, die LKWs virtuell auf realen Straßen fahren zu lassen. Für das Routing mit Hilfe von OpenStreetMap gibt es eine Reihe von fertigen Servern. Am Ende hatte ich die Wahl zwischen OSRM und Valhalla. Meine Wahl fiel auf Valhalla, da dieser verspricht, wenig RAM zu verbrauchen.

OpenStreetMap Format link

Die auf OpenStreetMap spezialisierte Firma Geofabrik GmbH bietet die Karte in Ausschnitten als osm.pbf Files an. Nicht ganz offensichtlich kann auf der Download Webseite durch das anklicken von Regionen wie z.B. Europa auch kleinere Regionen wie Deutschland ausgewählt werden.

Um Routing-Anfragen schnell beantworten zu können, erzeugt Valhalla einen Graphen mit allen möglichen Verbindungen. Diese werden in (Teil-)Kacheln aufgeteilt, um nicht immer den gesamten Graphen im Speicher halten zu müssen.

Dieser Graph muss nur einmal generiert werden und kann bei Updates der Map bereits generierte Kacheln wiederverwenden. Nachdem ich mehrere Stunden auf die Fertigstellung für ganz Europa gewartet habe, habe ich das abgebrochen und nur Deutschland zum Testen genommen.

Für die Generierung habe ich ein DigitalOcean Droplet mit dem Docker Container gisops verwendet. Achtung: Der Navigationsgraph wird parallel zur Kartenregion relativ groß. Meine ersten Versuche scheiterten an der Festplattengröße. Da ich mir aber die Option offen halten wollte, das Droplet nach der Generierung wieder auf eine günstigere Größe zu verkleinern, habe ich dafür ein Volume eingebunden. Die Mapfiles habe ich auf der SSD des Droplets belassen, in der Hoffnung, dadurch etwas Geschwindigkeit herauszuholen.

Docker Container zum generieren und Server starten link

Mit dem folgenden Docker-Befehl kann der Valhalla-Server gestartet werden. Falls keine vorgenerierten Kacheln gefunden werden, werden diese automatisch erzeugt. Als Kartenmaterial wird die Datei germany.osm.pbf aus dem Home-Verzeichnis gemountet und das Ergebnis in das Volume geo geschrieben.

docker run -dt \
  --name valhalla_gis-ops \
  -p 8002:8002 \
  -v /mnt/geo/custom_files:/custom_files \
  -v ~/germany.osm.pbf:/custom_files/germany.osm.pbf \
  --env use_tiles_ignore_pbf=True \
  --env force_rebuild=False \
  --env force_rebuild_elevation=False \
  gisops/valhalla:latest

Nach dem erstmaligen Starten legt Valhalla in dem custom_files eine Konfigurationsdatei mit dem Namen valhalla.json an. Hier können Einstellungen vorgenommen werden, die die Größe des Ergebnisses und die Dauer wesentlich beeinflussen. Da ich später Routen für LKW und ggf. PKW berechnen möchte, habe ich z.B. Fuß- und Radwege deaktiviert.

Serverauslastung während der Generierung link

Wie in der Grafik zu sehen ist, nutzt Valhalla die meiste Zeit nur 1-2 CPUs. Gegebenenfalls könnte auch ein kleineres Droplet verwendet werden, das etwas länger läuft.

  • 4 vCPUs
  • 8 GB Memory
  • ca 3.3GB Graph

CPU Verbrauch Memory Verbrauch Disk Verbrauch

Routing Server verwenden link

Valhalla bietet verschiedene spannende Abfragen an. Ich habe mir nur die Routing Queries angeschaut.

Aktuell verwendet Valhalla eine REST API mit JSON Output. Aktuell in Arbeit ist auch ein Protobuf Endpunkt. Der Server hört auf dem im Docker Command angegebenen Port 8002.

Request link

Valhalla möchte den Request JSON Encoded als Query Parameter an :8002/route?json={} empfangen.

{
  "locations": [
    {
      "lat": "",
      "lon": "",
    },
    {
      "lat": "48.1548895",
      "lon": "11.4717965",
    }
  ],
  "costing": "truck",
  "units": "kilometers",
  "language": "de",
  "id": "my-trip-id"
}

In Valhalla werden wesentlich mehr Optionen angeboten. Die hier im Beispiel verwendeten werden kurz erläutert:

  • locations Alle Koordinaten die auf der Strecke liegen sollen.
  • coasting Für welche Fortbewegungsart soll die Route berechnet werden (Z.b. truck oder auto).
  • units In welcher Unit sollen alle angaben zurück gegeben werden.
  • language Valhalla gibt in dieser Sprache Straßennamen und Fahranweisungen zurück.

Response link

Die Routing-Antwort ist sehr umfangreich. Daher werde ich hier nur auf einige Punkte eingehen.

Das Segment trip.legs enthält die eigentliche Route. Jedes leg ist eine Verbindung zwischen den jeweiligen Orten.

{
  ...
  "legs": {
    "shape": "...",
    "summary": {
      "length": 34.4334,
      "time": 2.43434,

      ...
    },
    "maneuvers": [
      {
        "instruction": "",

        "verbal_transition_alert_instruction": "",
        "verbal_pre_transition_instruction": "",
        "verbal_post_transition_instruction": "",

        "street_names": [""],
        "begin_street_names": [""],

        "length": 34.4334,
        "time": 2.43434,

        "begin_shape_index": 1234,
        "end_shape_index": 2345,

        "toll": false,
        "highway": false,
        "rough": false,
        "gate": false,
        "ferry": false,

        ...
      }
    ]
  }
}

Die legs enthalten jeweils Manöver (maneuvers). Diese stellen die Anweisungen in der Navigation dar. Für mein Ziel, LKW-Fahrten zu simulieren, sind die Werte shape, begin_shape_index und end_shape_index interessant. Der Inhalt von shape enthält ein verpaketes Array mit den Koordinaten der Route. Diese sind so detailliert, dass sie auf der Karte eingezeichnet werden können und die Route darstellen.

Die Koordinaten des aktuellen Manöverzeitpunktes können aus dem Array über die Indizes begin_shape_index und end_shape_index ermittelt werden.

Virtuelle Position kalkulieren link

Ich aktualisiere die virtuelle Position per CronJob. Dazu speichere ich die aktuelle Manöverzeit und die Startzeit. Dann mape ich die Zeitspanne auf die Indexspanne und habe den aktuellen Index. Der Index zeigt auf die aktuelle Position.

func getCurrentIndex(now time.Time, startTime time.Time, endTime time.Time, startIndex int, endIndex int) int {
  if now.Sub(endTime) > 0 {
    return endIndex
  }

  indexSlots := endIndex - startIndex
  durationMilli := endTime.Sub(startTime).Milliseconds()
  elapsedTimeMilli := now.Sub(startTime).Milliseconds()

  milliPerSlot := durationMilli / int64(indexSlots)
  slot := elapsedTimeMilli / milliPerSlot

  index := startIndex + int(slot)
  if index > endIndex {
    return endIndex
  }

  return index
}

Wenn die Endzeit in der Vergangenheit liegt, wird die nächste Manöverzeit als aktuelle Manöverzeit und die Endzeit des letzten Manövers als Startzeit festgelegt.