Heuristische Verfahren zur Bestimmung von kürzesten Wegen in großen Straßengraphen

Das Problem, einen kürzesten Weg zwischen zwei Knoten in einem gewichteten Graphen zu finden, ist eines der klassischen Probleme in der Netzwerkoptimierung, das seit über vierzig Jahren Gegenstand ausgiebiger Forschungstätigkeit ist. In vielen praktischen Anwendungen taucht die Bestimmung von kürzesten Wegen auf, entweder als eigenständige Fragestellung (z.B. bei Transportproblemen, Projektmanagement und DNA-Sequenzierung) oder als Teilproblem eines komplexeren Problemzusammenhangs (z.B. bei der Approximation von Funktionen und dem Knapsack-Problem).

**Abbildung 3.1:** Bestimmung des kürzesten Weges zwischen den Knoten S und T. Es wird ein Rückwärtsdijkstra vom Zielknoten T aus auf dem Suchgraphen der Partitionsklasse, in der S liegt, durchgeführt. Im Gesamtgraphen sind alle Knoten schwarz eingefärbt, die während der Suche vom Algorithmus ,,besucht`` werden.
$\begin{figure}\noindent \epsfig{file=verkehr/figures/diwi_hier.eps,width=\linewidth} \end{figure}$

Im Rahmen einer Dissertation wurden verschiedene algorithmische Verfahren zur Bestimmung kürzester Wege in sehr großen Straßengraphen untersucht. Die Beschäftigung mit diesen Fragestellungen wurde angeregt durch die zunehmende praktische Bedeutung der Generierung von geeigneten Routenempfehlungen für eine Vielzahl von Fahrern in Straßennetzen.

Ausgelöst wurde diese Entwicklung durch die Notwendigkeit einer effektiveren Verkehrslenkung aufgrund des immer weiter steigenden Verkehrsaufkommens und durch den Einsatz neuer Technologien im Bereich der Fahrzeugelektronik in den letzten Jahren. Hier sind insbesondere die zunehmende Verbreitung von individuellen Navigationssystemen und das damit verbundene Gebiet der Telematik zu nennen. Seit der Markteinführung solcher Navigationssysteme vor einigen Jahren verzeichnen die Hersteller jährlich sich verdoppelnde Umsatzzahlen mit einem erwarteten Absatz von über 600.000 Geräten in Deutschland für das Jahr 2000. Dabei tendiert die Entwicklung zu einer Routenführung hin, bei der zunehmend dynamische Verkehrsdaten berücksichtigt werden.

Auch bei einer effizienteren Planung und Steuerung von Verkehr mittels der am Institut entwickelten einzelfahrzeugbasierten Mikrosimulation müssen bei der iterativen Bestimmung des dabei angestrebten Verkehrsgleichgewichts idealerweise in jedem Iterationsschritt die Routen aller Fahrer neu berechnet werden. Bereits für ein relativ kleines Untersuchungsgebiet wie das Straßennetz der Stadt Wuppertal mit ungefähr 17.000 Kanten im Graphen bedeutet dies die Berechnung von 500.000 Routen pro Iterationsschritt, was selbst auf Computerworkstations der aktuellen Technik mehrere Stunden in Anspruch nimmt.

Den beschriebenen Anwendungen ist gemeinsam, dass eine benötigte Route nicht unbedingt der tatsächlich kürzeste Weg zwischen den beiden Endpunkten sein muss. Es reicht, wenn die Fahrtzeit einer vorgeschlagenen Routenempfehlung hinreichend nahe an derjenigen des optimalen Weges ist. Für die Zufriedenheit des Benutzers eines individuellen Navigationssystems ist es dabei insbesonders wichtig, dass seine persönlichen Erwartungen erfüllt werden. Dagegen steht im Rahmen einer Verkehrssimulation eine ausreichende Beschreibung des realen Verkehrszustandes im Vordergrund. Dieser ist gegenüber vereinzelten nicht zu großen Abweichungen der Routen von optimalen Wegen relativ unempfindlich.

Für das darunter liegende Problem der Bestimmung von kürzesten Wegen in Graphen mit nicht-negativer Kostenfunktion ist der klassische Lösungsalgorithmus das bereits 1959 von Dijkstra vorgeschlagene Verfahren. Die schnellsten Implementierungen von Dijkstras Algorithmus benötigen für die Bestimmung eines kürzesten Weges im Straßengraphen von Nordrhein-Westfalen mit etwas über einer Million Kanten weniger als eine Sekunde auf einer Sun Enterprise E450 mit 4 mit 400 MHz getakteten UltraSPARC-II Prozessoren.

In praktischen Anwendungen kommen häufig heuristische Verfahren zur Routengenerierung in Straßengraphen zum Einsatz. Solche Methoden nutzen meist die spezielle Struktur von Straßengraphen mit gerichteten Kanten, Kantenlängen nah der euklidischen Distanz der beiden Endknoten sowie die Fastplanarität und eine hierarchischen Struktur aufgrund einer Typisierung der Kanten nach Wichtigkeit.

Im Rahmen der Dissertation wurde eine Heuristik entwickelt, die die Ähnlichkeit von kürzesten-Wege-Bäumen in Straßengraphen für nah beeinander liegende Startknoten ausnutzt. Die Heuristik gliedert sich in mehrere Phasen. Zuerst wird der Graph in

Klassen möglichst gleicher Größe partitioniert, und nachdem für jede Partitionsklasse eine Reihe von Basisknoten bestimmt wurde, wird in jeder der Klassen ein Suchgraph auf Basis dieser Knoten erzeugt. Diese Suchgraphen enthalten wesentlich weniger Kanten als der Gesamtgraph, aber alle Knoten des Graphen. Die Kantenmenge eines Suchgraphen besteht aus allen Kanten der Klasse und der Vereinigung aller Kanten von kürzesten-Wege-Bäumen der Basisknoten. Die Suchgraphen sind somit lokal dicht, aber global dünn besetzt. Die Anwendung eines Rückwärtsdijkstra bei der eigentlichen Routensuche führt schließlich zu einem sehr schnellen Algorithmus, s.a. Abbildung 3.1.

Auf den größten betrachteten Netzen ist die Baumheuristik um einen Faktor drei bis acht schneller als Dijkstras Algorithmus. In Bezug auf die Anzahl permanent markierter Knoten erzielt die Heuristik einen Gewinn um den Faktor 7 bis 20. Dabei werden Pfade gefunden, die im Mittel um weniger als 1% vom optimalen Weg abweichen, sofern die beiden Endknoten nicht zu nahe beeinander liegen. Es ist zu erwarten, dass über 90% der exakten kürzesten Wege von der Heuristik gefunden werden.

Darüber hinaus wurden etablierte Heuristiken untersucht und für das spezielle Problem auf Straßengraphen angepasst. Der Vergleich der Baumheuristik mit diesen Ansätzen zeigt, dass die neu entwickelte Heuristik aufgrund der gleichzeitigen Ausnutzung von geometrischen und hierarchischen Strukturen der Straßennetze und der Möglichkeit der dynamischen Anpassung der Suchgraphen zu sehr guten Ergebnissen führt.