Bei Cyface haben wir uns neben der Erfassung des Straßenzustands durch Crowd-Sourcing auch mit der Nutzung dieser Daten als Teil einer Komfortnavigation beschäftigt. Dieser Artikel gibt einen Überblick der gewonnenen Erkenntnisse. Zunächst wird ein Überblick existierender Algorithmen gegeben. Daran schließt sich eine sicherlich nicht erschöpfende Übersicht verfügbarer Routingbibliotheken an. Solche Bibliotheken können als Grundlage einer Komfortnavigation verwendet werden. Die Inhalte dieses Artikels basieren auf den Ergebnissen der Belegarbeit von Markus Sontowski zum Thema „Fahrradrouting unter Einbeziehung der Straßenqualität mit Google Android“.
Routingalgorithmen
Routingalgorithmen arbeiten auf Graphen aus Knoten die über Kanten verbunden sind. Im Falle des Verkehrsroutings repräsentiert ein Knoten eine Kreuzung und eine Kante eine Straße, als Verbindung von zwei Kreuzungen. Jede Kante verfügt über ein Gewicht, welches im einfachsten Fall die Entfernung zwischen den beiden verbundenen Kreuzungen darstellt. Ein solcher Beispielgraph ist in der folgenden Abbildung zu sehen.
Beispielgraph mit Kantengewichten
Die wichtigsten Anforderungen an einen Routingalgorithmus sind die Stabilität, Korrektheit und Schnelligkeit der Suche.
Stabilität: Der Algorithmus produziert immer eine exakte Lösung. Es entstehen keine Abweichungen durch Rundung.
Korrektheit: Der Algorithmus terminiert immer und liefert dabei ein gemäß seiner Definition festgelegtes Ergebnis, wie eine Liste von Kanten von Knoten A nach Knoten B.
Schnelligkeit der Suche: Kann über die Zeitkomplexität als Anzahl der notwendigen Schritte abgeschätzt werden, die eine Eingabe in eine korrekte Ausgabe überführen.
Die sieben im folgenden Vorgestellten Algorithmen sind stabil, korrekt und besitzen neben anderen Eigenschaften unterschiedliche Geschwindigkeiten.
| Algorithmus | Zeitkomplexität | Vorteile | Nachteile |
|---|---|---|---|
| Dijkstra-Algorithmus (mit Fibonacci-Heap) | O(m + n log n) | findet immer den Weg mit den geringsten Kosten | relativ langsam berechnet den Weg zu allen Knoten |
| A*-Algorithmus | n.a. | schnell komplett optimal | Hoher Speicherbedarf |
| Ameisen-Algorithmus | O(n log n) | schneller als exakte Algorithmen häufig sehr effizient | Zufallsbasiert Effizienz schlecht nachzuweisen |
| Verbesserter Algorithmus von Kruskal | O(m + n log n) + Sortierzeit | Sehr effektiv bei wenigen Knoten | Sortierte Kanten als Vorraussetzung |
| Algorithmus von Prim(mit Fibonacci-Heap) | O(m + n log n) | Effektiver als Kruskal auf vielen Knoten | Sehr komplexe Struktur mit Fibonacci-Heap |
| Algorithmus von Floyd und Warshall | O(n³) | Wegberechnung zu allen Knoten | langsam |
| Bellman-Ford-Algorithmus | O(nm) | Verwendung negativer Kanten möglich | langsam |
Der Dijkstra und der darauf aufbauende A*-Algorithmus sind die wohl bekanntesten Verfahren. Dijkstra entwickelte seinen Algorithmus bereits 1959 und legte damit praktisch den Grundstein für Routingalgorithmen. A* und der Ameisenalgorithmus verwenden Heuristiken zur Bestimmung der nächsten Kante, was bedeutet, dass nicht immer der kürzeste Weg gefunden wird, häufig aber schnell ein Ergebnis vorliegt. Für den Algorithmus von Kruskal müssen die Kanten zunächst sortiert werden, was in einem Straßennetz einen unerhört hohen Aufwand bedeutet. Der Algorithmus von Prim wurde entwickelt um diese Einschränkung zu umgehen, wird aber in Graphen mit zu vielen Knoten recht langsam. Die Algorithmen von Floyd und Warshall, sowie der Bellman-Ford-Algorithmus sind eher der Vollständigkeit wegen erwähnt. Sie wiesen in einem komplexen Graphen wie dem Straßennetz eine zu hohe Komplexität auf, haben in kleineren Netzen aber einige nützliche Eigenschaften, die Dijkstra, A* und Ameisenalgorithmus nicht bieten können. Die genaue Funktionsweise jedes Algorithmus übersteigt den Umfang dieses Beitrags und lässt sich über die Links in der Tabelle bei Wikipedia genau nachvollziehen.
Routingbibliotheken
Zum Glück ist es nicht nötig die vorgestellten Routingalgorithmen selbst zu implementieren. Es existieren eine Reihe frei verfügbarer und quelloffener Bibliotheken für Routing und Navigation basierend auf Daten von Open Street Map.
Für Cyface ist es natürlich von großem Interesse unter welcher Lizenz die Bibliothek steht. Außerdem haben wir die verwendeten Algorithmen darauf untersucht, ob die Routenberechnung auf dem Client oder dem Server erfolgt, ob neben PkW auch Fahrräder unterstützt werden, ob Navigationsanweisungen zur Verfügung stehen, ob Geocoding – also die Suche nach Routen über die Eingabe von Start- und Zieladresse – zur Verfügung steht und natürlich ob sich eine eigene Formel für die Kantengewichte (Straßen) integrieren lässt. Einige weitere eher nebensächliche Eigenschaften der betrachteten Systeme sind die Unterstützung von Reverse Geocoding, die Nutzung des Höhenprofils, benötigte externe Abhängigkeiten und die Unterstützung von Offline-Karten. Reverse Geocoding bezeichnet dabei das finden einer Adresse zu einer Geokoordinate, was zum Beispiel beim Klick auf einen Punkt auf der Karte von Bedeutung ist. Im Zuge der Recherche wurden die Bibliotheken Graphhopper, BRouter, osmdroid mit osmbonus-pack und die Open-Source-Routing-Machine
Die folgende Tabelle stellt die betrachteten Eigenschaften für die untersuchten Routingbibliotheken vor.
| Graphhopper | BRouter | osmdroid mit osmbonus-pack | Open Source Routing Machine | |
|---|---|---|---|---|
| Lizenz | Apache 2.0 | GPL v3 | Apache 2.0 | MIT |
| Algorithmen | Dijkstra mit Contraction Hierarchies | Dijkstra & A* | Abhängig von Routing-Bibliothek (übl.: Dijkstra & A*) | Dijkstra mit Contraction Hierarchies |
| Ausführung | Server/Client | Client | Server | Server |
| Fahrradprofil | Ja | Ja | Ja | Ja |
| Gewichtungsformel integrierbar | ja | Ja | n.a. | Ja |
| Navigations- anweisungen | Ja | externe App | Ja | Ja |
| Geocoding | Ja | Ja | Ja | Ja |
| Reverse Geocoding | Ja | externe App | Ja | Ja |
| Anzeige des Höhenprofils | Ja | Ja | Ja | Nein |
| benötigte Bibliotheken | trove4j & slf4j | Externe App zur Routendarstellung | slf4j | libboost, libstxxl, libxml2, libesparsehash, libbz2, zlib1g, libzip. libgomp1, liblua, libgdal, libtbb, libexpat |
| Offlinekarten | Ja | externe App | Caching geladener Karten | Nein |
Komfortrouting
Es gibt neben der Straßenqualität verschiedene andere Faktoren die Einfluss auf die Wahl der angenehmsten Route für Radfahrer haben. Darunter fallen zum Beispiel auch die Länge und die Art der Straße. Weitere mögliche Einflussgrößen wie Lichtsignalanlagen, Steigungen, Vorfahrtsstraßen, Sonderverkehrsmittel (z.Bsp.: Fähren) oder die Dichte des motorisierten Verkehrs werden an dieser Stelle nicht betrachtet. Der Straßentyp und die Länge der Straße bilden die Grundlage der meisten existierenden Routingalgorithmen. Aus ihnen berechnet sich ein Gewicht für jede Kante, des dem Routing zugrunde liegenden Graphen. Zu diesem Wert muss für das beabsichtigte Komfortrouting der Straßenzustand als Gewicht dazu gerechnet werden.
Da ein Straßenabschnitt unterschiedliche Qualitätsabschnitte haben kann, muss ein Verfahren genutzt werden, um all diese Werte zu einem Faktor zusammen zu fassen. Es lässt sich zum Beispiel eines der folgenden vier Verfahren verwenden:
- Die schlechteste Bewertung wird genutzt, um die gesamte Kante zu bewerten. Dies würde man tun, wenn man einen Fahrer nicht einmal über sehr kurze schlechte Straßenabschnitte fahren lassen möchte.
- Die Mehrheit der Qualitätswerte legt den Qualitätswert für die gesamte Kante fest. Dadurch erreicht man eine wesentlich glattere Einschätzung der Straßen. Straßen mit einigen wenigen Anomalien, die aber sonst glatt sind würden als befahrbar eingestuft. Das Risiko ist, dass man den Fahrer über eine einzelne sehr schlechte Stelle schickt und damit den Komfort deutlich einschränkt.
- Es wird ein Schwellenwert für die schlechteste Qualität festgelegt. Die negativste Qualität die diesen Schwellenwert übersteigt, wird als Gewicht der ganzen Kante angenommen. Mit diesem Verfahren lässt sich der Anteil zulässiger schlechter Straßenabschnitte feiner einstellen.
- Man berechnet das arithmetische Mittel aller Qualitätswerte und rundet auf den nächsten Wert. Dies ist ein sehr einfaches Verfahren, das aber trotzdem alle Qualitätsstufen die auf einem Straßenabschnitt vorkommen in Betracht zieht. Insgesamt hat man dann aber relativ wenig Kontrolle darüber ob Ausreißer den Gesamtwert stark beeinflussen oder vielleicht nur ungenügend einfließen. Alternativ lassen sich andere Mittelwerte (z.Bsp.: Median) oder Perzentile verwenden.
Mit dem Wert den man über eines dieser Verfahren bekommt lassen sich die Originalgewichte zum Beispiel gemäß folgender Formel anpassen:
f(x) = \begin{cases} \frac{x}{n} \cdot &Q \cdot \alpha & \textrm{für } x > n \\ &Q & \textrm{für } x = n \\ \frac{x}{n} \cdot &Q \cdot \frac{1}{\alpha} & \textrm{für } x < n \end{cases} \{(x, n, \alpha) \in \mathbb{N} | x \in 1 .. 4, n \in 1 .. 4, \alpha \geq 1\}
Die Variable x ist ein Qualitätswert zwischen 1 und 4, wobei 1 für sehr gute Qualität (blau) und 4 für sehr schlechte Qualität (rot) steht. Durch n wird der „neutrale“ Wert repräsentiert während Q das ursprüngliche, von der Routingbibliothek gelieferte Kantengewicht ist. Der neutrale Wert legt den Bereich fest ab dem eine Straße dank ihrer Oberfläche auf- bzw. abgewertet wird. Er stellt sicher, dass alle Kantengewichte mit guten Qualitätswerten kleiner (x<n) und alle Kanten mit schlechterer Qualität (x>n) höher gewichtet werden. Alle Kanten die genau die selbe Qualitätsklasse haben (x=n) behalten ihr Gewicht. Die Konstante \alpha kann genutzt werden, um die Änderung der Kantengewichte durch den Straßenzustand im Vergleich zum Originalgewicht zu verstärken oder abzuschwächen. Die Gewichtungsfunktion skaliert linear. Es wäre möglich eine exponentielle oder logarithmische Funktion zu verwenden. Versuche haben aber gezeigt, dass dadurch die Kantengewichte zu stark verändert werden.
Zusammenfassung
Solche und ähnliche spannende Anwendungen lassen sich mit den von Cyface erfassten Daten entwickeln. Da die Nutzung guter Straßen den Verschleiß reduziert, ist eine komfortable Navigationsfunktion insbesondere für Fahrer teurer oder auch älterer Fahrzeuge interessant. Auch wer sparsam fahren oder die Reichweite seines Elektrofahrzeugs um einige Kilometer erhöhen möchte, wird mit einer gewichteten Navigation basierend auf Cyface-Daten glücklich. Falls Sie Interesse haben solche Anwendungen zu entwickeln, kontaktieren Sie uns.