AA3 – Networks

Project

AA3-2

Nash flows over time in transport and evacuation simulation

Project Heads

Kai Nagel, Martin Skutella

Project Members

Leon Sering (TU), Theresa Ziemke (TU)

Project Duration

01.01.2019 – 31.12.2021

Located at

TU Berlin

Description

This interdisciplinary project aims to make progress at the intersection of network flows, algorithmic game theory, and traffic simulation and control. The goal is to gain a better structural understanding and, based upon this, provide efficient algorithmic methods to handle real-world traffic scenarios, e.g., in the context of evacuation planning. To this end, in interdisciplinary collaboration between mathematicians and traffic engineers, advanced flow over time models for dynamic user equilibria will be developed and mathematically analyzed. Solutions resulting from novel flow over time methods will be empirically evaluated and integrated into the large-scale agent-based transport simulation tool MATSim.

Even though real-world traffic consists of non-splittable vehicles, continuous flows over time describe average traffic rates. Our first results show that, from a stochastic point of view, the discrete MATSim model can be interpreted as a realization of a random experiment where the average of the distribution is given by a dynamic user equilibrium in the flow over time model. To confirm the strong connection between the two models even further, we analyze the discretization error by decreasing the time step and vehicle size within MATSim and show experimentally that the average deviation in travel times and cumulative inflow rates decreases.

In addition to that, we extend the flow over time model by several real-world traffic features, such as spillback, kinematic waves and time-varying capacities and transit times and proof the existence of dynamic user equilibria in this generalized model.

Project Webpages

Selected Publications

  1. L. Graf, T. Harks. & L. Sering, Dynamic Flows with Adaptive Route Choice. Mathematical Programming, 2020. https://doi.org/10.1007/s10107-020-01504-2
  2. J. Israel & L. Sering, The Impact of Spillback on the Price of Anarchy for Flows Over Time. accepted at 13th Symposium on Algorithmic Game Theory, 2020. preprint: arXiv:2007.04218.
  3. H. M. Pham & L. Sering, Dynamic Equilibria in Time-Varying Networks. accepted at 13th Symposium on Algorithmic Game Theory, 2020. preprint: arXiv:2007.01525.
  4. T. Ziemke, L. Sering, L. Vargas Koch, M. Zimmer, K. Nagel, & M. Skutella, Flows Over Time as Continuous Limits of Packet-Based Network Simulations. submitted to The 23rd Euro Working Group on Transportation, 2020.
  5. L. Sering & L. Vargas Koch, Nash Flows Over Time with Kinematic Waves. submitted to Operations Research, 2019.
  6. L. Sering, Multi-Commodity Nash Flows Over Time. submitted to Mathematics of Operations Research, 2020.
  7. A. Adamik & L. Sering, Atomic Splittable Flow Over Time Games. submitted to The 16th Conference on Web and Internet Economics, 2020.

Selected Pictures

Flow dynamics in MATSim and the flow over time model.
Illustration of flow dynamics in MATSim (left hand side) and flow over time model (right hand side). The numbers denote the capacities.
Deviation in Travel Times
Travel times by departure time in MATSim and in a Nash flow over time for time step size 1, 1/2, 1/4 and 1/8 (from left to right) in a Braess network with three routes: top, middle, bottom.

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.