Adaptive Traffic Control

Project director: Prof. Dr. Rolf H. Möhring
Institut für Mathematik, Technische Universität Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany
Tel: +49 (0)30 - 314 24594
e-mail: moehring[at]math.tu-berlin.de
Researcher: Dr. Tobias Harks
Institut für Mathematik, Technische Universität Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany
Tel: +49 (0)30 - 314 29384
e-mail: harks[at]math.tu-berlin.de
Support: Bundesministerium für Bildung und Forschung (BMBF)
Cooperation partner: Planung Transport Verkehr AG (PTV)
PTV

Project description.

Todays traffic situations in big cities are still far from being satisfactory. Traffic jams at rush hour or at special events (sport or music events) occur frequently and people complain about increased total travel time. Additionally, traffic congestion significantly increases exhaust gas pollution. The situation is particularly dramatic in the rising megacities of Asia, Middle-, and Southamerica. The traffic volume in China, for instance, increased in 2005 by 15% (http://www.fon.org.cn/greenchoice) and is expected to grow faster in the next years, making sound network planing and traffic control indispensible.

Typically, network planning and traffic control both rely on simulation models. These models are capable of describing traffic behavior for certain network and traffic configurations but usually fail to provide strategies for adaptively controling the traffic and optimizing the system's performance.

The goal of this project, is to bring together simulation models and mathematical optimization models so as to develope a new notion of adaptive traffic control. The idea is to combine optimization based methods and models (e.g, static, dynamic, and distributed network flow theory, algorithmic game theory, traffic signal control theory) with extensive large scale traffic microsimulations. Since the interdependencies between such simulations and existing mathematical models are far from being well understood, several fundamental problems and questions arise: How can microsimulations be used to generate realistic but still tractable mathematical models. How can in turn mathematical models be used to improve and accelerate the simulations?

VISUM
Congestion collapse on a network of one-way streets. The red cars are those causing the gridlock by stopping in the middle of the intersection, ©http://en.wikipedia.org/wiki/Gridlock.

Cooperation Partner.

Our cooperation partner, the ptv AG from Karlsruhe, Germany, is one of Europe's leading traffic software developing companies.

Microsimulations.

In recent years, microscopic traffic simulations have become an increasingly active field of research in transport science. Micro refers to the fact that all elements of the transport system, like roads, crossings, vehicles, and most importantly travelers (referred to as agents) are resolved. This modeling approach is in contrast with the more aggregate models implemented in current transport planning software and used by transportation planners. While those programs have seen several decades of development and practical use, agent-based microscopic simulation systems are still relatively new and are mostly used in small and medium scale scientific scenarios rather than in real world applications. But new technologies, such as robust and fast object-oriented programming languages and high performance computing clusters make the applications increasingly realistic and increasingly large scale.

For further information see www.matsim.org and www.vsp.tu-berlin.de.

VISUM
Screenshot of the "Berliner Stern" crossing.

Microsimulations and Evacuation Models.

During or after mega-events like world cup soccer games, due to natural disasters like Hurricanes or Tsunamis or even during the rush hour it is eligible to evacuate the traffic participants or even the whole population as fast as possible. For the simulation and evacuation of metropolises a large-scale multi agent traffic simulation can be used. In this case the locations of the persons at the time of the evacuation are computed by a regular activity based demand modeling framework as often used in the transport science. Evacuation flow is simulated by a simple queue model that only uses free speed and bottleneck capacities as input. This approach is implemented inside the MATSim (www.matsim.org) framework for transportation planning. The results from the simulation give an estimate of the time it could take to evacuate the endangered area. Furthermore they can be used for evacuation training purposes and for guidance advices in an emergency.

One goal of the project is to improve existing solutions in the area of dynamic flow models and to investigate mathematical methods improving the grasp of the different problems arising from such situations. By the use of the MATSim framework it will be possible to evaluate those solutions empirically.

Researchers:

Prof. Dr. Kai Nagel, Dipl. Inf. Dominik Grether, and Dipl. Inf. Gregor Lämmel

Fakultät V, Verkehrs- und Maschinensysteme Institut für Land- und Seeverkehr, Fachgebiet Verkehrssystemplanung und Verkehrstelematik, Sekr. SG 12, Salzufer 17-19, D-10587 Berlin

Optimization and Simulation.

Microsimulations and network optimization are two different techniques to quantitatively analyze traffic flows.

The main idea of microsimulations is to simulate rational behavior of agents in a distributed system. The goal is to find a steady state, where no agent can unilaterally improve its utility by deviating to another strategy (by choosing another route). Such stable states are known as Nash equilibria and, since the model explicitly involves travel times, an equilibrium point constitutes a dynamic Nash equilibrium.

This project aims at combining network optimization and microsimulations so as to achieve a new notion of traffic modeling, prediction, and control. In a first step, we want to integrate network optimization and microsimulations by generating traffic routes using static network flow methods, which in turn are fed into the simulator. If the traffic model used for the network optimization problem accurately approximates the dynamic Nash equilibrium, then the hope is to effectively reduce convergence time of the simulator. Furthermore, a clever choice of start routes will eventually guide the simulation process to a qualitatively good equilibrium.

Researchers:

Prof. Dr. Rolf H. Möhring, Dr. Tobias Harks

Evacuation Models.

Evacuations are extreme situations and nothing else might show the bottlenecks of a road system as clearly. However, evacuations are also rare and much time can be spent preparing for such an event. A thoughtfully worked out and convincing evacuation plan can greatly improve the time needed to clear an area.

This project aims to model evacuation scenarios using techniques from combinatorial optimization and network flow theory in particular. While microsimulation likely is the most realistic way of modeling, network flow models are often computationally more efficient and their properties are better understood. An important result of this more theoretical approach are earliest arrival flows. Such an earliest arrival flow has the property that at any point in time as many people are already rescued as possible. The existence of earliest arrival flows, however, is only guaranteed in a very stylized setting.

Nonetheless, these models can prove to be good starting points for the microsimulation. If the computed flows are already close to what the microsimulation considers a stable state, then less of the computational intensive iterations of the microsimulation are needed, resulting in a speed-up. For this, the flow model must find a good compromise between effectiveness and realism. The stability criterion also implies that the evacuation plan derived from the computed flow should be convincing to the selfish agents of the simulation. Otherwise, the agents would stray from the suggested evacuation plan and, despite the plan being a realistic and good plan, break it by hoping to find a better way out for themselves, thus moving the simulation into a completely different direction.

Thus, it is the goal of this project to find better models and devise efficient algorithms, all based on a solid mathematical approach, to supply good evacuation plans to the microsimulation group.

Researchers:

Prof. Dr. Martin Skutella, Dipl. math. Daniel Dressler

Distributed Traffic Control.

When traffic networks are optimized statically from a global perspective, a small deviation from the normal (such as a traffic accident) can cause major delays.  On the other hand, local optimization using distributed information can help people get around the blockages, thus reducing the congestion.

We aim to develop algorithms and strategies for reducing congestion using local optimization and distributed information. These strategies will include suggestions to modify the speed and route of vehicles as well as the schedules of traffic lights.

To evaluate our algorithms properly, we also need simulation tools that show the delays that occur with the introduction of randomness into a highly-optimized system.  We are developing such a simulator that uses an accurate physics-based traffic model.

The fuel usage of a car decreases significantly and traffic jams are smoothed in our simulation when we apply our local optimizations.

We are also investigating evacuation scenarios.  One particular aspect of evacuation that we are investigating is the extent to which a confluent flow—a partition of the space into connected regions where every person in a given region leaves by the same exit—can be worse than a non-confluent flow (where any person can leave through any exit—the only constraint is that the evacuation is as fast as possible).

A confluent and a non-confluent flow.  Notice that the non-confluent flow can complete almost twice as quickly as the confluent.

Researchers:

Prof. Dr. Sándor Fekete, Dr. Chris Gray, Dipl. Phys. Björn Hendriks

Traffic Signal Control.

Waiting in front of a red traffic light is annoying. But due to the higher traffic volume in our urban regions waiting times are unavoidable. An optimal coordination of traffic lights may not yield a “green wave” for everybody, but it can significantly reduce the average traveling time of all road users.

The main task of this project is the simultaneous calculation of optimal traffic light coordination and solving a corresponding traffic assignment problem. Each change in the traffic light coordination may cause some users to search for better and faster ways and therefore change the loads of the roads. This project aims to extend static network models by a time component resulting in a more precise description of traffic networks with traffic lights. Afterwards offsets, split times and cycle times of traffic lights and the traffic flow itself are to be optimized with techniques from network flow theory and linear programming. Due to limited information and selfish behavior of the road users, results from game theory have to be considered as well. Besides theoretical results we want to obtain optimal or close to optimal solutions for real world scenarios. These results are to be evaluated via microsimulations.

The road user will not only benefit from shorter travel times. An optimal traffic light coordination also allows higher traffic loads and reduces noise and fuel consumption, because less acceleration and braking is needed.

Simulation (PTV)
Screenshot of a Traffic Simulation (PTV).

Researchers:

Prof. Dr. Ekkehard Koehler, Dipl. math. Martin Strehler

Projekt Output.

V. Bonifaci, T. Harks and G. Schaefer.
Stackelberg Routing in Arbitrary Networks.
In Proceedings of the 4th International Workshop On Internet And Network Economics (WINE), 2008, to appear.
[pdf]
T. Harks.
Stackelberg Strategies and Collusion in Network Games with Splittable Flow.
In Proceedings of the 6th Workshop on Approximation and Online Algorithms (WAOA) 2008, to appear.
[pdf]

Events.

[1] ADVEST Kick-off Meeting [pdf]