Suche
Schnelle Routenplanung basierend auf OpenStreetMap

GraphHopper – ein flexibler Routenplaner

Peter Karich

© Shutterstock.com / VECTORWORKS_ENTERPRISE

Routenplanung ist ein wichtiger Teil der mobilen Gesellschaft und kommt zum Einsatz, um den täglichen Stau zur Arbeit zu vermeiden oder zur Planung einer Fahrradtour. Auch im geschäftlichen Bereich ist Routenplanung oft ein essenzieller Teil, z. B. für die Müllabfuhr, Pizzalieferung oder beim Planen von Mitfahrgelegenheiten, wo oft Tausende oder sogar Millionen Routen in Sekunden berechnet werden sollen.

GraphHopper ist ein Java-Programm zur schnellen Berechnung von Routen basierend auf den Daten von OpenStreetMap (OSM). Es wurde 2012 unter der Apache-Lizenz veröffentlicht und stetig weiterentwickelt. Die aktuelle Version 0.4.0 ist im März 2015 erschienen und wird auch für die Beispiele in diesem Artikel herangezogen. GraphHopper läuft auf allen von Java unterstützten Betriebssystemen, inklusive Android, Raspberry Pi und sogar auch auf iOS. Letzteres ist durch das Projekt J2ObjC möglich. Die Daten werden standardmäßig aus dem OpenStreetMap-Projekt importiert. Andere Datenformate wie Ordnance Survey sind auch in der Entwicklung.

GraphHopper erledigt „nur“ das Routenfinden mittels komplexer Graphalgorithmen, hat also keine Funktionalität für Kartenvisualisierung, Tourenoptimierung oder Adresssuche integriert. Allerdings spielt GraphHopper gut mit existierender Software für diese Spezialgebiete zusammen.

GraphHopper-Nutzung

GraphHopper ist schon heute bei kleinen und großen Firmen im Produktiveinsatz, vor allem bei Logistikunternehmen und Unternehmen wie komoot und GPSies, die Outdooranwendungen entwickeln. Denn GraphHopper ist sehr flexibel und kann somit eine breite Anforderungspalette für das Routing erfüllen. Die Standardprofile Auto, Fahrrad, Fußgänger aber auch Motorrad, Mountainbike und Rennrad sind mit dabei. Die Nutzung von GraphHopper ist ganz einfach, wenn Java und Git installiert sind:

git clone git://github.com/graphhopper/graphhopper.git
cd graphhopper; git checkout 0.4
./graphhopper.sh web europe_germany_berlin.pbf

Danach läuft der Webserver Jetty unter http://localhost:8989, wo eine lokale Version von GraphHopper Maps ausprobiert werden kann (Abb. 1). GraphHopper Maps orchestriert im Wesentlichen drei Komponenten: die Onlinekarten, die Adresssuche und das Routing, wobei nur Letzteres von GraphHopper bereitgestellt wird. Die anderen Komponenten werden durch verschiedene Open-Source-Projekte bzw. Services implementiert. Unter der JSON-Web-Schnittstelle http://localhost:8989/route kann man auf die Routenberechnung über die meisten Programmiersprachen zugreifen, wobei Java und JavaScript von Haus aus unterstützt werden.

Einfache Änderungen des Routings sind über die Konfigurationsdatei config.properties möglich. Um z. B. Auto, Fahrrad und Fußgänger gleichzeitig zu unterstützen, gibt man diese Profile für den Import an:

graph.flagEncoders=bike,foot,car|turnCosts=true

Man kann auch Höhendaten für die Routenberechnung und -ausgabe mit einbeziehen:

graph.elevation.provider=srtm

Das Routingprofil bike2 kann dadurch Berge vermeiden, und es wären beispielsweise Profilverbesserungen für das Profil Mountainbike (mtb) denkbar, welches dann Berge bevorzugt.
Weiterhin verwendet GraphHopper standardmäßig beim ersten Fahrzeug in der flagEncoders-Liste den Speed-up-Modus (Kasten: „Speed-up Modus vs. Flexibilitätsmodus“). Da dies zwar das Routing selbst erheblich beschleunigt, aber den Import deutlich verlängert, kann es ausgeschalten werden:

