Wie Waze Routen kalkuliert

Zurück

Die Thematik "Benennen von Straßen" wurde in der Vergangenheit oft sehr kontrovers diskutiert. Um die Sache besser zu verstehen, muss man sich zunächst ansehen, wie Waze Routen berechnet.

Hier eine kurze Zusammenfassung, die einen ersten Einblick in die Routing-Logik von Waze bieten soll. Dazu gilt zu sagen, dass Waze selbst keinesfalls den Routing Algorithmus veröffentlichen wird. Warum? Niemand gibt seine besten Karten aus der Hand!

Anfragen an den Routing-Server

Wenn Du eine Route berechnen lässt, wird die Anfrage an den Routing-Server gesandt. Die berechnete Route wird dann an Deinen Client zurückgesandt. Die berechnete Route ist von Deinen Einstellungen im App-Menü "Navigation" abhängig (schnellste/kürzeste Route, Autobahnen oder Mautstraßen meiden usw.)

Routenberechnung im Client

Der Client führt simple Routenberechnungen selbständig durch. Diese Berechnungen beinhalten keine Echtzeit-Verkehrsdaten. Sie werden nur aufgrund der Durchschnitte der Segmente seit dem letzten Update geführt, welche auch bereits im Client-Cache hinterlegt sein müssen. Eine Berechnung im Client findet nur statt, wenn keine Netzwerkverbindung besteht während einer Routenberechnung.

Straßentypen und Kreuzungen

Das Routing ist auch abhängig von Straßentypen, die aufgrund der Distanzen ins Routing mit einbezogen werden (eine Tabelle dazu findest Du weiter unten). Ebenso wird die Anzahl der Kreuzungen in Betracht gezogen, um von Punkt A nach Punkt B zu gelangen. In der Regel gilt für eine Kreuzung ein Penalty (Zeit Zuschlag) von 5 Sekunden bei der Berechnung einer Route (Fake-Nodes ausgenommen = Kreuzungen, die nur 2 Segmente verbinden und keine andere Abbiege-Möglichkeit bieten). Das Routing zieht längere Segmente mit weniger Kreuzungen (auch Fake-Nodes) kürzeren Segmenten mit mehreren Kreuzungen vor.

Zeit und Geschwindigkeit

Wenn ein Wazer die Segmente befährt, werden die Geschwindigkeiten vom System registriert und ein Durchschnitt gespeichert. Bei der Berechnung der Routen, werden die Geschwindigkeiten der einzelnen Segmente berücksichtigt. Ebenso wird die Zeit berücksichtigt, die benötigt wird, um ein Segment zu durchfahren. Wurde ein Segment nie befahren, ist auch keine Durchfahrts-Geschwindigkeit in diesem Segment gespeichert.

Standard-Geschwindigkeiten

Für den Routing-Server gelten Standard-Geschwindigkeiten für unbefahrene Straßen.

- Freeway	130 km/h
- Major Highway	110 km/h
- Minor Highway	90 km/h
- Primary Street	50 km/h
- Street	50 km/h

Aktuelle Fahrgeschwindigkeiten

Waze registriert Echtzeit-Verkehrsmeldungen wie Staus und beginnt eine neue Strecke zu berechnen, da die aktuellen Geschwindigkeiten mit der gespeicherten Geschwindigkeit in den Segmenten verglichen werden. Mit dieser Methode wird man um Staus herum geroutet. Hierzu gilt zu sagen: Wenn Du eine Route planst, die mehr als 30 Minuten dauert, werden nicht die aktuellen Verkehrsdaten am Endpunkt in die Berechnung einfließen. Ein Beispiel: Wenn Du eine Route von München nach Hamburg planst, werden nicht die aktuellen Staus in Hamburg in die Berechnung einfließen. Eine neue Berechnung am aktuellen Ort löst dieses Problem.

Fernstreckennetz

Das sogenannte "Least-Cost-Routing" durch das Straßennetz von Waze ist eine sehr rechenintensive Angelegenheit. Damit es dennoch klappt, innerhalb einer möglichst kurzen Zeit eine Route zu generieren, benutzt Waze eine Vielzahl von Tricks.

Einer dieser Tricks ist die Verwendung des Fernstreckennetzes, also jene Straßen, die in die Kategorie Highway fallen: Alle Freeways, Ramps, Major- und Minor Highways sind in einem Netz zusammengefasst, das nur für längere Routen verwendet wird.

Bei Planung einer Route versucht Waze mit Hilfe aller befahrbaren Straßen, dieses Fernstreckennetz zu erreichen, dafür wird in einem Umkreis von bis zu 25 km gesucht. Einmal auf diesem Fernstreckennetz angelangt, findet Waze schnell eine Route, bevor es auf den letzten 25 km dann wieder über alle befahrbaren Straßen plant.

Dieser Vorgang wird für jeden möglichen Übergang in und aus dem Fernstreckennetz wiederholt, bis am Ende eine optimale Route übrigbleibt.

Ein weiterer Trick ist die Gruppierung von mehreren Segmenten, entsprechend ihres Straßennamens und City-Eintrags.

Je mehr Segmente hierbei berücksichtigt werden müssen, desto länger dauert auch die Kalkulation. Ist eine bestimmte Anzahl an Segmenten erreicht, bricht der Routing-Server die Berechnung ab.

Deswegen werden z.B. Autobahnen mittlerweile zu möglichst großen Segmenten zusammengefasst (einheitlicher Name, kein City-Eintrag). Da es wohl auch niemanden gibt, der z.B. am Autobahnkilometer 157 wohnt, wäre ein Eintrag im City-Feld auch sinnlos.

