Domingo Vencedor

The Nagel-Schreckenberg model is a theoretical model for the simulation of freeway traffic. It was developed in the early 90s by the German physicists Kai Nagel and Michael Schreckenberg. Using algorithms it delivers predictions for roadway traffic, in particular concerning traffic density and traffic flow. The model was the first to explain how traffic congestions can emerge without external influence as a result of imperfect driving behavior. It is related to the fields of chaos theory and game theory.

Structure of the model

In the Nagel-Schreckenberg model, a road is comprised of several segments, called cells. For the simpler versions of the model, these cells are aligned in a row whose ends are connected so that all cells make up a circle. The cells can have either of two possible statuses: occupied or empty, i.e. either exactly one vehicle is in said cell or no vehicle. Neither can one vehicle be in more than one cell at the same time, nor can multiple vehicles occupy a single cell at the same time. Each vehicle is assigned an integer value of velocity. For the most common versions of the Nagel-Schreckenberg model possible velocities range from zero to five (i.e. the integer value of five presents the maximum speed). Time is distributed into rounds. In each round, firstly the next speeds, and by that the next movements, of all vehicles are determined simultaneously. After this is done, all vehicles are actually moved. This structure corresponds to a cellular automaton. The model is based on the assumption of the worst possible traffic situation, i.e. the persistent threat of congestion. Passing and accidents are not part of the model.

Modeling procedure

In each round, the following four steps are conducted.

Acceleration: In case a vehicle has not reached its maximum speed yet and, at the same time, the distance to the vehicle in front of it (counted in cells, i.e. an integer value) is larger than its speed (by definition also an integer value), the vehicle’s speed is increased by one speed step.
Slowing down: In case the distance to the vehicle in front of the observed vehicle (counted in cells) to is smaller than its speed, the speed of the vehicle is reduced so that the new speed equals the distance between both vehicles (the cells that are occupied by the two vehicles are not counted). This step serves the prevention of accidents).
Randomization: The speed of the observed vehicle is now reduced by one speed step with a probability of p.
Vehicle motion: Finally, all vehicles are moved forward the number of cells that equals the speed that they have been assigned by the first three steps of the model.

Randomization

The randomization step (third step of above described Modeling Procedure) addresses three phenomena at the same time:

First, a driver might not use the chance to reach maximum speed. That is why a vehicle that had been accelerated in the first step might reverse this acceleration in the third step to account for the possibility that a driver does not use their chance to accelerate.
Second, a vehicle which has already reached its maximum speed can fall back. This accounts for fluctuations at maximum speed caused by dallying. For environments where a significant amount of vehicles are equipped with cruise control (e.g. the United States), the model delivers better results when this property is excluded from the model.
Third, a vehicle that already had to break due to insufficient distance to its predecessor can lose additional speed because of dallying. This takes into account the fact that a driver might overreact at breaking. This overreaction has been identified as the reason for the emergence of traffic congestion without external cause.

Without this step the model would be completely deterministic. If this step of randomization is not included into the model, it will quickly reach a stationary pattern.

Model Properties

The model explains how traffic congestions can emerge without external influences because of dallying and overreacting at braking.
It was shown that variants of the Nagel-Schreckenberg model deliver (with a tolerance in the range of jam spacing) precisely the same results for vehicle trajectories as kinematic wave models and linear vehicle-following models (see Daganzo, 2006).
To reach a realistic model of congestion on freeways, the probability of slowing down in the third step of the model has to be higher for starting (after being forced to stop due to traffic congestion) than for all other cases.
To further increase the model’s closeness to reality, the effects of brake lights can be considered.
For a maximum speed of one (instead of five) and a probability of random slowing down, the model equals cellular automaton 184 by Stephen Wolfram.
The model is minimalist, i.e. that the exclusion of any element of the model’s definition will immediately cause loss of crucial properties of traffic.
A simulation of millions of vehicles with the Nagel-Schreckenberg model is possible with parallel working computers.

Application

The Nagel-Schreckenberg model was further developed during Nagel's research stay at the Los Alamos National Laboratory for parallel computing. The transportation forecasting model Transims is based on this work.
In the German state (bundesland) of North Rhine-Westphalia the Nagel-Schreckenberg model has been used as the foundation for a comprehensive traffic forecasting system which is accessibile online (see Weblinks).

Literature

Nagel, K. and M. Schreckenberg. A cellular automaton model for freeway traffic, J. Phys. I France 2 (1992) pp. 2221-1229.
Daganzo, C. In traffic flow, cellular automata = kinematic waves. Transportation Research Part B. 40 (2006) pp. 396-403.

Weblinks

Link to the original work of Nagel and Schreckenberg: [1] (PDF, 1038 KB)
Link to a website that contains an online tool with which one can run the Nagel-Schreckenberg model and related simulations on a circular road [2]
North Rhine-Westphalia's OLSIM traffic forecasting system [3] (German)