Artikel verfasst von Ignacio „Nacho“ Correas, Chief Technology Innovation Officer bei Skymantics -
Es gibt zwei Kompromisse, die sorgfältig abgewogen werden müssen: Genauigkeit und Leistung. Es ist sinnlos, wenn eine Routing-Engine schnell suboptimale Routen generiert, aber es ist ebenso unpraktisch, optimale Routen zu generieren, deren Berechnung viel Zeit in Anspruch nimmt. Der erste kritische Punkt, den man bei der Routing-Engine berücksichtigen muss, ist der Routing-Algorithmus.
Routing-Algorithmen
Skymantics hat mit Kürzeste-Wege-Algorithmen experimentiert, insbesondere mit Dijkstra und A* (A-Star), in drei Modi: unidirektional, bidirektional und mit Optimierung der Kontraktionshierarchien (CH). Die Implementierung einer unidirektionalen Standardversion dieser Algorithmen ist relativ einfach, und im Internet gibt es zahlreiche Tutorials, die dabei helfen, dies zu verstehen. Als Faustregel gilt, dass bidirektionale Algorithmen (mit anderen Worten, der Pfad wird gleichzeitig vom Ursprung und vom Ziel aus berechnet) die optimale Route 5- bis 10-mal schneller liefern als unidirektionale, obwohl die Wahl des optimalen gemeinsamen Knotens (wo der Pfad vom Ursprung auf den Pfad vom Ziel trifft) ihre eigenen Probleme mit sich bringt. Die Wahl zwischen Dijkstra und A* und zwischen bidirektional oder mit CH ist jedoch nicht einfach.
Wann wird A* verwendet?
Theoretisch sollte A* ein effizienterer Algorithmus sein, da er weniger Berechnungen erfordert: Es handelt sich im Grunde um einen gerichteten Dijkstra, der nur die Graphknoten berücksichtigt, die dabei helfen, sich in die Richtung zum Ziel zu bewegen. Dies erfordert jedoch die Berechnung von Richtung und heuristischen Distanzen, was eine rechenintensivere Operation als eine Dikjstra-Iteration ist und kontraproduktiv sein kann. Im Allgemeinen ist A* für sehr dichte Netze von Straßen/Wegen derselben Hierarchie möglicherweise die bessere Wahl. Für alles andere wird Dijkstra wahrscheinlich ausreichen.
Wann wird CH verwendet?
Für lange Überlandrouten benötigen Sie eine Art Optimierung wie beispielsweise Kontraktionshierarchien. Diese Optimierung priorisiert Routen mit höherer Hierarchie und ignoriert Alternativen mit niedrigerer Hierarchie, wodurch die Berechnungen zur Ermittlung der kürzesten Route sehr effizient drastisch reduziert werden. Hier ist ein Beispiel für eine 265 km (165 Meilen) lange Route durch Belgien: Die Berechnung dauert mit dem bidirektionalen Algorithmus von Dijkstra 35 Sekunden, mit der Optimierung der Kontraktionshierarchien jedoch nur 0.1 Sekunden.
Wann wird das bidirektionale Dijkstra-Verfahren verwendet?
Bei kürzeren Stadtstrecken können Kontraktionshierarchien zu einer nicht optimalen Route führen, da der Algorithmus Umwege nehmen kann, wenn er in der Nähe eine Route mit höherer Hierarchie findet. Dieser Effekt lässt sich reduzieren oder sogar ganz beseitigen, indem man die Straßenhierarchien sorgfältig anpasst und dem Algorithmus einige zusätzliche Iterationen zugesteht. Falls die Routing-Anwendung jedoch nur für ein bestimmtes Stadtgebiet bestimmt ist, ist es möglicherweise einfacher, einfach eine bidirektionale Dijkstra zu verwenden. Hier sehen Sie ein Beispiel für eine Route durch die Innenstadt von Providence im Bundesstaat Rhode Island, die eigentlich eine gerade Linie sein sollte, bei der die Kontraktionshierarchien jedoch ausgetrickst werden und einen Umweg über die nahe gelegene Hauptstraße nehmen. Die Rechenzeit für CH beträgt 1 Millisekunde gegenüber 1.5 Millisekunden für die bidirektionale Dijkstra. Dies zeigt, dass Spielraum für zusätzliche Iterationen besteht, um diesen Umwegeffekt zu vermeiden.
Routing-Algorithmen können Genauigkeit garantieren und die Leistung bis zu einem gewissen Grad verbessern. Tatsächlich verlaufen sie durch ein Netz von Straßen, die in einem Kartendatensatz definiert sind, und die Ergebnisse hängen stark von der Genauigkeit dieser Datensätze und der Art und Weise ab, wie sie vorverarbeitet wurden.
Vorverarbeiten von Datensätzen
Datensätze und Vorverarbeitung sind die wichtigste Möglichkeit, die Genauigkeit und Leistung eines Routing-Algorithmus zu verbessern. Es ist schwierig, diesen Punkt genug zu betonen. Ich werde versuchen, die wichtigsten zu berücksichtigenden Aspekte in den folgenden Punkten zusammenzufassen:
- Nicht alle Datensätze weisen die gleiche Genauigkeit auf. OpenStreetMap ist ein großartiges Beispiel; es deckt praktisch die ganze Welt ab und kann kostenlos heruntergeladen und verwendet werden, aber es fehlen einige wichtige Informationen wie viele Geschwindigkeitsbegrenzungen, Höhen-/Gewichtsbeschränkungen oder verbotene Manöver. In einigen Fällen kann es sogar falsche Informationen in Bezug auf Einbahnstraßenrichtungen oder -verbindungen enthalten, um nur einige zu nennen. Andere Karten, wie z. B. HIER KLICKENbieten eine viel höhere Genauigkeit, haben aber ihren Preis. Interessanterweise stimmen die Straßenkoordinaten in verschiedenen Datensätzen nicht zu 100 % überein, und Sie stellen möglicherweise fest, dass dieselben Koordinaten je nach verwendetem Datensatz als Teil verschiedener Straßen betrachtet werden.
- Abhängig von der Anwendung Ihrer Routing-Engine können viele in einem Datensatz enthaltene Straßen- oder Wegabschnitte zu einer einzigen Kante zusammengeführt werden, wodurch die Größe des Diagramms manchmal um bis zu 90 % reduziert wird. Beispielsweise können Abkürzungen erstellt werden, um Kreuzungen niedrigerer Hierarchie zu überspringen und so die Routenberechnung auf langen Distanzen zu beschleunigen.
- Ein kritischer Teil der Vorverarbeitung ist die Entscheidung, wie die Hierarchie der Straßenverbindungen klassifiziert werden soll: Verbinden sie Straßen mit niedrigerer und höherer Hierarchie? Verbinden sie Straßen mit derselben Hierarchie? Dies ist ein besonders wichtiger Aspekt für Autobahnkreuze, da Straßen, die Autobahnen verbinden, die höchste Hierarchie haben müssen (um die Kontraktionshierarchien zu beschleunigen). Wenn jedoch alle Straßenverbindungen von einer Autobahn auf die höchste Hierarchie gesetzt werden, verlangsamt dies die Berechnungen aufgrund zu vieler Kreuzungen.
Routing-Algorithmen, Datensätze und Vorverarbeitung sind die wichtigsten Aspekte, die beim Erstellen eines präzisen und leistungsfähigen Routing-Algorithmus berücksichtigt werden müssen. Aber es gibt noch andere Aspekte, die den Unterschied zwischen einer nützlichen und einer nutzlosen Routing-Engine ausmachen können.
Bewährte Methoden für die Programmierung
Ich gehe davon aus, dass gute Programmierpraktiken vorhanden sind und dass für die Aufgabe eine geeignete Programmiersprache gewählt wird. Bei der Bereitstellung und dem Betrieb einer Routing-Engine sind drei wichtige Punkte zu beachten:
- Für eine optimale Leistung müssen die Grafikdaten im Speicher liegen. Einige Teile können in einer Datenbank vorhanden sein, z. B. geografische Daten, die dabei helfen, die nächstgelegenen Knotenpunkte zu Start- und Zielort zu finden, aber der Routing-Algorithmus muss mit Daten im Speicher arbeiten, sonst besteht die Gefahr, dass er bei Karten, die etwas größer als ein Stadtzentrum sind, nicht die erwartete Leistung erbringt.
- Die Routing-Engine muss alle erforderlichen Daten vorab laden und Threading für sekundäre, zeitaufwändige Aufgaben nutzen, z. B. das Speichern der generierten Route auf der Festplatte. Andernfalls summieren sich diese Zeiten und verringern die Gesamtleistung.
- Dies mag offensichtlich erscheinen, aber wenn die Routing-Engine als Remote-Dienst angeboten werden soll, ist die Verbindungsgeschwindigkeit entscheidend. Es macht keinen Sinn, die Routing-Berechnung zu beschleunigen, wenn der Engpass im Kommunikationskanal liegt. Latenz und Durchsatz sind für einen leistungsfähigen API-Dienst von entscheidender Bedeutung.
Und das ist im Grunde alles. Das Erstellen einer Routing-Engine kann eine spannende Aufgabe sein, voller Herausforderungen und Spaß. Auch wenn es nicht Ihr Ziel ist, eine zu erstellen, Sie aber Routing intensiv nutzen müssen, ist es gut, die wichtigsten Aspekte zu verstehen. Ich hoffe, Sie hatten beim Lesen dieser Artikelserie genauso viel Spaß wie ich beim Schreiben. Prost!
