Bei Cyface haben wir uns neben der Erfas­sung des Straßen­zu­s­tands durch Crowd-Sourc­ing auch mit der Nutzung dieser Dat­en als Teil ein­er Kom­fort­nav­i­ga­tion beschäftigt. Dieser Artikel gibt einen Überblick der gewonnenen Erken­nt­nisse. Zunächst wird ein Überblick existieren­der Algo­rith­men gegeben. Daran schließt sich eine sicher­lich nicht erschöpfende Über­sicht ver­füg­bar­er Rout­ing­bib­lio­theken an. Solche Bib­lio­theken kön­nen als Grund­lage ein­er Kom­fort­nav­i­ga­tion ver­wen­det wer­den. Die Inhalte dieses Artikels basieren auf den Ergeb­nis­sen der Bel­e­gar­beit von Markus Son­tows­ki zum The­ma “Fahrradrout­ing unter Ein­beziehung der Straßen­qual­ität mit Google Android”.

Routingalgorithmen

Routin­gal­go­rith­men arbeit­en auf Graphen aus Knoten die über Kan­ten ver­bun­den sind. Im Falle des Verkehrsrout­ings repräsen­tiert ein Knoten eine Kreuzung und eine Kante eine Straße, als Verbindung von zwei Kreuzun­gen. Jede Kante ver­fügt über ein Gewicht, welch­es im ein­fach­sten Fall die Ent­fer­nung zwis­chen den bei­den ver­bun­de­nen Kreuzun­gen darstellt. Ein solch­er Beispiel­graph ist in der fol­gen­den Abbil­dung zu sehen.

Beispielgraph mit Kantengewichten

Beispiel­graph mit Kan­tengewicht­en

Die wichtig­sten Anforderun­gen an einen Routin­gal­go­rith­mus sind die Sta­bil­ität, Kor­rek­theit und Schnel­ligkeit der Suche.

Sta­bil­ität: Der Algo­rith­mus pro­duziert immer eine exak­te Lösung. Es entste­hen keine Abwe­ichun­gen durch Run­dung.

Kor­rek­theit: Der Algo­rith­mus ter­miniert immer und liefert dabei ein gemäß sein­er Def­i­n­i­tion fest­gelegtes Ergeb­nis, wie eine Liste von Kan­ten von Knoten A nach Knoten B.

Schnel­ligkeit der Suche: Kann über die Zeitkom­plex­ität als Anzahl der notwendi­gen Schritte abgeschätzt wer­den, die eine Eingabe in eine kor­rek­te Aus­gabe über­führen.

Die sieben im fol­gen­den Vorgestell­ten Algo­rith­men sind sta­bil, kor­rekt und besitzen neben anderen Eigen­schaften unter­schiedliche Geschwindigkeit­en.

Der Dijk­stra und der darauf auf­bauende A*-Algorithmus sind die wohl bekan­ntesten Ver­fahren. Dijk­stra entwick­elte seinen Algo­rith­mus bere­its 1959 und legte damit prak­tisch den Grund­stein für Routin­gal­go­rith­men. A* und der Ameise­nal­go­rith­mus ver­wen­den Heuris­tiken zur Bes­tim­mung der näch­sten Kante, was bedeutet, dass nicht immer der kürzeste Weg gefun­den wird, häu­fig aber schnell ein Ergeb­nis vor­liegt. Für den Algo­rith­mus von Kruskal müssen die Kan­ten zunächst sortiert wer­den, was in einem Straßen­netz einen uner­hört hohen Aufwand bedeutet. Der Algo­rith­mus von Prim wurde entwick­elt um diese Ein­schränkung zu umge­hen, wird aber in Graphen mit zu vie­len Knoten recht langsam. Die Algo­rith­men von Floyd und War­shall, sowie der Bell­man-Ford-Algo­rith­mus sind eher der Voll­ständigkeit wegen erwäh­nt. Sie wiesen in einem kom­plex­en Graphen wie dem Straßen­netz eine zu hohe Kom­plex­ität auf, haben in kleineren Net­zen aber einige nüt­zliche Eigen­schaften, die Dijk­stra, A* und Ameise­nal­go­rith­mus nicht bieten kön­nen. Die genaue Funk­tion­sweise jedes Algo­rith­mus über­steigt den Umfang dieses Beitrags und lässt sich über die Links in der Tabelle bei Wikipedia genau nachvol­lziehen.

