Hallo,
Ich möchte ein paar Gedanken und Ergänzungen zu http://www.waze.com/wiki/index.php/Wie_Waze_Routen_kalkuliert zeigen. Die Seite ist sehr gut, enthält aber nicht alle frei verfügbaren Fakten.
Zuerst ein paar Ergänzungen:
Im Januar beschrieb Krankyd die Grundgeschwindigkeiten für die verschiedenen Straßentypen, wenn noch keine Durchschnittsgeschwindigkeit erfasst wurde:
https://world.waze.com/forum/viewtopic.php?f=28&t=14942&p=134288#p134288
In https://www.waze.com/wiki/index.php/How_Waze_determines_turn_/_keep_/_exit_maneuvers ist neben der Entscheidungsfindung an Kreuzungen auch beschrieben, wie es zu den verschiedenen Abbiegeansagen kommt.
Infos zur Beeinflussung des Routings durch Stau-Meldungen gibt es hier: https://world.waze.com/forum/viewtopic.php?f=4&t=13662&p=115452#p115452
Nicht für das Routing relevant aber trotzdem interssant zum Thema Locking: https://world.waze.com/forum/viewtopic.php?f=10&t=13094&p=115676#p115676
Zum Verhalten von Ramps: https://world.waze.com/forum/viewtopic.php?f=10&t=11468&p=108262&hilit=detouring#p108262
Zum Sinn von Kreuzungen am Ende von Sackgassen: https://world.waze.com/forum/viewtopic.php?f=10&t=8194
An die Posts in denen die Penaltys für “non driveable” Segmente standen komme ich leider nicht mehr ran. Da gab es im August/September eine Diskussion im Zusammenhang mit Tollroads. Betreff war irendetwas mit “Routing big problem” oder so.
OK, soweit zu prüfbaren Fakten. Jetzt ein paar Annahmen/Gedanken:
Die Diskussion erhitzt sich derzeit ja an diesem Auszugs:
Hieraus schließen manche, dass das City-Feld entscheidend für die Geschwindigkeit des Routingvorgangs ist. Als sicher kann gelten, dass der Routingalgorithmus nicht einfach startet und alle Segmente um den Startpunkt abklappert, bis er den Endpunkt gefunden hat. Es muss also eine Optimierung her. Welche Anforderungen muss diese Optimierung haben:
- sie muss den Algorithmus signifikant beschleunigen
- sie muss (speziell im Fall von Waze) auf verschiedenen Editierqualitäten funktionieren. Das sind handerstellte Gebiete ohne Basemap, durcheditierte Gebiete, wie z.B. viele Städte, uneditierte Basemap
- sie muss das Gebiet in Segmente gleicher Komplexität zerteilen
- sie muss zu reproduzierbaren Ergebnissen führen
- sie muss für alle routebaren Segmente funktionieren
Wie ist das jetzt, wenn das City-Feld für dieses Clustering benutzt wird:
- Beschleunigung des Routings ist prinzipiell möglich
- Nicht auf allen Segmenten gibt es ein ausgefülltes Cityfeld. Insbesondere bei nicht editierter Basemap gibt es das nicht.
- Das Cityfeld sorgt für eine sehr ungleichmäßige Clusterung. Insbesondere Großstädte haben extrem viele Segmente mit dem gleichen Cityfeld.
-
- viele Segmente haben kein gültiges Cityfeld. Die Fehlerkorrektur aus den umliegenden Segmenten kann in Einzelfällen funktionieren. Spätestens bei nocity-Segmenten wird sie versagen.
Es gibt natürlich Alternativen, die diese Probleme nicht haben. Eine Idee gibt die geografische Verteilung und Dichte von Postleitzahlbereichen. 
In Gebieten mit hoher Bevölkerungsdichte (und damit auch mit hoher Straßendichte) gibt es viele Postleitzahlenbereiche und in dünn besiedelten Gebieten sehr wenige. Das ist so, weil die Postzustellung ein ähnliches Problem wie die Routingoptimierung hat. Alle Zustellbezirke sollen ungefähr die gleiche Komplexität haben.
Hmmmm… Waze weiß nichts von Postleitzahlen! Waze hat aber unabhängig von der Benennung noch zwei andere Informationen, die es überall gibt ohne das Waze sich auf externe Quellen stützen muss. Das ist zum einen die örtliche Straßendichte und zum anderen die Straßentypen. Das die Straßentypen tatsächlich dafür herangezogen werden, dafür spricht der Abschnitt “Strecken-Berechnung für langen Distanzen” und auch die Beobachtung, dass es sich lohnt das Fernstraßennetz auf ein vernünftiges Maß auszudünnen (Herabstufung der K-Straßen von Minors auf Primary). Meine Idee wäre die Kreuzungen der verschiedenen Straßentypen gleichen Typs als Ausgangspunkte für einen Clusterbildungsalgorithmus zu nehmen. Das scheint mir doch auch ein Grund dafür zu sein, das Waze keine Ramps zwischen gleichen Straßentypen möchte. Stichworte im Netz wären z.B. http://de.wikipedia.org/wiki/Voronoi-Diagramm und http://de.wikipedia.org/wiki/Algorithmische_Geometrie
Gute Lektüre
tom
