To top

Homotopy Methods for Dynamic Flows

Motivation: Traffic Flows

Image credit: Staboslaw via Pixabay, under Pixabay License

Private motorized transport has an enormous impact on life in modern cities. Not only are large parts of the urban infrastructure planned around road traffic and optimized for it. Road traffic also accounts for a not insignificant share of noise, air and environmental pollution as well as the emission of climate-damaging gases.

Therefore, it is essential for modern urban planning to understand inner-city individual traffic and the underlying dynamics and to use the resulting insights to improve the traffic situation.

The Model: Dynamic Nash Equilibria

Image credit: Elchinator via Pixabay, under Pixabay License

We look at road traffic from a game theoretic perspective: A set of agents (the drivers) with individual objectives (moving from A to B in a road network) can choose from a set of possible strategies (different routes). When following a strategies, the agents influence each others's travel time by inducing congestion on the roads they use. Assuming that the agents act rational and selfish, everyone strive to choose a fastest route possible. Since a large number of players repeats this game over and over, from a macroscopic view the overall situation converges to an equilibrium state where no agent can improve their route individually.

Since we are mainly interested in a macroscopic view of the situation, we consider models that treat the road traffic as a continuous stream of infinitesimally small particles rather than an interaction of individual agents. The underlying mathematical object to model this is a flow. Equilibrium flow models like the widely used Wardrop equilibrium model have been used for a long time to model road traffic.

The disadvantage of the Wardrop equilibrium and related models is that it only considers static flows. In such models, flow is thought to be travelling with a constant, static rate through the network. While this allows for a rather good approximation of traffic flows in relatively constant situation on the larger scale, such as the traffic flow in rush hour conditions, static flow models lack the ability to accurately model the underlying dynamics of traffic.

In order to model more the more complex dynamics, we consider Flows over time first introduced by Ford and Fulkerson. Koch and Skutella introduced the following model for Nash flows over time, where infinitesimally small particles move through a network consisting of edges. For every edge, there is a fixed time that is needed to traverse the respective edge as well as a capacity. If the capacity is exceeded, queues build on the edges, slowing the particles down. This is why this model is also referred to as the dynamic queuing model. A Nash flow in this setting is a flow where every particle travels only on shortest paths.

Instance: A flow over time network
  • Graph $G = (V,E)$ with vertices $V$ and edges $E$
    The road network where the roads are represented by the edges and intersections are represented by the vertices.
  • Edge travel times $\tau_e \geq 0, e \in E$
    The time that a particle/driver needs to traverse the edge $e \in E$ without any congestion.
  • Edge capacities $\nu_e > 0, e \in E$
    The amount of particles/drivers that can traverse an edge within one time unit. If the capacities are exceeded, queues start to build up on the edges.
  • Inflowrate at some source vertex $s \in V$ given as a function $u : \mathbb{R}_{\geq 0} \to \mathbb{R}_{\geq 0}$, a terminal vertex $t$
    The inflow rate of traffic that enters the network at the specific vertex $s$ depending on the time and the target target vertex $t$.
Solution: A Nash flow over time
  • Inflow functions $f^+_e : \mathbb{R}_{\geq 0} \to \mathbb{R}_{\geq 0}$ and outflow functions $f^-_e : \mathbb{R}_{\geq 0} \to \mathbb{R}_{\geq 0}$ for all vertices that satisfy the following conditions
    Functions that specify the amount of flow entering and leaving at every given point in time.
  • $\displaystyle \sum_{e \in \delta^+(v)} f^+_e (\theta) - \sum_{e \in \delta^-(v)} f^-_e (\theta) = \begin{cases} u(\theta) & \text{if } v = s, \\ 0 & \text{if } v \neq s, t \end{cases}$
    Flow conservation: In- and outflow sum to zero (if $v \neq s, t$) or to the inflow rate (at $v = s$).
  • For almost all points in time $\theta$, for every edge $e = (v,w) \in E$ with $f^+(\theta) > 0$, we have \[ l_w( \theta ) = l_v (\theta) + \frac{z_e(l_v(\theta))}{\nu_e} + \tau_e \] where
    • $l_v (\theta)$ is the earliest point in time, where a particle entering the network at time $\theta$ can reach vertex~$v$
    • $z_e(\theta)$ is the amount of flow waiting in a queue on edge $e$ at time $\theta$.
    Equilibrium conditions: Every particle moves only on edges such that the particle arrives at the next vertex as early as possible. This implies no particle has an incentive to deviate to another path in this configuration.
