Project
IN-6
Homotopy Methods for Dynamic Flows
Project Heads
Max Klimm
Project Members
Philipp Warode
Project Duration
01.01.2022 – 31.12.2022
Located at
TU Berlin
Description
Motivation: Traffic Flows
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
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.
Project Goals
Although Nash flows over time have been researched for many years now, there are still many open questions regarding the model.
Open questions
- Does the equilibrium flow consist of finitely many phases?
It is known that a Nash flow over time consists of consecutive phases in which the in- and outflow rates are constant. However, it is not yet knwon, whether the number of this phases is finite. - How there an efficient way to compute thin flows? If not, what is the complexity of computing a thin flow?
The computation of Nash flows over time relies on the computation of the derivatives of the flows that are also called thin flows. There is no known, efficient algorithm to compute these flows.
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.
Further information
For more information see also the project’s webpage at the chair of discrete optimization at TU Berlin.
Selected Publications
- Parametric Computation of Minimum Cost Flows with Piecewise Quadratic Costs (), Mathematics of Operations Research, 47(1):812–846, 2022.
- Computing all Wardrop Equilibria parametrized by the Flow Demand (), SODA 2019 – Proc. 30th ACM-SIAM Symposium on Discrete Algorithms, pp. 917–934.
Selected Pictures
A Nash flow over time.
Please insert any kind of pictures (photos, diagramms, simulations, graphics) related to the project in the above right field (Image with Text), by choosing the green plus image on top of the text editor. (You will be directed to the media library where you can add new files.)
(We need pictures for a lot of purposes in different contexts, like posters, scientific reports, flyers, website,…
Please upload pictures that might be just nice to look at, illustrate, explain or summarize your work.)
As Title in the above form please add a copyright.
And please give a short description of the picture and the context in the above textbox.
Don’t forget to press the “Save changes” button at the bottom of the box.
If you want to add more pictures, please use the “clone”-button at the right top of the above grey box.