There is a trend in the transportation community (science as well as industry) to base the prediction of traffic distributions on complex computer-based simulations that are capable of resolving many elements of a real transportation system. On the other hand, the theory of dynamic traffic assignments in terms of equilibrium existence, computability and efficiency, has not matured to the point matching the model complexity inherent in simulations. This Dagstuhl Seminar is the second in a row on this topic and aims at bringing together leading scientists in the areas traffic simulations (SIM), algorithmic game theory (AGT) and dynamic traffic assignment (DTA) with the goal to further close the gap between theory and simulations. Although the three communities SIM, DTA, AGT are wellestablished and have various specialized conferences and publication outlets, there are important open problems in their intersection that have not been resolved. In particular, the following research topics will be addressed in this seminar:
Spillback at intersections
One key aspect that currently separates complex simulation tools and DTA models is the modeling of queueing dynamics at intersections. In contrast to the conceptually simple fluid queue model in which the time to traverse an edge is composed of a flow-dependent waiting time in a queue at the entrance of the edge plus a constant travel time after leaving the queue, models with spatial spillback are more realistic but considerably increase the model complexity. Spillback at intersections may cause car blockings at adjacent roads leading to propagation effects across the entire network. The modeling of spillbacks leads to complex mathematical and algorithmic challenges that will be addressed in this seminar.
Oligopolistic DTA models
As soon as some of the agents control a fleet of (autonomously guided) vehicles, the resulting network routing game turns into an oligopolistic model in which some players, like, e.g., fleet managers, control a significant amount of traffic. In the theory of network games, such models are called atomic splittable routing models, which stand in sharp contrast to the widely used non-atomic splittable models, also known under the name Wardrop model. While the field of atomic splittable routing in dynamic networks is widely unexplored, there is a broad range of literature on atomic splittable congestion games in the static setting regarding existence, uniqueness, and efficiency of oligopolistic equilibria. During the proposed seminar, we want to deeply investigate the incorporation of travel times into such oligopolistic models.
DTA models with risk-averse travellers
A common traveller reacts to heavy and uncertain traffic condition by looking for alternate, sometimes longer but less crowded and more reliable routes. We want to understand how risk aversion can be successfully incorporated into dynamic selfish routing models.
Traffic assignment models play an important role for traffic planners to predict traffic distributions, especially, in light of possible changes of the infrastructure, e.g., road constructions, traffic light controls, speed limits, tolls, etc. The prevailing mathematical approaches used in the transportation science literature to predict such distributions can be roughly classified into static traffic assignment models based on aggregated static multi-commodity flow formulations and dynamic traffic assignment (DTA) models based on the methodology of flows over time. While static models have seen several decades of development and practical use, they abstract away too many important details and, thus, become less attractive. On the other hand, dynamic models are known to be notoriously hard to analyze in terms of existence, uniqueness and computability of dynamic equilibria.
In light of the prevailing computational difficulties for realistic-sized networks, the systematic optimization of such networks (e.g., by designing the network infrastructure, link tolls, or traffic light controls) becomes even more challenging as the resulting mathematical programs with equilibrium constraints contain already in the lower level presumably "hard" optimization-, complementarity- or variational inequality problems; not to speak of the resulting optimization problem for the first level.
On the other hand, there is a trend in the transportation science community to use large-scale computer-based microsimulations for predicting traffic distributions. The striking advantage of microscopic simulations over DTA models is that the latter usually ignores the feedback of changing network conditions on user behavior dimensions such as flexible departure time choice, mode choice, activity schedule choice, and such. Current simulation tools integrate all these dimensions and many more. The increasing model complexity, however, is by far not matched by the existing theory of dynamic traffic assignments.
The seminar brought together leading researchers from three different communities - Simulations (SIM), Dynamic Traffic Assignment (DTA) and Algorithmic Game Theory (AGT). This years seminar was centered around three topics:
- Horizontal queueing models. Most of the static traffic assignment models assume that queues can occur, but do not take up any physical space. In order to make the current models more realistic one should assume that queues might effect traffic on other nearby road segments, thus, include possible spill-back effects.
- Oligopolistic competition. With the rise of autonomous vehicles new routing decisions need to be made. As a novel aspect, individual vehicles might to be interested in selfishly optimizing their routes, but cooperate with other vehicles using the same software in order to decrease the average journey time.
- Risk-averse travelers. Current static traffic models often assume that each player is rational, and has the sole purpose of minimizing travel time or distance. However, the exact travel time of many routes might be uncertain at the moment of departure. Hence, travelers might stick to a more predictable route and might be unwilling to explore possibly better alternatives.
Again, the seminar was a big success both in terms of stimulating new and very fruitful collaborations. We got enthusiastic feedback from many participants which is also reflected in the survey conducted by Dagstuhl.
- Umang Bhaskar (TIFR Mumbai, IN) [dblp]
- Roberto Cominetti (Adolfo Ibáñez University, CL) [dblp]
- Gunnar Flötteröd (KTH - Royal Institute of Technology - Stockholm, SE) [dblp]
- Martin Gairing (University of Liverpool, GB) [dblp]
- Cristóbal Guzmán (Pontifical Catholic University of Chile, CL) [dblp]
- Tobias Harks (Universität Augsburg, DE) [dblp]
- Martin Hoefer (Goethe-Universität - Frankfurt a. M., DE) [dblp]
- Anja Huber (Universität Augsburg, DE) [dblp]
- Max Klimm (HU Berlin, DE) [dblp]
- Ekkehard Köhler (TU Cottbus, DE) [dblp]
- Kai Nagel (TU Berlin, DE) [dblp]
- Neil Olver (VU University of Amsterdam, NL) [dblp]
- Carolina Osorio (MIT - Cambridge, US) [dblp]
- Britta Peis (RWTH Aachen, DE) [dblp]
- Rahul Savani (University of Liverpool, GB) [dblp]
- Marco Scarsini (LUISS Guido Carli - Rome, IT) [dblp]
- Guido Schäfer (CWI - Amsterdam, NL) [dblp]
- Heiko Schilling (TomTom International - Amsterdam, NL) [dblp]
- Miriam Schlöter (TU Berlin, DE) [dblp]
- Daniel Schmand (RWTH Aachen, DE) [dblp]
- Marc Schröder (RWTH Aachen, DE) [dblp]
- Alexander Skopalik (Universität Paderborn, DE) [dblp]
- Nicolas Stier-Moses (Facebook - Menlo Park, US) [dblp]
- Sebastian Stiller (TU Braunschweig, DE) [dblp]
- Martin Strehler (TU Cottbus, DE) [dblp]
- Chris Tampère (KU Leuven, BE) [dblp]
- Theresa Thunig (TU Berlin, DE) [dblp]
- Veerle Timmermans (Maastricht University, NL) [dblp]
- Laura Vargas Koch (RWTH Aachen, DE) [dblp]
- Bernhard von Stengel (London School of Economics, GB) [dblp]
- David Watling (University of Leeds, GB) [dblp]
- data structures / algorithms / complexity
- modelling / simulation
- dynamic traffic assignment models
- algorithms & complexity of traffic equilibrium computation
- simulation & network optimization