Dynamic Flow animation A Nash flow over time.

Animation generated with Nash Flow Computation Tool

Project Goals

Image credit: Stocksnap via Pixabay, under Pixabay License

Although Nash flows over time have been researched for many years now, there are still many open questions regarding the model.

Open questions
Our approach

In previous work we developed homotopy methods to compute parametrized Nash equilibrium flows in the static Wardrop equilibrium model. The solution flows of in these models can be expressed as solutions to differential equations on piecewise linear vector fields. Since the same holds true for the dynamic queuing model and we were able to develop efficient computation schemes for the static case, we hope to extend our techniques also to the dynamic flow case.

References

  • Parametric Computation of Minimum Cost Flows with Piecewise Quadratic Costs ( and )
    Mathematics of Operations Research, 47(1):812–846, .
    PDF DOI Preliminary version (SODA 2019) Bibtex
    @article{KlimmWarode2021,
    author = {Max Klimm and Philipp Warode},
    doi = {10.1287/moor.2021.1151},
    journal = {Mathematics of Operations Research},
    number = {1},
    pages = {812--846},
    title = {Parametric Computation of Minimum Cost Flows with Piecewise Quadratic Costs},
    volume = {47},
    year = {2022},
    }
  • Continuity, Uniqueness and Long-Term Behavior of Nash Flows Over Time (, and )
    arXiv, abs/2111.06877, .
    Bibtex
    @article{olverseringkoch2021,
    author = {Neil Olver and
    Leon Sering and
    Laura Vargas Koch},
    title = {Continuity, Uniqueness and Long-Term Behavior of Nash Flows Over Time},
    journal = {arXiv},
    volume = {abs/2111.06877},
    year = {2021},
    eprinttype = {arXiv},
    eprint = {2111.06877},
    }
  • Computing all Wardrop Equilibria parametrized by the Flow Demand ( and )
    SODA 2019 – Proc. 30th ACM-SIAM Symposium on Discrete Algorithms, pp. 917–934.
    PDF DOI Extended version (MOR 2021) Bibtex
    @inproceedings{KlimmWarode2019,
    author = {Max Klimm and Philipp Warode},
    booktitle = {SODA 2019 – Proc. 30th ACM-SIAM Symposium on Discrete Algorithms},
    doi = {10.1137/1.9781611975482.56},
    pages = {917--934},
    title = {Computing all {Wardrop} Equilibria parametrized by the Flow Demand},
    year = {2019},
    }
  • Nash Equilibria and the Price of Anarchy for Flows over Time ( and )
    Theory Comput. Syst., 49(1):71–97, .
    DOI Bibtex
    @article{DBLP:journals-mst-KochS11,
    author = {Ronald Koch and
    Martin Skutella},
    title = {Nash Equilibria and the Price of Anarchy for Flows over Time},
    journal = {Theory Comput. Syst.},
    volume = {49},
    number = {1},
    pages = {71--97},
    year = {2011},
    doi = {10.1007/s00224-010-9299-y},
    timestamp = {Sun, 28 May 2017 13:18:25 +0200},
    biburl = {https://dblp.org/rec/journals/mst/KochS11.bib},
    bibsource = {dblp computer science bibliography, https://dblp.org},
    }
  • Maximal flow through a network ( and )
    Canadian Journal of Mathematics, Cambridge University Press, 8:399–404, .
    Bibtex
    @article{ford1956maximal,
    title = {Maximal flow through a network},
    author = {Ford, L. R. and Fulkerson, D. R.},
    journal = {Canadian Journal of Mathematics},
    volume = {8},
    pages = {399--404},
    year = {1956},
    publisher = {Cambridge University Press},
    }