prepare.chWeighting=no

GraphHopper-Integration

GraphHopper kann sehr leicht über Java und andere JVM-Sprachen in eigenen Anwendungen eingesetzt werden. Zunächst fügt man GraphHopper z. B. via Maven zu den Abhängigkeiten hinzu:

<dependency>
  <groupId>com.graphhopper</groupId>
  <artifactId>graphhopper</artifactId>
  <version>0.4.0</version>
</dependency>

Danach kann man OSM-Daten importieren, die man vorher beispielsweise von download.geofabrik.de heruntergeladen hat:

GraphHopper hopper = new GraphHopper();
hopper.setOSMFile("berlin.osm.pbf");
hopper.setGraphHopperLocation("./graph-cache");
hopper.setEncodingManager(new EncodingManager("bike,foot"));
hopper.importOrLoad();

Der Import wird das erste Mal möglicherweise einige Minuten dauern, die nächsten Aufrufe von importOrLoad sind aber meist unter einer Sekunde machbar, da der Graph nur von der Festplatte gelesen wird. Danach kann man beliebig viele Routen, auch mittels mehrerer Threads, ausrechnen lassen (Listing 1).

GHRequest req = new GHRequest(52.52583,13.382034, 52.496578,13.397141).
      setVehicle("car").setWeighting("fastest").setLocale(Locale.GERMAN);
GHResponse rsp = hopper.route(req);
if(rsp.hasErrors())
   throws new RuntimeException("route has errors" + rsp.getErrors());
InstructionList instructions = rsp.getInstructions();
PointList pointList = rsp.getPoints();

Für die Abbiegeanweisungen (Turn Instructions) kann eine von mehr als 25 verschiedenen Sprachen über die Methode setLocale bei jeder Anfrage angegeben werden.

GraphHopper-Nutzung am Beispiel der Distanzmatrix

Im konkreten Anwendungsfall eines Logistikunternehmens wird eine optimale Tour mit mehreren Zwischenpunkten gewünscht. Ein Außendienstmitarbeiter, der beispielsweise vier Orte besuchen muss oder ein Paketlieferant mit vier Paketen haben dann die Wahl zwischen 4!, also 24 möglichen Touren. Schon bei mehreren Dutzend Paketen kann auch ein leistungsstarker Server nicht mehr alle möglichen Touren innerhalb einer sinnvollen Zeit berechnen, sodass man in der Praxis auf heuristische Lösungen dieses Optimierungsproblems angewiesen ist. Zusätzlich kommen dann noch Nebenanforderungen wie einzuhaltende Zeiträume der Anlieferung oder notwendige Fähigkeiten der Fahrer hinzu. Für diese Optimierungsaufgaben gibt es spezielle Tools, auch Open Source und in Java geschrieben, wie z. B. OptaPlanner und jsprit. Diese Optimierungstools benötigen eine so genannte Distanzmatrix, also die Informationen der Distanz zwischen allen Punkten, um so die optimale Reihenfolge der finalen Endtour zu bestimmen:

| A | B | C | D
A |0 |2 |1 | 7
B |3 |0 |5 | 8
C |2 |6 |0 | 2
D |8 |9 |3 | 0
Im Beispiel ist der Weg von A nach B 2 km lang, von A nach C 1 km, von D nach C 3 km etc. In den Optimierungstools können statt der Distanz auch weitere bzw. andere Informationen wie Zeit und Kraftstoffkosten berücksichtigt werden. Diese Matrix ist meist nicht symmetrisch, da eine Rückroute etwa durch Einbahnstraßen länger bzw. kürzer sein kann. Mit GraphHopper und zwei for-Schleifen ist die Berechnung einer solchen Matrix leicht möglich und lässt sich auch leicht in die genannten Optimierungstools integrieren (Listing 2).
List<GHPoint> pointList = getPackageDeliveryLocationList();
for( int fromIndex = 0; fromIndex < pointList.size(); fromIndex++) {
  for( int toIndex = 0; toIndex < pointList.size(); toIndex++) {
    if(fromIndex == toIndex) continue;
    GHPoint fromPoint = pointList.get(fromIndex);
GHPoint toPoint = pointList.get(toIndex);
GHRequest request = new GHRequest(fromPoint, toPoint).setVehicle("car").
    setWeighting("fastest").
    putHint("calcPoints", false).
    putHint("instructions", false);
GHResponse response = hopper.route(request);
    distanceMatrix[fromIndex][toIndex] = response.getDistance();
    timeMatrix[fromIndex][toIndex] = response.getMillis();
  }
}

