TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 15412

Dynamic Traffic Models in Transportation Science

( Oct 04 – Oct 09, 2015 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/15412

Organizers

Contact



Motivation

Traffic assignment models play an important role for traffic planers to predict traffic distributions, especially, in light of possible changes of the infrastructure, e.g., road constructions, traffic light controls, 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. Dynamic models, on the other hand, 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) 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.

Complementary to mathematical approaches, 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 ignore 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. For many microscopic simulation models (and even DTA models) the following questions are especially pertinent:

  • Under which conditions do the models admit an equilibrium?
  • Is an equilibrium efficiently (polynomial time) computable or is the computation (PPAD)-hard?
  • Are multiple equilibria possible and how can they be qualitatively as well as quantitatively distinguished?
  • Which type of equilibrium is computed depending on the choice of the learning processes of agents?
  • How do we efficiently compute optimal (or approximatively) network designs or traffic light controls subject to dynamic equilibrium constraints?
  • How does stochasticity, for example in the behavioral models and/or in the network loading, affect the results and their mathematical interpretation?

In this seminar we want to bring together leading researchers from three different communities (Simulations, Dynamic Traffic Assignment and Algorithmic Game Theory) to discuss ways to narrow the existing gap between complex simulation based models and the existing theory.


Summary

Traffic assignment models play an important role for traffic planers to predict traffic distributions, especially, in light of possible changes of the infrastructure, e.g., road constructions, traffic light controls, 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 ignore 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. Against this background, the seminar provided (partial) answers to questions of the following type:

  • Under which conditions do microscopic simulation models and dynamic traffic assignment models admit an equilibrium?
  • Is an equilibrium efficiently (polynomial time) computable?
  • Which models lead to multiple equilibria and how do the parameters of a learning process influence the resulting equilibrium outcome?
  • What are the implications of possible intractability results (PPAD-hardness) on the plausibility of existing models?
  • how do we compute optimal (or approximatively) network designs or traffic light controls subject to dynamic equilibrium constraints in polynomial time?

The seminar brought together leading researchers from three different communities -- Simulations (SIM), Dynamic Traffic Assignment (DTA) and Algorithmic Game Theory (AGT) -- and identified ways to narrow the existing gap between complex simulation based models and the existing theory. Among other points, the seminar initiated a systematic study of the complexity of equilibrium computations for DTA models -- which is the core task when resolving dynamic traffic assignment problems. Equilibrium computation and its complexity status is a core topic in AGT. The seminar provided an excellent forum for a discourse of these questions between the DTA, SIM and AGT community which initiated several novel research questions and directions. The seminar also stimulated a conceptual discourse regarding the validity of DTA and microscopic simulation models in terms of their predictive power and use for optimization based approaches.

Overall, the seminar was a big success both in terms of stimulating new and very fruitful collaborations between so far separate communities and also with respect to novel insights and results on traffic equilibria and related concepts. We got enthusiastic feedback from many participants which is also reflected in the survey conducted by Dagstuhl.

Copyright José R. Correa, Tobias Harks, Kai Nagel, Britta Peis, and Martin Skutella

Participants
  • Umang Bhaskar (TIFR Mumbai, IN) [dblp]
  • Roberto Cominetti (University of Chile - Santiago de Chile, CL) [dblp]
  • José R. Correa (University of Chile - Santiago de Chile, CL) [dblp]
  • Martin Gairing (University of Liverpool, GB) [dblp]
  • Yannai A. Gonczarowski (The Hebrew Univ. of Jerusalem, IL) [dblp]
  • Tobias Harks (Maastricht University, NL) [dblp]
  • Martin Hoefer (Universität des Saarlandes, DE) [dblp]
  • Max Klimm (TU Berlin, DE) [dblp]
  • Ekkehard Köhler (TU Cottbus, DE) [dblp]
  • Felix König (TomTom - Berlin, DE) [dblp]
  • Jannik Matuschke (TU Berlin, DE) [dblp]
  • Kai Nagel (TU Berlin, DE) [dblp]
  • Neil Olver (VU University of Amsterdam, NL) [dblp]
  • Britta Peis (RWTH Aachen, DE) [dblp]
  • Rahul Savani (University of Liverpool, GB) [dblp]
  • Marco Scarsini (LUISS Guido Carli - Rome, IT) [dblp]
  • Miriam Schlöter (TU Berlin, DE) [dblp]
  • Daniel Schmand (RWTH Aachen, DE) [dblp]
  • Marc Schröder (Maastricht University, NL) [dblp]
  • Alexander Skopalik (Universität Paderborn, DE) [dblp]
  • Martin Skutella (TU Berlin, DE) [dblp]
  • Nicolas Stier-Moses (Facebook - Menlo Park, US) [dblp]
  • Martin Strehler (TU Cottbus, DE) [dblp]
  • Chris Tampère (KU Leuven, BE) [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]

Related Seminars
  • Dagstuhl Seminar 18102: Dynamic Traffic Models in Transportation Science (2018-03-04 - 2018-03-09) (Details)
  • Dagstuhl Seminar 22192: Dynamic Traffic Models in Transportation Science (2022-05-08 - 2022-05-13) (Details)
  • Dagstuhl Seminar 24281: Dynamic Traffic Models in Transportation Science (2024-07-07 - 2024-07-12) (Details)

Classification
  • data structures / algorithms / complexity
  • modelling / simulation
  • networks

Keywords
  • dynamic traffic equilibria
  • complexity of equilibrium computation
  • simulation
  • dynamic network flow theory
  • network optimization