Nagel–Schreckenberg model

The Nagel-Schreckenberg model (short- Nash model) is a theoretical model for the simulation of road traffic. It was formulated by the solid-state physicists Kai Nagel and Michael Schreckenberg early 1990s. Using elementary rules it provides predictions for road transport, in particular traffic density (vehicles per route section) and traffic flow ( passing vehicles per unit time). The model explained the first time the jam out of nowhere as a result of non- observance of the safety distance. It touches the areas of chaos theory and game theory.

Structure of the model

In the model, the road is composed of individual sections, called cells together. The view is binary: a cell is empty or occupied by exactly one vehicle, ie, a vehicle exceeds no cell boundaries. The time has the same scheme, called rounds, disassembled. In each round is first determined simultaneously for all vehicles where they will move, then only the vehicles are moved. This structure corresponds to a cellular automata. The model is the assumption of the worst possible traffic based, so the constant fear of stagnation, because overtaking and accidents are excluded.

Computed example

The length of a cell should correspond to the place, the one standing in a traffic jam vehicle needs. This is the sum of the average length of a vehicle and the gap between two vehicles. Usually, 7.5 meters is assumed for this value. As duration of a round, the typical response time of a road user of one second is set. This results in a speed of 7.5 meters per second results (27 km / h) when a vehicle is advancing a cell in a round. As a top speed then you take most five cells per round (ie 135 km / h ) at.

The end of a round - the " update rules"

The following four steps are performed for all vehicles per round:

In the third step, three phenomena can be modeled simultaneously:

Example of the sequence of a round

Configuration at time t:

Step (1) - Speed ​​( vmax = 5):

Step (2) - Brakes:

Step (3) - dawdling ( ρ = 1 /3):

Step ( 4) - Drive ( = configuration at time t 1):

Properties of the model

• With the model it has been possible to explain the occurrence of the " jams out of nothing" as a result of dawdling and overreacting when braking.
• For a more realistic simulation of the storage structure on the highways junk probability must be greater than set in the other cases ( VDR model - Velocity Dependent Randomization ) when starting up.
• Other approaches to reality is achieved by considering the effect of brake lights.
• For a maximum speed one instead of five and flea probability p = 0, the Nagel-Schreckenberg cellular automata model corresponds to the 184 Stephen Wolfram and the deterministic TASEP with parallel update.
• The model is minimal, that is not an element of the definition may be omitted without that one immediately loses essential characteristics of the traffic.
• Due to its simplicity, it has an added educational value ( eg for school computer science classes ).
• A simulation of many millions of vehicles is possible with the help of parallel working computers and has already been implemented (see applications).

Illustration

In the pictures below, a 7.5 km long been divided into 1000 cells ring road is ready, take the vehicles from left to right. At the bottom of the starting condition of the road is shown second by second line by line at the top. A green dot represents a vehicle that has recently moved with the velocity 5, a red dot means a stationary vehicle. Accordingly, in between are lying colors for speeds of one to five cells per round.

In double density (300 vehicles) and p = 0.15, the number of traffic jams increased dramatically.

The VDR model the structure of the congestion changes. Here are 300 cars in the ring at p = 0.15 ( for v > 0 for v = 0 p > 0.15 )

This graphic is an enlarged image size of the above illustration with the junk parameter p = 0.15. Colored squares indicate one vehicle with its corresponding speed. Each row represents the state of occupation of the same street. The state of occupation of each on one line ( the road), indicates the state in the next second.

Fundamental diagram

As a fundamental diagram is defined as the application of the flow over the density. Flow is the number of vehicles that pass a certain mark per round (which can be on a single track road up to one ). Density is the percentage of covered vehicles by the road surface ( ergo also more than one). This plot (flux as a y -coordinate density as the x coordinate ) is characteristic of a particular choice of parameters of a particular model that they are called fundamental diagram.

The broken lines indicate how unstable the flow of traffic at these locations. In reality, there is even a hysteresis effect: If the traffic is too slow, you can still reached at a certain density a fairly high flow. Eventually this breaks together by over-reacting a driver when braking and drops to a significantly lower value. The density of traffic now has to drop significantly, to get back on the rising branch of the fundamental diagram. Only then an increase in the density may again lead to an increased flow. This effect also has been observed in simulations.

Another point in which the real fundamental diagram differs from the fundamental diagrams of all discussed here versions of the Nash - model is that the rising branch of the fundamental diagram in reality has a curvature. The reason for this is that, in reality, the maximum speed of the vehicle varies. The curvature begins when the first vehicles have reached their limit. To implement this in the model, the Nash model has been extended to multi-lane traffic rules and overtaking. Without these rules, different maximum principle would always lead to congestion, as fast vehicles would ascend to slow, but could not overtake.

In the deterministic case, the maximum is always at a density. For the laws of motion for vehicles are identical to those of gaps ( in the other direction ). Therefore, the maximum is there readily apparent at the location where the vehicle can move as freely gaps ().

Applications

The Nash model was further developed by Kai Nagel in the United States for parallel computers and marketed under the name ' TRANSIMS '. It is interesting that the algorithm is not allowed to simply parallelize on vector computers and therefore Beowulf cluster are used. Meanwhile, TRANSIMS has been applied to simulate the entire Swiss traffic in real time, with about 10 million vehicles.

In Germany is the model - with extensions - the basis of OLSIM traffic forecast for the freeway traffic in North Rhine -Westphalia, which is on the website listed below to the public.