Das Routing

Moderators: Unholy, lizcrime, Error79, argus-cronos

Das Routing

Postby aeytom » 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

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.


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.

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:

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.


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. Image

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
AM: Berlin South/East, Fläming; Nexus 4
Image
aeytom
 
Posts: 284
Joined: Sat Nov 27, 2010 8:14 am
Location: Berlin/Germany
Has thanked: 2 times
Been thanked: 3 times

Re: Das Routing

Postby argus-cronos » Sat Nov 17, 2012 7:08 pm

Danke Tom für das Zusammensuchen all der Infos hier ;)

aeytom wrote: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

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.

aeytom wrote:Infos zur Beeinflussung des Routings durch Stau-Meldungen gibt es hier: https://world.waze.com/forum/viewtopic. ... 52#p115452

Ist beides eingeflossen.

aeytom wrote: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.

Sehr technische Seite, natürlich nicht ungültig, aber wird bereits durch die Seite Kreuzungen (Junction Style Guide) abgedeckt.

aeytom wrote:Zum Sinn von Kreuzungen am Ende von Sackgassen: https://world.waze.com/forum/viewtopic.php?f=10&t=8194

Dies wird definitiv durch die Seite Kreuzungen (Junction Style Guide) abgedeckt.

aeytom wrote:Nicht für das Routing relevant aber trotzdem interssant zum Thema Locking: https://world.waze.com/forum/viewtopic. ... 76#p115676

Dazu gibts hier: https://world.waze.com/forum/viewtopic.php?f=10&t=14036 noch den Rest

aeytom wrote: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.


Letzte Meldung dazu ist: wir schauens uns an ;-) Es geht im Grund darum, dass aufgrund der tollroads meiden ungewöhnliche Routings vorgeschlagen werden.

Gruss
Argus
argus-cronos
Waze Global Champs
Waze Global Champs
 
Posts: 6464
Joined: Sat Apr 03, 2010 3:00 pm
Location: Basel, Switzerland
Has thanked: 813 times
Been thanked: 1042 times

Re: Das Routing

Postby argus-cronos » Thu Nov 21, 2013 4:48 pm

Es kommen die Angaben, die in nanoRep publiziert sind, Segment-Geschwindigkeiten, tageszeitabhängige Faktoren, historische Daten zusammen etc... Einzelne Probleme sind wirklich konkret anzuschauen, ist auf jeden Fall besser.
argus-cronos
Waze Global Champs
Waze Global Champs
 
Posts: 6464
Joined: Sat Apr 03, 2010 3:00 pm
Location: Basel, Switzerland
Has thanked: 813 times
Been thanked: 1042 times

Das Routing

Postby beffl » Sun Nov 18, 2012 9:51 am

Super Sammlung!
Hier noch ein Thread über Softturns:

viewtopic.php?t=25489

LG, Stefan


Sent from my iPhone using Tapatalk
Cheers,
Beffl - CM AT + DE
Image
Wiki Portal Österreich: Image | Waze Austria auf: Image Image Image
Wie Waze Routen kalkuliert | KISS | Der richtige Start beim Editieren
Waze iOS 3.7 | iPhone4s | iPad4
beffl
Waze Global Champs
Waze Global Champs
 
Posts: 2457
Joined: Tue Jun 19, 2012 3:00 pm
Location: Perchtoldsdorf (bei Wien), Austria
Has thanked: 342 times
Been thanked: 576 times

Re: Das Routing

Postby Mesonus » Fri Nov 08, 2013 3:11 pm

Ich sag's mal vorsichtig so, die oben aufgeführten Informationen sind inzwischen ein Jahr alt - was nicht heißt, dass sie nun grundsätzlich falsch sind - aber in dem Jahr hat sich viel getan. Dazu kommt, dass sich Waze beim Routing-Algorithmus noch nie wirklich in die Karten schauen ließ. Von daher habe ich inzwischen aufgegeben, darüber zu theoretisieren.
Wenn es eine konkrete Frage oder ein Routing-Problem gibt, kann man sich die vorhandenen Daten anschauen und analysieren, theoretisch bringt das meistens nix ;)

Gruß Jan
ImageImage Image Image Image
AM zwischen Hannover und Hameln ~ Country Manager
Mesonus
Country Manager
Country Manager
 
Posts: 1414
Joined: Wed Jan 30, 2013 5:41 pm
Location: Hannover
Has thanked: 266 times
Been thanked: 412 times

Re: Das Routing

Postby zottel » Fri Nov 08, 2013 2:54 pm

Auf der verlinkten Wiki-Seite sind Kilometerangaben, ab wann Waze welche Straßen nicht mehr beim Routing berücksichtigt.

Beziehen sich die auf den bei der Routensuche "zurückgelegten" Weg oder auf den Luftlinienabstand? Wie hängt das zusammen mit dem Fernstreckennetz?

Beispiel: Mein Arbeitsweg ist, je nach Route, zwischen 28 km und 35 km lang. Luftlinie werden es wohl ca. 20 km sein, vielleicht etwas mehr.

Was passiert jetzt beim Routen? Am Anfang und am Ende muss Waze ja Streets mit einbeziehen, sonst würde es ja gar nicht funktionieren.

Die Gesamtentfernung ist ja über 15 km, Luftlinie wahrscheinlich auch. Die meisten Routen sind auch über 30 km lang, gehen wir also von so einer aus - das hieße keine Primary Streets mehr. Routet Waze dann von Start und Ziel jeweils bis zum nächsten Minor Highway, und von dort aus dann nur noch Minor Highways und größer?

Tut es der Erfahrung nach nicht, aber was genau kommt dabei dann eigentlich zur Anwendung?
zottel
 
Posts: 109
Joined: Wed May 26, 2010 11:38 am
Has thanked: 1 time
Been thanked: 2 times


Return to Navigation und Routing

Who is online

Users browsing this forum: No registered users

cron