Die Hinweise an GraphHopper mittels putHint beschleunigen die Routenberechnung noch zusätzlich, da es im Falle der Distanzmatrix meist nicht notwendig ist, die Abbiegehinweise (Instructions) und nicht die Routengeometrie zu berechnen. Weitere Geschwindigkeitsverbesserungen um das bis zu 150-fache stehen im Matrix-Add-on durch Spezialalgorithmen anstelle der zwei for-Schleifen zur Verfügung. Damit ist die Berechnung großer Matrizen mit mehreren Millionen Routen in Sekunden möglich und macht so den gesamten Optimierungsprozess auch für größere Probleme in wenigen Sekunden bzw. Minuten möglich.

GraphHopper-Programmierung: Graphalgorithmus

Ein Straßennetz besteht aus Straßen und Kreuzungen. Damit der Computer eine Vorstellung davon bekommt, verwendet man einen Graphen als Datenstruktur, der aus Kanten und Knoten besteht. Die Knoten („Kreuzungen“) sind durch die Kanten („Straßen“) verbunden, und auf den Kanten können Eigenschaften wie die Länge abgespeichert werden. Um eine Route von A nach B in diesem Graphen zu berechnen, verwendet man üblicherweise den Dijkstra-Algorithmus. Jedoch wird man für lange Routen über 500 km oder bei wenig Speicherplatz schnell an die Hardwaregrenzen stoßen. In den letzten Jahren wurden daher so genannte hierarchische Abkürzungsalgorithmen entworfen, die mehrere Größenordnungen schneller sind und auch weniger Speicher verwenden. GraphHopper verwendet einen solchen Algorithmus standardmäßig im so genannten Speed-up-Modus (Kasten: „Speed-up Modus vs. Flexibilitätsmodus“ ). Eine andere Möglichkeit zur Beschleunigung wären Heuristiken, von denen GraphHopper aber bisher noch keinen Gebrauch macht.

Speicherdatenstruktur

Ein weiteres Geheimnis der hohen Geschwindigkeit von GraphHopper auch im Flexibilitätsmodus ist die speichereffiziente Datenhaltung und Graphtraversierung. Java hat aktuell noch den großen Nachteil gegenüber C++, dass große Listen von kleinen Objekten meist Speicherverschwendung sind, wenn man das Standard-Java-API verwendet. Will man beispielsweise viele Punkte mit nur zwei Eigenschaften latitude und longitude halten, so wird man List<Point> mit der Klasse class Point { double latitude; double longitude; } verwenden.

Dies bedeutet aber bei einer 64-Bit-JVM, dass man schon 6 bis 8 Byte pro Point-Objekt für eine Referenz zu diesem nur 2*8 Byte großen Objekt benötigt. Um dies zu vermeiden, kann ein Wrapperobjekt Points verwendet werden:

class Points { double[] latitudes; double[] longitudes; }
Der Zugriff und die Verarbeitung werden jedoch verkompliziert. Eine Verbesserung erreicht man mittels dem Flyweight-Entwurfsmuster (Listing 3).

public class FPoints { 
  private double[] latitudes; private double[] longitudes; 
    private Point accessorPoint = new Point();
  public Point getPoint(int index) {
    accessorPoint.setLatitude(latitudes[index]);
    accessorPoint.setLongitude(longitudes[index]);
    return accessorPoint;
  }
}

