Dynamic Network Flows with Adaptive Route Choice based on Current Information
Description
In this book Lukas Graf studies dynamic network flows which are a model for individual car traffic in road networks. It is assumed that drivers choose their routes based on information about the current state of the network in such a way as to selfishly minimize their own arrival time at their destination. Whilst on their journey the drivers adapt their current route choices based on the changing state of the network. A dynamic flow wherein every (infinitesimally small) flow particle behaves in this way is then called an instantaneous dynamic equilibrium. After giving a mathematically precise definition of this equilibrium concept the author shows existence of those equilibrium flows, studies their computational complexity and derives bounds on their quality.
More details
Other editions
Additional editions
Person
After receiving his PhD from the University of Augsburg, Lukas Graf now works as a research assistant at the chair for mathematical optimization at the University of Passau.
Content
- Intro
- Many Thanks
- Contents
- Symbols and Notation
- General
- Topology
- Measure Theory
- Functions and function spaces
- Graphs
- Networks
- Dynamic flows
- 1 Introduction
- 1.1 A (Brief) Historic Overview of Dynamic Flows
- 1.2 Thesis Contribution and Organization
- 2 Preliminaries
- 2.1 General Notation
- 2.2 Measure Theory
- 2.3 Topology
- 2.4 Two General Existence-Results
- 2.5 Graph Theory and Optimization
- 2.6 Complexity Theory
- 3 Model
- 3.1 Physical Model
- 3.1.1 Anonymous Edge Flows
- 3.1.2 Multi-Commodity Edge Flows
- 3.1.3 Network Flows
- 3.2 Behavioural Model
- 3.2.1 Instantaneous Dynamic Equilibria
- 3.2.2 Quality Measures for Dynamic Flows
- 3.3 Model Summary
- 3.4 Bibliographic Notes and Open Questions
- 4 Existence of IDE
- 4.1 A Meta-Theorem on IDE-Existence
- 4.2 Extension Lemma for General Inflow Rates
- 4.3 Extension-Lemmas using IDE-Thin Flows
- 4.3.1 IDE-Thin Flow Augmentation
- 4.3.2 IDE-Thin Flows via a Fixed Point Theorem
- 4.3.3 IDE-Thin Flows via Convex Optimization
- 4.4 Bibliographic Notes and Open Questions
- 5 Computational Complexity of IDE
- 5.1 Computing IDE-Thin Flows
- 5.1.1 Multi-Commodity Networks
- 5.1.2 Single-Commodity Networks
- 5.2 Bounding the Number of Extensions
- 5.2.1 Upper Bound for Single-Commodity Networks
- 5.2.2 Lower Bounds
- 5.3 NP-Hardness of IDE-Decision Problems
- 5.4 Bibliographic Notes and Open Questions
- 6 Quality of IDE
- 6.1 Upper Bounds
- 6.1.1 Acyclic Networks
- 6.1.2 General Single-Commodity Networks
- 6.2 Lower Bounds
- 6.2.1 Single-Commodity Networks
- 6.2.2 Multi-Commodity Networks
- 6.3 The Price of Anarchy
- 6.4 Bibliographic Notes and Open Questions
- 7 Conclusion
- 7.1 Summary and Comparison to Full Information Equilibria
- 7.2 Potential Directions for Future Research
- References
