Nash Flows over Time in Transport and Evacuation Simulation

Project 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.