Allerdings ist diese Liste FPoints nun nicht mehr Thread-sicher. In GraphHopper findet dieses Muster bei dem Traversieren des Graphens Anwendung. Um beispielsweise alle benachbarten Kanten eines Knotens fromNode zu finden, wird ein EdgeExplorer erstellt, der einen wiederverwendbaren edgeIterator erzeugt und dadurch das oft millionenfache Allokieren beim Traversieren durch den Graphen unnötig macht (Listing 4).

Graph graph = hopper.getGraph();
EdgeExplorer edgeExplorer = graph.createEdgeExplorer();
EdgeIterator edgeIterator = edgeExplorer.setBaseNode(fromNode);
while(edgeIterator.next()) {
  // listet die Name und Länge (in Metern) der Nachbarkanten auf:
  String edgeName = edgeIterator.getName();
  double distance = edgeIterator.getDistance();
}

Dadurch, dass pro Thread ein EdgeExplorer erstellt werden kann, ist GraphHopper beim Berechnen der Route über GraphHopper.route auch Thread-sicher und kann z. B. in einer Webanwendung problemlos verwendet werden. Beispielsweise beim Schreiben von neuen Kantenattributen muss man jedoch aktuell noch sicherstellen, dass nur ein Thread auf den Graphen Zugriff hat.

Flexible Gewichtung

GraphHopper kann nicht nur den kürzesten (shortest) oder den schnellsten (fastest) Weg berechnen. Beim Fahrradprofil bike werden auch Wege entlang von offiziellen Radrouten bevorzugt. Eine eigene Gewichtung kann man leicht umsetzen, indem man das Weighting-Interface implementiert. Das gesamte Vorgehen ist in der Dokumentation anhand eines Beispiels beschrieben.

Abb. 1: GraphHopper Maps

Abb. 1: GraphHopper Maps

Speed-up Modus vs. Flexibilitätsmodus

GraphHopper bietet einen Flexibilitätsmodus und Speed-up-Modus, der mittels Konfigurationsdatei oder Java-API eingestellt werden kann.
Der Flexibilitätsmodus erlaubt die Integration von benutzerspezifischen Änderungen pro Anfrage, wie es z. B. notwendig ist, wenn Fahrradfahrer Treppen vermeiden möchten oder bis zu einer gewissen Höhe akzeptieren, wenn dadurch der Umweg zu groß würde. Dieser Modus wird in der Konfigurationsdatei mit prepare.chWeighting=no eingeschaltet.
Beim Standardmodus, dem Speed-up Modus, muss das konkrete Profil mit allen Einstellungen schon vor der Anfrage beim Import feststehen, also z. B. die Information, ob und wie Treppen beim Fahrradprofil toleriert werden. Die notwendigen Vorberechnungen werden durch Contraction Hierarchies ausgeführt und ermöglichen eine sehr schnelle Berechnung von Routen. Dadurch ist es möglich, mit Standardhardware mehrere hundert Routen pro Sekunde auszuliefern und das fast unabhängig von deren Länge.

Aufmacherbild: Grasshopper vector von Shutterstock.com / Urheberrecht: VECTORWORKS_ENTERPRISE

Verwandte Themen:

Geschrieben von
Peter Karich
Peter Karich
Peter Karich ist Physiker und arbeitet als freiberuflicher Softwareentwickler hauptsächlich an „Routing-Problemen“ mit GraphHopper. Vorher hat er an Algorithmen für Sprachassistenten und Suchtechnologien wie Elasticsearch gearbeitet.
Kommentare

Hinterlasse einen Kommentar

2 Kommentare auf "GraphHopper – ein flexibler Routenplaner"

avatar
400
  Subscribe  
Benachrichtige mich zu:
trackback

[…] from heise.de. The map matching is now also usable as a web API in the lastest master branch. A German article about version 0.4 is available and you cannot only try it online but also offline in the browser […]

trackback

[…] from heise.de. The map matching is now also usable as a web API in the lastest master branch. A German article about version 0.4 is available and you cannot only try it online but also offline in the browser […]