AA3 – Networks

Project

AA3-2

Nash Flows over Time in Transport and Evacuation Simulation

Project Heads

Kai Nagel, Martin Skutella

Project Members

Theresa Ziemke (TU) and Leon Sering (TU until 03/21, ETH Zurich since 04/21)

Project Duration

01.01.2019 – 30.11.2023

Located at

TU Berlin

Description

This interdisciplinary project studies 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. In this interdisciplinary collaboration between mathematicians and traffic engineers, we develop advanced flow over time models and packet routing models for dynamic user equilibria and mathematically analyzed. Solutions resulting from novel flow over time methods are 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. One of our 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 analyzed the discretization error by decreasing the time step and vehicle size within a packet model similar to MATSim and proved that the travel times and cumulative inflow rates of the packet model converges to the respective functions in the flow over time model. Furthermore, we show that the convergence result implies the existence of approximate equilibria in the competitive version of the packet routing model. This is of significant interest as exact equilibria, similar to almost all other competitive models, cannot be guaranteed in the multi-commodity setting.

  

In addition to that, we extended the flow over time model by several real-world traffic features, such as spillback, kinematic waves and time-varying capacities and transit times and proved 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. doi:10.1007/s10107-020-01504-2
  2. J. Israel & L. Sering, The Impact of Spillback on the Price of Anarchy for Flows Over Time. 13th Symposium on Algorithmic Game Theory, 2020.doi:10.1007/978-3-030-57980-7_8.
  3. H. M. Pham & L. Sering, Dynamic Equilibria in Time-Varying Networks. 13th Symposium on Algorithmic Game Theory, 2020. doi:10.1007/978-3-030-57980-7_9.
  4. L. Sering, Nash Flows Over Time. Dissertation, TU Berlin, 2020. doi:10.14279/depositonce-10640.
  5. T. Ziemke, L. Sering, L. Vargas Koch, M. Zimmer, K. Nagel, & M. Skutella, Flows Over Time as Continuous Limits of Packet-Based Network Simulations. Transportation Research Procedia, 2021. doi:10.1016/j.trpro.2021.01.014.
  6. L. Sering & L. Vargas Koch, Nash Flows Over Time with Spillback. ACM-SIAM Symposium on Discrete Algorithms, 2018. doi:10.1137/1.9781611975482.57
  7. L. Sering & L. Vargas Koch, Nash Flows Over Time with Spillback and Kinematic Waves. 2018. doi:10.48550/arXiv.1807.05862
  8. L. Sering, L. Vargas Koch & T. Ziemke, Convergence of a Packet Routing Model to Flows Over Time. Proceedings of the 22nd ACM Conference on Economics and Computation (EC’21), 2021. doi:10.1145/3465456.3467626
  9. L. Sering, L. Vargas Koch & T. Ziemke, Convergence of a Packet Routing Model to Flows Over Time. Mathematics of Operations Resarch, 2022. doi:10.1287/moor.2022.1318
  10. T. Ziemke, L. Sering & K. Nagel, Spillback Changes the Long-Term Behavior of Dynamic Equilibria in Fluid Queuing Networks. Accepted for ATMOS 2023.

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.
Picture reference: [5]

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.
Picture reference: [5]

Packet routing game without Nash equilibrium.

Their are six players, indicated by different colors. The transit times are depicted beside the arcs and all arcs have a capacity of 1. The two main players, pursuer 1 going from o_P to d_P and evader 2 going from o_E to d_E, are the only players who can choose a path. The purpose of the remaining four players is to transfer the information between the main players. By giving the four long arcs priority in the merging, we obtain a matching pennies game between the pursuer and the evader, which does not possess a Nash equilibrium.
Picture reference: [9]

Oscillating phases of the Nash flow over time with spillback.

Cumulative flow values (left hand side) for the three different routes in a Braess-like network periodically change over time and no final phase is reached. Queue length and with that travel time (right hand side) unboundedly increases over time, although the example consists of a single-commodity instance with constant inflow rate. This shows that the long-term behavior of dynamic traffic equilibria heavily depends on whether spillback is captured in the traffic model or not.
Picture reference: [10]

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.