The world-wide road traffic volume increases continuously while street capacities cannot be expanded accordingly. Coping with traffic congestion to reduce the overall travel time requires sophisticated traffic planning methods. Charge fees for the usage of network capacities is of special interest in scientific literature and, recently, has been implemented in practise. However, for technical, economical or political reasons, it is still not practicable to impose tolls on every edge of a given traffic network individually. Therefore, we study the mathematical optimization problem of computing tolls for a predefined subset of roads with the objective of reducing the total travel time. Furthermore, we discuss the related problem of computing tolls when only a finite number
of taxable roads is accounted for. For both problems we present algorithms applicable on general large-scale traffic networks. We test their performance and solution quality systematically on real-world instances. Finally, the results are integrated into an agent-based transport simulator to achieve qualitatively better solutions and reduced convergence time of the simulation process.
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
1.1 Related Work
Already in 1920 Pigou [45] observed that traffic participants should pay a fee equal to the difference of marginal social and marginal private cost (marginal cost pricing) to induce a system optimal traffic distribution. Later on, many scientists studied the theoretical background of marginal cost pricing, among them Knight [35], Beckmann et al. [10] and Smith [53]. Bergendorff et al. [11] and Larsson and Patricksson [40] showed that the set of tolls which induces a system optimal user equilibrium can be characterized by a non-empty polyhedron defined in terms of a system of linear inequalities. Hearn and Ramana [32] introduced toll optimization problems where the objective is to minimize a toll dependent function over the polyhedron of feasible tolls which induce an optimal flow. Subsequently, several efficient algorithms for computing such secondary toll optimization problems were worked out, among them toll computation algorithms which minimize the total revenue collected from the network users, see Dial [22, 23] and Bai et al. [4]. Furthermore, Bai and Rubin [6] and Bai et al. [5] proposed algorithms for the NP-hard minimum toll booth problem where the objective is to minimize the number of taxed edges.
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.
- Quote paper
- Ingo Kleinert (Author), 2011, Tolls in Transportation Networks, Munich, GRIN Verlag, https://www.hausarbeiten.de/document/172954
