OpenStreetMap
Im Folgenden beschreibe ich wie wir Alternativrouten in den Multi-Level Dijkstra Algorithmus der Open Source Routing Machine implementiert haben.
Endprodukt: effiziente und plausible Alternativrouten
Unser Fokus beim Designen und Implementieren von Alternativerouten lag dabei auf:
- hoch-qualitative Alternativerouten zu generieren: fuer den Endanwender und fuer Anwendungsfaelle die von vielen Alternativerouten profitieren koennen (z.B. eine Jogging-App bei der Start und Ziel ueber die Woche hinweg gleich bleiben aber die Route sich aendern soll), und
- gleichzeitig fuer schnelle Antworten der Routingengine garantieren zu koennen, die im Bereich von 10-100 ms liegen und damit in das Konzept der Open Source Routing Machine passen wobei pre-processing benoetigt wird aber dafuer extrem effizient und schnelle exakte Routen berechnet werden koennen.
Hier sind die Kriterien nach denen wir die Qualitaet der Alternativerouten beurteilen:
- die Alternativroute soll nicht laenger als
x%verglichen zur schnellsten Route sein; das haengt natuerlich auch von der Laenge der Route ab (z.b. ist eine Alternativroute von 13 Minuten okay wenn die schnellste Route 10 Minuten betraegt; 13 Stunden Alternativerouten bei 10 Stunden schnellste Route ist nicht mehr okay fuer den Nutzer) - die Alternativeroute soll sich um mindestens
x%verglichen zur schnellsten Route unterscheiden - die Alternativeroute soll “lokal optimal” sein:
x%der Alternativerouten-Umweg ist wiederum eine schnellste Route
Wir koennen an diesen Parametern nun so drehen dass wir entweder Alternativerouten hoeherer Qualitaet bekomme oder generell mehr Alternativerouten potentiell schlechterer Qualitaet.
Was wir fuer diese Implementierung nicht betrachten:
- wir geben dem Nutzer keine explizite Mischung an Alternativerouten bestehend z.b. aus “Nutze Autobahn” und “Vermeide Autobahn”. Dafuer gibt es ein unabhaengiges Feature in der Routing engine.
- wir geben dem Nutzer keine multi-metric Alternativerouten, also keine Alternativerouten basierend z.b. auf Zeit, Distance, und Aehnlichem. Die Alternativerouten basieren auf einer einzigen Metric die von den Profilen und Traffic Daten bestimmt wird.
Hier ist der grobe Ablauf beschrieben wir wir Alternativerouten mitterls der so genannten “Via-Methode” berechnen:
- starte die bi-direktionale Dijktra Vorwaertssuche von
s; speichere alle besuchten Knoten - starte die bi-direktionale Dijktra Rueckwartssuche von
t; speichere alle besuchten Knoten - wenn sich beide Suchraeume treffen (und die Suche normal abgebrochen werden kann, da eine schnellste Route gefunden wurde), lasse beide Suchen “ein bisschen” weiterlaufen
- schneide die zwei Mengen an Knoten: das sind die Knoten fuer die beide Suchraeume sich ueberlappen.
- fuer alle dieser Knoten
ckann eine (potentiell schlechte) Alternativeroute erstellt werden ueber die Route(s, c, t) - evaluiere und filtere diese Alternativerouten Kandidaten basierend auf den oben genannten Kriterien
Im Folgenden schoen zu sehen wie diese Alternativerouten Kandidaten aussehen:
Das Hauptproblem ist nun dass es etliche Alternativerouten Kandidaten gibt die gefiltert werden muessen.
Das Filtern muss also extrem effizient und schnell sein. Aus diesem Grund filtern wir schrittweise, von inexakten groben Filtern am Anfang die z.b. nicht die genaue Geometrie entpacken muessen, zu hoch-qualitativen Filtern die wegen Laufzeitbeschraenkungen auf nur noch wenigen Alternativerouten Kandidaten laufen koennen.
Die initialen Via-Knoten bekommen wir mittels Intertial Flow Graph-Partitioniers (osrm-partition).
Der Graph-Partitioniere schneided den Graph rekursiv (und komplett parallelisiert) mittels Dinic’s Min-Cut Algorithmus in zwei Stuecke.
Hier ist der Suchraum fuer eine Route Muenchen – Berlin aus dem wir die Via-Knoten fuer die Alternativerouten Kandidaten entnehmen. Dank des Graph-Partitioniers wissen wir dass alle Routen durch diese Via-Knoten gehen muessen.
Wir koennen dann die untersten Level der Partition verwenden um Alternativerouten Kandidaten zu filtern die “zu aehnlich” sind, ohne dass wir die Geometrien der Routen entpacken muessen (was extrem teuer waere).
Ein weiteres Kriterium fuer die Qualitaet der Alternativerouten ist die so genannte Lokale Optimalitaet. Das Problem das Lokale Optimalitaet versucht zu loesen sind Alternativerouten die kurzfristig einen unzumutbaren Umweg nehmen. Das koennte beispielsweise so aussehen, dass die Alternativeroute von der Autobahn kurz ab geht, nur um dann kurz danach wieder auf die Autobahn zu gehen.
Um fuer Lokale Optimalitaet zu garantieren schauen wir uns die Routen um die Via-Knoten an und nutzen die Heaps der Forwaerts- und Rueckwartssuche um zu testen ob diese Routen selbst schnellste Routen sind.
Die lokale Route ist selbst optimal:
Erst jetzt entpacken wir die Geometrien der Alternativerouten-Kandidaten und ueberpruefen unsere Kriterien auf den detaillierten Routen.
Und zuletzt muessen wir diese Kriterien nicht nur zwischen der schnellsten Route und den Alternativerouten-Kandidaten ueberprufen, sondern sobald wir mehrere Alternativerouten gefunden haben gegen alle paarweise Alternativrouten selbst.
Probier’s aus mit der Open Source Routing Machine - wir sind offen fuer Feedback!
Ein besondere Dank geht an Moritz Kobitzsch der eine grosse Hilfe war und mit seinem Doktor in Alternativrouten mit seinem Wissen extrem helfen konnte!
Mehr Details:
Discussion