von Dr. Lukas Graf (Gewinner Dissertationspreis 2024)

Netzwerkflüsse bzw. Flüsse in Graphen sind ein häufig genutztes Modell für den Autoverkehr.  Hierbei wird das Straßennetz als gerichteter Graph und der Verkehr darin als Fluss modelliert. Insbesondere bildet man hierbei also nicht einzelne Autos ab, sondern gibt nur für jede Kante (=Straße) an, welche (beliebig teilbare) Menge an Verkehrsfluss diese benutzt. In Abhängigkeit von dieser Flussmenge hat jede Kante dann gewisse Kosten für ihre Benutzung. Im einfachsten Fall entsprechen diese Kosten dabei den vom Verkehr induzierten Reisezeiten auf den jeweiligen Straßen.

Das Verhalten der Flusspartikel (=Autofahrer) wiederum kann mit Mitteln der Spieltheorie nachgebildet werden. Hierbei startet man mit der Annahme, dass die einzelnen Spieler basierend auf den ihnen zu Verfügung stehenden Informationen Entscheidungen treffen, die ihre individuellen Kosten minimieren. Eine Situation, in welcher sich alle Spieler so verhalten, bezeichnet man dann als Gleichgewicht. Im Fall von statischen Flüssen und vollständiger Information heißen solche Gleichgewichtsflüsse auch „Wardrop-Gleichgewichte“ ( [1]) und sind dadurch charakterisiert, dass nur solche Wege benutzt werden, welche minimale Kosten unter dem jeweiligen Fluss haben.

Eine erste wichtige Beobachtung hierbei ist, dass solche Gleichgewichtsflüsse im Allgemeinen keine optimalen, d.h. die Gesamtkosten minimierenden, Flüsse sind (siehe Abbildung 2 für ein klassisches Beispiel dafür im statischen Fall).

Eine wichtige Erweiterung des bisher beschriebenen (statischen) Flussmodells ist die explizite Berücksichtigung der Zeitkomponente in der Flussdynamik ( [2]): Hierbei beeinflussen die (flussabhängigen) Kantenreisezeiten dann nicht nur die Gesamtkosten des Flusses bzw. eines Weges, sondern auch die Dynamik des Flusses selbst. Ein solcher dynamischer Fluss besteht aus zwei Funktionen pro Kante: Einer Einfluss- und einer Ausflussrate. Diese beschreiben, mit welcher Rate zu jedem Zeitpunkt Flusspartikel die Kante betreten und verlassen, und sind über eine (flussabhängige) Reisezeitfunktion miteinander gekoppelt.

Ein solches viel genutztes dynamisches Flussmodell ist das „Vickrey Queuing Modell“ ( [3]): Hierbei hat jede Kante eine flussunabhängige Mindestreisezeit τ und eine maximale Kapazität ν. Überschreitet die Rate, mit der die Flusspartikel eine Kante betreten wollen, diese Kapazität, so bildet sich eine Warteschlange am Beginn der Kante, was zu einer Erhöhung der Gesamtreisezeit über die Kante führt. In Abbildung 3 sieht man auf der Kante von v nach w ein Beispiel für das Entstehen einer solchen Warteschlange.

Meine Dissertation [4] beschäftigt sich nun innerhalb dieses Flussmodells mit Flüssen, welche aus folgendem Verhalten resultieren: Jedes Flusspartikel hat einen festen Startort und -zeitpunkt sowie einen gewünschten Zielort. Wann immer ein Partikel an einem Knoten ankommt, erhält es die Information über die aktuellen Reisezeiten im gesamten Netzwerk, berechnet basierend darauf einen kürzesten Weg von der aktuellen Position zu seinem Ziel und betritt die erste Kante auf einem solchen Weg. Der resultierende Fluss ist dann ein Modell für einen Verkehrsfluss, in dem jeder Autofahrer ein eigenes Navigationsgerät benutzt, welches kontinuierlich Informationen über die aktuelle Verkehrslage erhält und, darauf basierend, die vorgeschlagene Route anpasst.

Einen dynamischen Fluss, in welchem alle Partikel dieses Verhalten zeigen (also immer nur Kanten auf aktuell kürzesten Wegen betreten), bezeichnet man dann als „Instantaneous Dynamic Equilibrium (IDE)“. Abbildung 3 stellt beispielhaft einen Teil eines solchen Gleichgewichtsfluss dar. Der zentrale Teil meiner Dissertation beschäftigt sich mit der Beantwortung der folgenden drei fundamentale Fragen zu IDEs:

• Wann existiert ein solches Gleichgewicht?
• Wie können wir einen Gleichgewichtsfluss berechnen?
• Wie gut (oder schlecht) sind die Reisezeiten eines IDEs?

Existenz

