Tolls in Transportation Networks

Inhaltsverzeichnis

1 Introduction

1.1 Related Work

1.2 Outline of the Thesis

2 Preliminaries

2.1 Graphs and Flows

2.2 Wardrop Transportation Model

2.3 The Price of Anarchy

3 Taxes on Subnetworks

3.1 Preliminaries

3.2 NP-Hardness of Computing Optimal Taxes on Subnetworks

4 Toll Computation Algorithms for General Networks

4.1 The Algorithms

4.2 Flow Computation with CMCF

4.3 Data sets

4.4 The Choice of the Set of Taxable Edges

4.5 Computational Results

4.6 Convergence Time

5 The Cardinality Constrained Toll Problem

5.1 NP-Hardness

5.2 Computational Study

6 Integration into a Multi-Agent Transport Simulator

6.1 Tolls in MATSim

6.2 Computational study

7 Conclusion

Zielsetzung und Themen

Die vorliegende Arbeit untersucht das mathematische Optimierungsproblem der Berechnung von Mautgebühren für eine vordefinierte Teilmenge von Straßen in einem Verkehrsnetz, mit dem Ziel, die Gesamtfahrzeit aller Verkehrsteilnehmer zu reduzieren. Dabei wird insbesondere das Problem der Mautberechnung unter einer Kardinalitätsbeschränkung für die Anzahl der bemautbaren Straßenabschnitte analysiert und die Wirksamkeit der entwickelten Ansätze durch Integration in einen agentenbasierten Verkehrssimulator evaluiert.

• Mathematische Modellierung des "Wardrop-Gleichgewichts" in Verkehrsnetzen.
• Entwicklung und Evaluation von Algorithmen zur effizienten Mautberechnung.
• Analyse der NP-Härte bei der Auswahl optimaler Maut-Teilmengen.
• Integration der Ergebnisse in den agentenbasierten Simulator MATSim.
• Systematische Untersuchung anhand realer Verkehrsdaten (u.a. Berlin, Schweiz).

Auszug aus dem Buch

Zusammenfassung der Kapitel

1 Introduction: Einführung in die Problematik steigender Verkehrsaufkommen und das Modell des egoistischen Nutzerverhaltens (Wardrop-Gleichgewicht).

2 Preliminaries: Definition der grundlegenden graphentheoretischen Begriffe, des Wardrop-Modells und der "Price of Anarchy" zur Quantifizierung von Effizienzverlusten.

3 Taxes on Subnetworks: Theoretische Untersuchung der Mauterhebung auf Teilnetzen und Beweis der NP-Härte für die Berechnung optimaler Mautgebühren auf einer vordefinierten Teilmenge von Kanten.

4 Toll Computation Algorithms for General Networks: Vorstellung vier verschiedener Algorithmen zur iterativen Mautanpassung in allgemeinen Netzen und Diskussion der Ergebnisse auf Basis realer Instanzen.

5 The Cardinality Constrained Toll Problem: Analyse des Problems, wenn zusätzlich zur Mauthöhe auch die Anzahl der bemautbaren Straßen eingeschränkt ist, inklusive NP-Härte-Beweis und heuristischer Lösungsansätze.

6 Integration into a Multi-Agent Transport Simulator: Übertragung der statischen Ergebnisse in den dynamischen, agentenbasierten Verkehrssimulator MATSim und Evaluierung der verbesserten Netzwerkauslastung.

7 Conclusion: Zusammenfassende Betrachtung der erzielten Resultate und Ausblick auf zukünftige Forschungsmöglichkeiten im Bereich dynamischer Mautanpassungen.

Schlüsselwörter

Verkehrsplanung, Wardrop-Gleichgewicht, Mautgebühren, Congestion Pricing, Netzwerkoptimierung, NP-Härte, MATSim, Verkehrssimulation, Price of Anarchy, Marginal Cost Pricing, Verkehrsnetz, Algorithmen, Straßenauslastung, Verkehrsfluss, Reisezeitreduktion.

Häufig gestellte Fragen

Worum geht es in dieser Arbeit grundsätzlich?

Die Arbeit untersucht, wie durch die Erhebung von Mautgebühren auf einer begrenzten Auswahl von Straßen der Gesamtverkehrsfluss in einem Netzwerk optimiert werden kann, um Reisezeiten zu minimieren.

Was sind die zentralen Themenfelder?

Die Arbeit fokussiert sich auf die Schnittstelle von Verkehrsplanung, Graphentheorie und mathematischer Optimierung sowie deren praktische Anwendung in Verkehrssimulationen.

Was ist das primäre Ziel oder die Forschungsfrage?

Das Ziel ist die Reduktion der Gesamtfahrzeit in Verkehrsnetzen durch die Berechnung optimaler Maut-Strategien, unter der praktischen Einschränkung, dass nicht alle Straßen gleichzeitig bemautet werden können.

Welche wissenschaftliche Methode wird verwendet?

Es werden mathematische Optimierungsverfahren, insbesondere Gradientenabstiegs-basierte Algorithmen, sowie Reduktionsbeweise zur Komplexitätsanalyse (NP-Härte) eingesetzt und durch computergestützte Simulationen validiert.

Was wird im Hauptteil behandelt?

Der Hauptteil umfasst die algorithmische Entwicklung zur Mautberechnung, die Untersuchung von Einschränkungen bei der Mautauswahl (Kardinalitätsconstraint) und die Implementierung der Ergebnisse in einen dynamischen Verkehrssimulator.

Welche Schlüsselwörter charakterisieren die Arbeit?

Zu den wichtigsten Begriffen zählen Wardrop-Gleichgewicht, Congestion Pricing, NP-Härte, Netzwerkoptimierung und agentenbasierte Verkehrssimulation.

Welche Rolle spielt die "Price of Anarchy" in diesem Dokument?

Sie dient als Metrik, um den Effizienzverlust durch das egoistische Verhalten von Verkehrsteilnehmern im Vergleich zum systemoptimalen Zustand messbar zu machen.

Warum ist die Integration in MATSim relevant?

Da statische Modelle die Dynamik von Aktivitätenplänen und zeitabhängigem Stauverhalten nur begrenzt abbilden, erlaubt die Integration in MATSim eine realistischere Überprüfung der Wirksamkeit der berechneten Mautlösungen.