Routingbibliotheken

Zum Glück ist es nicht nötig die vorgestell­ten Routin­gal­go­rith­men selb­st zu imple­men­tieren. Es existieren eine Rei­he frei ver­füg­bar­er und quellof­fen­er Bib­lio­theken für Rout­ing und Nav­i­ga­tion basierend auf Dat­en von Open Street Map.

Für Cyface ist es natür­lich von großem Inter­esse unter welch­er Lizenz die Bib­lio­thek ste­ht. Außer­dem haben wir die ver­wen­de­ten Algo­rith­men darauf unter­sucht, ob die Routen­berech­nung auf dem Client oder dem Serv­er erfol­gt, ob neben PkW auch Fahrräder unter­stützt wer­den, ob Nav­i­ga­tion­san­weisun­gen zur Ver­fü­gung ste­hen, ob Geocod­ing — also die Suche nach Routen über die Eingabe von Start- und Zieladresse — zur Ver­fü­gung ste­ht und natür­lich ob sich eine eigene Formel für die Kan­tengewichte (Straßen) inte­gri­eren lässt. Einige weit­ere eher neben­säch­liche Eigen­schaften der betra­chteten Sys­teme sind die Unter­stützung von Reverse Geocod­ing, die Nutzung des Höhen­pro­fils, benötigte externe Abhängigkeit­en und die Unter­stützung von Offline-Karten. Reverse Geocod­ing beze­ich­net dabei das find­en ein­er Adresse zu ein­er Geoko­or­di­nate, was zum Beispiel beim Klick auf einen Punkt auf der Karte von Bedeu­tung ist. Im Zuge der Recherche wur­den die Bib­lio­theken Graph­hop­per, BRouter, osm­droid mit osm­bonus-pack und die Open-Source-Rout­ing-Machine

Die fol­gende Tabelle stellt die betra­chteten Eigen­schaften für die unter­sucht­en Rout­ing­bib­lio­theken vor.

Komfortrouting

Es gibt neben der Straßen­qual­ität ver­schiedene andere Fak­toren die Ein­fluss auf die Wahl der angenehm­sten Route für Rad­fahrer haben. Darunter fall­en zum Beispiel auch die Länge und die Art der Straße. Weit­ere mögliche Ein­flussgrößen wie Lichtsig­nalan­la­gen, Stei­gun­gen, Vor­fahrtsstraßen, Son­derverkehrsmit­tel (z.Bsp.: Fähren) oder die Dichte des motorisierten Verkehrs wer­den an dieser Stelle nicht betra­chtet. Der Straßen­typ und die Länge der Straße bilden die Grund­lage der meis­ten existieren­den Routin­gal­go­rith­men. Aus ihnen berech­net sich ein Gewicht für jede Kante, des dem Rout­ing zugrunde liegen­den Graphen. Zu diesem Wert muss für das beab­sichtigte Kom­fortrout­ing der Straßen­zu­s­tand als Gewicht dazu gerech­net wer­den.

