Competitive variants of discrete and continuous flows over time

Vargas Koch, Laura; Peis, Britta (Thesis advisor); Skutella, Martin (Thesis advisor); Triesch, Eberhard (Thesis advisor)

Aachen (2020, 2021)
Doktorarbeit

Dissertation, RWTH Aachen University, 2020

Kurzfassung

Diese Arbeit beschäftigt sich mit diskreten und kontinuierlichen kompetitiven Flussmodellen. In solchen Modellen reisen egoistisch handelnde Akteure durch ein Netzwerk, in dem Kanten Reisezeiten und Kapazitäten haben. Dabei beeinflussen sie gegenseitig ihre Ankunftszeiten, da es auf Grund der beschränkten Kapazitäten der Kanten zu Überlastung kommen kann. Dies beschreibt eine Situation, wie sie auch im Straßenverkehr auftritt. Während es Simulationsprogramme gibt, die sehr detailreiche Verkehrsmodelle verwenden, dafür aber mathematisch kaum analysierbar sind, vereinfachen mathematische Modelle die Realität stark um analysierbar zu bleiben. Ziel der Arbeit ist es zur Entwicklung guter mathematischer kompetitiver Flussmodelle beizutragen. Dabei ist die große Herausforderung detailreiche und realistische analysierbare Modelle zu entwickeln und zu verstehen. Der erste Teil der Arbeit widmet sich der Entwicklung und Analyse eines diskreten kompetitiven Flussmodels, das sich kompetitives Paketrouting nennt. Die Grundlage dieses Models bildet ein Netzwerk, in dem jede Kante eine Reisezeit und eine Kapazität besitzt. Spieler betreten das Netzwerk an einem Startknoten und wählen einen Weg, auf dem sie so schnell wie möglich zu ihrem Zielknoten gelangen, wenn sie die Strategien der übrigen Spieler antizipieren. Es werden drei verschiedene Varianten untersucht, wie in diesem Modell Konflikte, die zwischen Spielern auftreten, gelöst werden können: durch spielerabhängige Regeln, durch kantenabhängige Regeln und durch randomisierte Regeln. Außerdem wird bei der Analyse zwischen symmetrischen Spielen, bei denen alle Spieler einen gemeinsamen Start- und Endknoten teilen und zwischen multi-commodity Spielen, bei welchen das nicht der Fall ist, unterschieden. In den verschiedenen Varianten des Spiels wird die Existenz und Berechenbarkeit von Gleichgewichtszuständen und deren Güte untersucht. Darüber hinaus beschäftigen wir uns mit der Berechnung möglichst guter Prioritätslisten. Im zweiten Teil dieser Arbeit werden zeitabhängige Nash-Flüsse analysiert, wie die Gleichgewichtszustände in dem kontinuierlichen kompetitiven Modell, welches hier präsentieret wird, genannt werden. Die Grundform des Models wurde von Koch und Skutella eingeführt. Auch hier bildet ein Netzwerk, in dem jede Kante eine Reisezeit und eine Kapazität hat, die Grundlage des Models. Der große Unterschied ist, dass unendlich kleine Partikel das Netzwerk an der Quelle mit einer bestimmten Rate betreten und dann jedes einzelne Partikel einen optimalen Weg zur gleichen Senke wählt. Wir erweitern dieses Modell durch die Einführung einer Einflusskapazität und durch die Beschränkung des Gesamtflusses einer Kante hin zum Spillback-Modell. So wird es ermöglicht Rückstau abzubilden. In einem nächsten Schritt fügen wir zudem eine Rückwärtsreisezeit zu den Eigenschaften der Kante hinzu. Damit können die Reaktionszeiten der Verkehrsteilnehmer berücksichtigt werden und der Verkehr verhält sich im Modell wellenähnlich, wie es auch im verstopften Stadtverkehr zu beobachten ist. Da sowohl der Rückstau als auch die wellenartige Bewegung des Verkehrs zu den Details gehören, die Verkehrssimulationsprogramme implementieren, ist diese Erweiterung relevant. Die bekannten Ergebnisse über die Existenz von Gleichgewichten werden auf die neuen Modelle übertragen und darüber hinaus werden die Eigenschaften der Gleichgewichte in den präsentierten Modellen analysiert. Abschließend wird der Zusammenhang zwischen einem diskreten und dem kontinuierlichen Flussmodell untersucht.

Einrichtungen

• Graduiertenkolleg UnRAVeL [080060]
• Fachgruppe Mathematik [110000]
• Lehrstuhl II für Mathematik (für Ingenieure) [113210]
• Lehrstuhl für Management Science [815110]