Penalty-System

Für die Erstellung einer Route verwendet Waze auch ein System von Penalties (Zeit Zuschläge).

Das Penalty-System ist dafür verantwortlich, den schnellsten Weg zu finden. Es eliminiert mögliche Routen, indem es für die Berechnung mehr Zeit (pro Segment oder Kreuzung) vergibt als erwartet.

Penalty-Typen:

• Nicht befahrbare Wege wie: Walking-Trail, Pedestrian Boardwalk, Railroad, Runway erhöhen die voraussichtliche Ankunftszeit (ETA) um 1 Stunde.
• "Parking-Lot-Road" und "Private Road" erhalten ebenfalls einen höheren Penalty, da sie nicht für durchgehendes Routing zur Verfügung stehen.
• Toll-Roads: Wenn "Avoid toll roads" in der Waze-App eingeschaltet ist, wird der Penalty für die Segmente um ein vielfaches multipliziert; ohne diese Einstellung im Client ist die Mautstraße für Waze eine normal befahrbare Straße!
• U-Turns: Scharfwinklige Kurven sowie U-Turns selbst erhalten einen enormen Zeitzuschlag für die Ankunftszeit. Einen Penalty erhalten auch U-Turns, die aus drei Segmenten bestehen. Wenn das U-Turn-Segment länger als 15 Meter lang ist, wird kein Penalty hinzugefügt.

Fahrtrichtung:

• Fahrtrichtung des Segments nicht gesetzt (Unknown) +0,30 Sekunden zusätzlich. Dies gilt für Amerika und alle Länder mit Base-Map.
• Richtung automatisch gesetzt bei Fahrten entgegen der Fahrtrichtung: Für jede Fahrt entgegen der Fahrtrichtung wird ein 30-Sekunden-Zuschlag zur ETA addiert.

Strecken-Berechnung für lange Distanzen:
Welche Straßentypen Waze ins Routing einbezieht, ist von den Distanzen abhängig.

• 0–15 km – Alle Straßentypen werden ins Routing einbezogen.
  Anmerkung: Das bezieht sich auch auf die Kategorie "Non-Drivable"
• 15–20 km – Alle Straßentypen außer Streets.
• 20–30 km – Alle Straßentypen außer Streets und Primary Streets.
• 30–200 km – Nur Minor, Major und Freeways.
• mehr als 200 km – nur Freeways.

Bearbeiten von Kreuzungen legt diese eindeutig fest

In Gegenden mit Base-Map gibt es einen Unterschied zwischen Kreuzungen, die vom User bearbeitet oder geupdatet wurden und den Base-Map-Kreuzungen, die nie bearbeitet oder befahren und mit dem Base-Map-Upload-Prozess erstellt wurden. Diese Kreuzungen erscheinen, als wären die Abbiegungen verboten, sie können jedoch geroutet werden, als ob sie erlaubt wären. In der Regel bevorzugt der Routing-Algorithmus Segmente und Kreuzungen, die vom User gesetzt wurden. Aber falls der Weg viel länger wird oder keiner vorhanden ist, wird trotzdem auch über nicht eindeutig gesetzte Abbiegungen geroutet. Eine Straße in beiden Richtungen befahrbar zu machen ändert den Status der Kreuzungen nicht. Wird eine Kreuzung bearbeitet, ist sie gültig, wie in Gegenden ohne Base-Map. Die Kreuzung wird nicht gelockt, wenn nur eine Abbiegung geändert wird.

Parking-Lot-Road

Die "Parking-Lot-Road" wird verwendet, um - wie der Name schon sagt - Parkplätze zu erstellen. Auch werden sie vom Routing-Server sozusagen ausgeschlossen. Waze hat im Juni 2012 den Algorithmus so angepasst, dass durch einen Penalty verhindert wird, durch die Parkplätze zu navigieren. Der Penalty besteht beim Übergang vom Parkplatz auf das normale Straßensystem. Das heißt: Es kann auf den Parkplatz und aus ihm heraus navigiert werden aber nicht durch den Parkplatz hindurch, um ggf. eine Abkürzung zu erzeugen. Es ist daher nicht sinnvoll, auf Parkplätzen die Straßentypen zu mischen. Ein Parkplatz hat durchgängig "Parking-Lot-Road" als Straßentyp.

Verkehrsmeldungen

Für die Erstellung von Verkehrsmeldungen bedient sich Waze anderer Methoden, indem die City-Namen aus der Umgebung herangezogen werden.

Das korrekte Bearbeiten der Autobahn-Anschlussstellen ist daher zwingend nötig. Weiterführende Straßen sollten nach Möglichkeit City- und Straßennamen enthalten, um eine Meldung so genau wie möglich einzugrenzen.

Staumeldungen

Staumeldungen (farbcodiert) veranlassen das Routing eine neue Strecke zu berechnen, um den Stau zu umfahren. Farbcodierte Segmente (ausgeleuchtet) entstehen wenn die gespeicherte Durchschnitts-Geschwindigkeit eines Segments unterschritten wird.

Melden von Staus wirkt sich auf das Entstehen eines farbcodierten Segments aus:
Meldet ein User einen Stau auf einer Straße, beschleunigt dies das Entstehen eines farbcodierten Segments, sofern dabei auch die gespeicherte Geschwindigkeit unterschritten wird.

Die Staumeldung eines Benutzers über das Client-Menü alleine genügt nicht, um farbcodierte Segmente zu erzwingen.

Zurück