Da ein Straßen­ab­schnitt unter­schiedliche Qual­itätsab­schnitte haben kann, muss ein Ver­fahren genutzt wer­den, um all diese Werte zu einem Fak­tor zusam­men zu fassen. Es lässt sich zum Beispiel eines der fol­gen­den vier Ver­fahren ver­wen­den:

  1. Die schlecht­este Bew­er­tung wird genutzt, um die gesamte Kante zu bew­erten. Dies würde man tun, wenn man einen Fahrer nicht ein­mal über sehr kurze schlechte Straßen­ab­schnitte fahren lassen möchte.
  2. Die Mehrheit der Qual­itätswerte legt den Qual­itätswert für die gesamte Kante fest. Dadurch erre­icht man eine wesentlich glat­tere Ein­schätzung der Straßen. Straßen mit eini­gen weni­gen Anom­alien, die aber son­st glatt sind wür­den als befahrbar eingestuft. Das Risiko ist, dass man den Fahrer über eine einzelne sehr schlechte Stelle schickt und damit den Kom­fort deut­lich ein­schränkt.
  3. Es wird ein Schwellen­wert für die schlecht­este Qual­ität fest­gelegt. Die neg­a­tivste Qual­ität die diesen Schwellen­wert über­steigt, wird als Gewicht der ganzen Kante angenom­men. Mit diesem Ver­fahren lässt sich der Anteil zuläs­siger schlechter Straßen­ab­schnitte fein­er ein­stellen.
  4. Man berech­net das arith­metis­che Mit­tel aller Qual­itätswerte und run­det auf den näch­sten Wert. Dies ist ein sehr ein­fach­es Ver­fahren, das aber trotz­dem alle Qual­itätsstufen die auf einem Straßen­ab­schnitt vorkom­men in Betra­cht zieht. Ins­ge­samt hat man dann aber rel­a­tiv wenig Kon­trolle darüber ob Aus­reißer den Gesamtwert stark bee­in­flussen oder vielle­icht nur ungenü­gend ein­fließen. Alter­na­tiv lassen sich andere Mit­tel­w­erte (z.Bsp.: Medi­an) oder Perzen­tile ver­wen­den.

Mit dem Wert den man über eines dieser Ver­fahren bekommt lassen sich die Orig­i­nal­gewichte zum Beispiel gemäß fol­gen­der 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 Vari­able x ist ein Qual­itätswert zwis­chen 1 und 4, wobei 1 für sehr gute Qual­ität (blau) und 4 für sehr schlechte Qual­ität (rot) ste­ht. Durch n wird der „neu­trale“ Wert repräsen­tiert während Q das ursprüngliche, von der Rout­ing­bib­lio­thek gelieferte Kan­tengewicht ist. Der neu­trale Wert legt den Bere­ich fest ab dem eine Straße dank ihrer Ober­fläche auf- bzw. abgew­ertet wird. Er stellt sich­er, dass alle Kan­tengewichte mit guten Qual­itätswerten klein­er (x<n) und alle Kan­ten mit schlechter­er Qual­ität (x>n) höher gewichtet wer­den. Alle Kan­ten die genau die selbe Qual­ität­sklasse haben (x=n) behal­ten ihr Gewicht. Die Kon­stante \alpha kann genutzt wer­den, um die Änderung der Kan­tengewichte durch den Straßen­zu­s­tand im Ver­gle­ich zum Orig­i­nal­gewicht zu ver­stärken oder abzuschwächen. Die Gewich­tungs­funk­tion skaliert lin­ear. Es wäre möglich eine expo­nen­tielle oder log­a­rith­mis­che Funk­tion zu ver­wen­den. Ver­suche haben aber gezeigt, dass dadurch die Kan­tengewichte zu stark verän­dert wer­den.

Zusammenfassung

Solche und ähn­liche span­nende Anwen­dun­gen lassen sich mit den von Cyface erfassten Dat­en entwick­eln. Da die Nutzung guter Straßen den Ver­schleiß reduziert, ist eine kom­fort­able Nav­i­ga­tions­funk­tion ins­beson­dere für Fahrer teur­er oder auch älter­er Fahrzeuge inter­es­sant. Auch wer sparsam fahren oder die Reich­weite seines Elek­tro­fahrzeugs um einige Kilo­me­ter erhöhen möchte, wird mit ein­er gewichteten Nav­i­ga­tion basierend auf Cyface-Dat­en glück­lich. Falls Sie Inter­esse haben solche Anwen­dun­gen zu entwick­eln, kon­tak­tieren Sie uns.