Simulationsbasierte Ansätze zur Routenumlegung

Im Rahmen des FVU hatte unsere Arbeitsgruppe die Aufgabe, den Verkehr in großen Straßennetzen, wie etwa dem der Stadt Wuppertal mit knapp 17000 einzelnen Straßenabschnitten, zu simulieren. Die oben beschriebenen mikroskopischen Verkehrsflußmodelle benötigen zur Simulation eines realen Straßennetzes detaillierte Eingangsdaten zur Verkehrsnachfrage, nämlich eine Liste aller Fahrten mit Startzeit und Route. Dagegen standen als Ausgangsdaten nur zeitlich und räumlich aggregierte Verkehrsnachfragedaten in Form einer sogenannten Start-Ziel-Matrix ohne Spezifikation der Routen zur Verfügung. Es mußte daher ein Verfahren entwickelt werden, das aus einer aggregierten Start-Ziel-Matrix individuelle Routen für die einzelnen Fahrzeuge berechnet.

Die grundlegende Idee hinter allen Routenwahlmodellen ist sehr einfach und wurde schon 1952 von Wardrop formuliert: Alle benutzten Routen zu einem gegebenen Paar von Start- und Zielknoten haben die gleichen Kosten, und die Kosten aller unbenutzten Routen sind mindestens genauso groß. Jeder Fahrer versucht also, seine Reisezeit individuell zu optimieren. Einen Zustand, in dem dies für jeden Verkehrsteilnehmer erfüllt ist, nennt man Benutzergleichgewicht. Die zeitunabhängige Version dieses Problems, statische Routenumlegung genannt, ist mathematisch und algorithmisch gut verstanden. Für streng konvexe Kostenfunktionen kann die Existenz und Eindeutigkeit einer Lösung gezeigt werden, und algorithmisch kann das Problem etwa mit dem Frank-Wolfe-Algorithmus gelöst werden. Diese klassischen Ansätze der Verkehrsplanung wurden im Rahmen einer Diplomarbeit in unserer Arbeitsgruppe implementiert und an Beispielnetzen erprobt. Auf Grund ihres hohen Rechenaufwandes sind sie jedoch nur für kleine Instanzen geeignet, und ihre Übertragung auf dynamische Fragestellungen scheitert selbst in diesen Fällen, da sich hierbei ein Aufwand proportional zum Produkt aus Netzgröße und der Anzahl der zu simulierenden Zeitschritte ergibt. Legt man die Anforderungen der anderen am FVU beteiligten Gruppen an die Zeitauflösung unserer Simulationen zugrunde, so ergäbe sich im dynamischen Fall für eine einzige Iteration des Frank-Wolfe-Algorithmus für die FVU-Modellstadt Wuppertal eine Laufzeit von ca. 2048 Tagen, die selbst in einer parallelisierten Version für eine praktische Anwendung nicht vertretbar ist.

Im Rahmen einer Dissertation wurde daher eine Methode entwickelt, das Benutzergleichgewicht für eine dynamische Start-Ziel-Matrix direkt im Simulationsmodell zu bestimmen, d.h. für eine gegebene Menge von Fahrern mit festem Startzeitpunkt Routen zu bestimmen, die das Wardropsche Kriterium erfüllen.

Die einfachste Idee wäre, jedem Fahrer zunächst den geometrisch kürzesten Weg zuzuweisen, mit Hilfe dieser Routen einen Simulationslauf durchzuführen, anschließend aufgrund der in der Simulation bestimmten Reisezeiten für einen gewissen Teil der Fahrer neue Routen zu bestimmen und diesen Prozeß zu iterieren, bis die Reisezeiten konvergieren und kein Fahrer seine Reisezeit durch Wahl einer anderen Route verbessern kann. Allerdings kann man sehr leicht Beispiele konstruieren, in denen dieser Prozeß nicht konvergiert und das Gleichgewicht instabil ist.

Unser Ansatz beruht darauf, daß ein Fahrer mehr als eine Route kennen kann. Ein Fahrer d wird in diesem Modell durch folgende Größen beschrieben:

- Startknoten O_d und Zielknoten D_d,
- Startzeit t_d,
- Menge $\mathcal{P}_d$ von Routen von O_d nach D_d,
- Wahrscheinlichkeitsverteilung für die Routenwahl

$$p_d: \mathcal{P}_d \rightarrow \mathbb{R} _+\mbox{ mit }\sum\limits_{r\in \mathcal{P}_d} p_d(r) = 1,$$

- ,,gelernte`` Reisezeiten $\tau_d: \mathcal{P}_d \rightarrow \mathbb{R} _+$.

In jeder Simulation wählt der Fahrer gemäß p_d zufällig eine Route aus $\mathcal{P}_d$ aus. Nach der Simulation werden die Reisezeiten $\tau_d$ geändert, und die Wahrscheinlichkeitsverteilung p_d wird so verschoben, daß günstigere Routen häufiger gewählt werden. Der Vorteil dieses Ansatzes ist, daß zumindest in einfachen Fällen und für das unten beschriebene Warteschlangenmodell die Stabilität des Verfahrens gezeigt werden kann.

Problematisch bei solch einem Iterationsprozeß ist die Rechenzeit des Simulationsmodells. Selbst die am ZPR/ZAIK entwickelten, sehr leistungsfähigen Fahrzeugfolgemodelle sind nicht so schnell, daß eine solche Iteration mit ihnen in angemessener Zeit durchgeführt werden könnte.

  

Abbildung 4.6: Kalibrierung der Reisezeiten des Warteschlangenansatzes am CA-Modell in einer Bottleneck-Situation

Daher wurde für diese Aufgabe ein spezielles Warteschlangenmodell entwickelt, das die Fahrzeugfolgedynamik auf einem Straßenabschnitt vernachlässigt; statt dessen wird jeder Straßenabschnitt als Warteschlange mit vorgegebener Länge, Kapazität und vorgegebenem Fassungsvermögen beschrieben. Obwohl dieses Modell den Verkehrsfluß sehr stark vereinfacht, werden die Reisezeiten, die in den am ZPR/ZAIK verwendeten Fahrzeugfolgemodellen gemessen wurden, sehr gut reproduziert. Mit Hilfe dieses Modells läßt sich der zeitliche Aufwand zur Berechnung des Benutzergleichgewichts (je nach Netztopologie) um den Faktor 10-100 beschleunigen.