Das Routing
Posted: Sat Nov 17, 2012 4:00 pm
Hallo,
Ich möchte ein paar Gedanken und Ergänzungen zu http://www.waze.com/wiki/index.php/Wie_ ... 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. ... 88#p134288
Infos zur Beeinflussung des Routings durch Stau-Meldungen gibt es hier: https://world.waze.com/forum/viewtopic. ... 52#p115452
Nicht für das Routing relevant aber trotzdem interssant zum Thema Locking: https://world.waze.com/forum/viewtopic. ... 76#p115676
Zum Verhalten von Ramps: https://world.waze.com/forum/viewtopic. ... ng#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:
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
Ich möchte ein paar Gedanken und Ergänzungen zu http://www.waze.com/wiki/index.php/Wie_ ... 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. ... 88#p134288
In https://www.waze.com/wiki/index.php/How ... _maneuvers ist neben der Entscheidungsfindung an Kreuzungen auch beschrieben, wie es zu den verschiedenen Abbiegeansagen kommt.krankyd wrote:Just to confirm (sorry that this is in English) - here are the speeds you should be working with:
Freeways -130 km/h
Major - 110 km/h
Minor - 90 km/h
Primary/ street - 50 km/h
Once you start driving on the road, of course this will change with the average cross times.
Infos zur Beeinflussung des Routings durch Stau-Meldungen gibt es hier: https://world.waze.com/forum/viewtopic. ... 52#p115452
Nicht für das Routing relevant aber trotzdem interssant zum Thema Locking: https://world.waze.com/forum/viewtopic. ... 76#p115676
Zum Verhalten von Ramps: https://world.waze.com/forum/viewtopic. ... ng#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:Ein weiter 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.
- 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
- 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.
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