Aufgrund der nicht-trivialen Abhängigkeiten innerhalb der Definition eines IDEs (welche Kanten benutzt werden dürfen, hängt von den aktuellen Reisezeiten ab – diese wiederum hängen davon ab welche Kanten in welchem Ausmaß genutzt werden), ist es zunächst einmal gar nicht klar, dass derartige Gleichgewichtsflüsse überhaupt existieren. Um dies zu zeigen, betrachten wir partielle Gleichgewichtsflüsse, d.h. Flüsse, die nur bis zu einem gewissen (endlichen) Zeitpunkt definiert sind. Wenn man nun zeigen kann, dass jedes solche partielle IDE für ein kleines zusätzliches Zeitintervall erweitert werden kann, garantiert Zorn’s Lemma die Existenz eines IDE für alle Zeit. Für die Existenz solcher Erweiterungen beschreiben wir drei Beweise unter verschiedenen Zusatzannahmen an das gegebene Netzwerk: Für stückweise-konstante Flüsse mit einem gemeinsamen Ziel für alle Partikel kann die Existenz einer Erweiterung auf die eines (statischen) Wardrop-Gleichgewichts in einem geeigneten Hilfsnetzwerk reduziert werden. Für stückweise-konstante Flüsse mit mehreren Zielen kann die Existenz aus Kakutanis Fixpunktsatz gefolgert werden und für den allgemeinst möglichen Fall folgt sie aus einer Version dieses Fixpunktsatzes für unendlich-dimensionale Räume.

Berechenbarkeit

Die grundlegende Struktur des Existenzbeweises legt bereits nahe, dass IDEs durch iteratives Erweitern berechnet werden können. Um daraus einen tatsächlichen Algorithmus zur Berechnung von IDEs zu erhalten, müssen zwei Dinge gezeigt werden: Wie man eine einzelne Erweiterung bestimmen kann und dass endlich viele solcher Erweiterungen ausreichen. Ersteres ist – unter geeigneten Annahmen – vergleichsweise leicht zu zeigen, da es sich bei dem dazu äquivalenten Wardrop Gleichgewichtsproblem um ein konvexes Optimierungsproblem handelt, welches mit einem einfachen Waterfilling-Algorithmus gelöst werden kann. Zweiteres hingegen ist deutlich komplexer zu beweisen, da das Existenzresultat keine untere Schranke an die Länge der Erweiterungsintervalle liefert. Stattdessen nutzen wir daher in unserem Beweis die Tatsache, dass es (in ausreichend kurzen Zeitintervallen) nur endliche viele Arten von Erweiterungen geben kann und jede davon wiederum nur endlich oft auftreten kann.

Güte

Im Vergleich zu einem optimalen Fluss gibt es in einem IDE gleich zwei Faktoren, welche zu höheren Kosten führen können: Zum einen  der Umstand, dass die einzelnen Flusspartikel eigennützige Entscheidungen treffen um ihre jeweils eigene Reisezeit zu minimieren, und zum anderen die Beschränktheit der Informationen aufgrund derer diese Entscheidungen getroffen werden: Partikel kennen immer nur die aktuellen Reisezeiten auf den betrachteten Routen, nicht aber die zukünftigen Reisezeiten, welche – gerade bei weiter entfernten Kanten – die tatsächliche Reisezeit bestimmen werden. Das daraus resultierende ständige Anpassen der Route kann im schlimmsten Fall sogar dazu führen, dass sich einzelne Flusspartikel entlang eines Kreises bewegen. Grundsätzlich ist daher nicht einmal klar, ob alle Partikel in endlicher Zeit ihr Ziel erreichen.Im Falle eines gemeinsamen Ziels aller Flusspartikel können wir die Terminierung von IDEs dennoch zeigen. Eine genaue Analyse der in diesem Beweis verwendeten Abschätzungen erlaubt zudem auch die Angabe expliziter oberer Schranken an die Gesamtreisezeit in einem IDE. Umgekehrt konstruieren wir eine Familie von Netzwerken, in welchen IDEs eine besonders hohe Reisezeit aufweisen und erhalten so untere Schranken. Schließlich zeigen wir, dass es im Falle von Partikeln mit verschiedenen Zielen passieren kann, dass Flusspartikel in einem IDE für immer in einem Kreis gefangen sind und daher nie ihr Ziel erreichen.

Literaturverzeichnis

1. J. R. Correa und N. E. Stier-Moses, „Wardrop Equilibria,“ in Wiley Encyclopedia of Operations Research and Management Science, John Wiley & Sons, Ltd, 2011.
2. M. Skutella, „An Introduction to Network Flows over Time,“ in Research Trends in Combinatorial Optimization, Heidelberg, Springer, 2009, pp. 451-482.
3. W. S. Vickrey, „Congestion Theory and Transport Investment,“ The American Economic Review, pp. 251-260, 1969.
4. L. Graf, Dynamic Network Flows with Adaptive Route Choice based on Current Information, Wiesbaden: Springer Spektrum, 2024.