The Nagel-Schreckenberg Model

Kai Nagel and Michael Schreckenberg published their cellular automaton model of single-lane highway traffic in Journal de Physique I in 1992. The model is remarkable for its economy: four rules, two parameters, integer arithmetic, and no differential equations. It reproduces phantom jams, the fundamental diagram, hysteresis, and the free-flow to congested phase transition. It can simulate millions of vehicles on a standard computer in seconds. The model demonstrated that the macroscopic phenomena of traffic flow are consequences of microscopic interaction rules, not of road geometry or aggregate demand.

The Four Rules

The road is a one-dimensional lattice of cells, each 7.5 meters long (approximately one car length). Each cell is either empty or occupied by one vehicle. Each vehicle carries an integer velocity from 0 to v_max (typically v_max = 5, corresponding to a maximum speed of 5 cells per time step, or 135 km/h at one-second time steps).

At each time step, four rules apply to every vehicle simultaneously:

Rule 1: Acceleration. If the vehicle’s velocity v is less than v_max, increase v by 1. Drivers accelerate toward the speed limit when conditions permit.

Rule 2: Braking. Let d be the number of empty cells between the vehicle and the vehicle ahead. If v > d, set v = d. No vehicle drives faster than its stopping distance allows. This prevents collisions.

Rule 3: Randomization. With probability p, decrease v by 1 (to a minimum of 0). This step represents the imperfection of real drivers: fluctuations in reaction time, momentary inattention, hesitation when accelerating, slightly late braking.

Rule 4: Motion. Advance the vehicle by v cells.

Rules 1 through 3 are evaluated based on the current configuration (before any vehicle moves). Rule 4 then moves all vehicles simultaneously. This is synchronous update: the system advances one time step at once, like a cellular automaton.

The complete model is specified by v_max, the randomization probability p, and the initial configuration. Nothing else is needed.

The Role of Randomization

The randomization step (Rule 3) is what separates the NaSch model from a trivial deterministic system. Its role is foundational, not cosmetic.

Without randomization (p = 0): The model is deterministic. Starting from any initial configuration, vehicles accelerate to v_max and maintain uniform spacing. No spontaneous jams form at any density below full occupation. The fundamental diagram is a straight line up to the critical density, then drops. There is no hysteresis and no metastability. This version is analytically solvable and physically unrealistic.

With randomization (p > 0): The behavior changes qualitatively. At low density, vehicles are far apart, and a random deceleration event is absorbed by the large following gap. The system remains in free flow. At high density, gaps are small. A random deceleration event reduces a vehicle’s speed, closing the gap behind it. The following vehicle, now too close, must brake (Rule 2), potentially more sharply than the original deceleration. The perturbation amplifies as it propagates backward through the traffic chain. Above a critical density, this amplification creates a self-sustaining stop-and-go wave --- a phantom jam.

The parameter p controls the noise level and therefore the onset of congestion. Higher p means more frequent random decelerations, which means lower critical density (jams form at lower traffic volumes) and more severe congestion. The empirically relevant range is p = 0.1 to 0.5. At p = 1 (every vehicle decelerates at every step), the system is maximally congested.

The physical interpretation of p: it is the fraction of time steps at which a driver fails to accelerate optimally or brakes unnecessarily. Real drivers are not perfect automata. They hesitate, they are distracted, they react slightly late. The randomization step captures the aggregate effect of these imperfections without modeling any individual cognitive process. This is the NaSch model’s core insight: the specific cause of each imperfection does not matter; what matters is that imperfections exist and that their frequency is parameterized by p.

The Fundamental Diagram

The fundamental diagram plots traffic flow q (vehicles per unit time passing a fixed point) against density rho (vehicles per unit length of road). It is the single most important empirical characterization of traffic behavior.

The NaSch model’s fundamental diagram has the correct qualitative shape:

  • At low density: flow increases linearly with density. Vehicles travel at v_max, and flow equals rho * v_max.
  • At intermediate density: flow reaches a maximum at a critical density rho_c. This is the road’s capacity.
  • At high density: flow decreases. Vehicles are forced to travel below v_max because of insufficient gaps, and the average speed drops faster than density increases.

The NaSch model also reproduces the hysteresis observed in real traffic data. When density increases slowly through the critical point, the system transitions from free flow to congested flow. When density then decreases, the transition back to free flow occurs at a lower density than the original transition. The system has memory: the congested state persists below the critical density, and a perturbation is required to restore free flow. This hysteresis is a signature of a first-order phase transition with metastability.

The quantitative match between the NaSch fundamental diagram and empirical data is approximate but surprisingly good for a model with two parameters. The shape, the location of the maximum, and the hysteresis loop all match real highway data qualitatively. Quantitative discrepancies arise from the model’s simplifications: single-lane traffic (real highways are multi-lane), identical vehicles (real traffic is a mix), and integer velocities (real speeds are continuous).

Comparison with Continuous Models

The NaSch model is not the only traffic model. Several alternatives operate in continuous space and time.

The Lighthill-Whitham-Richards (LWR) model (1955, 1956). A first-order partial differential equation that treats traffic as a compressible fluid. The flow-density relationship (fundamental diagram) is the equation of state. The LWR model predicts kinematic waves (including backward-propagating jams) and reproduces the fundamental diagram by construction. It does not produce spontaneous jam formation --- jams must be seeded by an initial perturbation or a boundary condition. The LWR model is analytically tractable and useful for theoretical analysis but does not capture the stochastic fluctuations that make phantom jams spontaneous.

The Optimal Velocity Model (Bando et al., 1995). A system of ordinary differential equations. Each driver has a desired velocity that depends on the gap to the lead vehicle, and accelerates or decelerates toward that desired velocity. The model produces spontaneous jam formation when the sensitivity parameter exceeds a critical value. It is continuous in space, time, and velocity, giving smoother trajectories than the NaSch model but requiring more computational effort per vehicle.

The Intelligent Driver Model (IDM; Treiber, Hennecke, and Helbing, 2000). A car-following model with realistic acceleration and deceleration behavior, including a comfort deceleration parameter. The IDM is calibrated to reproduce individual vehicle trajectories and is used in traffic engineering software. It produces phantom jams when density exceeds a critical value.

What the NaSch model gains: Computational speed. The integer arithmetic and synchronous update allow simulation of millions of vehicles in real time on standard hardware. This makes it feasible to simulate entire highway networks, which continuous models cannot do at the same scale. The discrete state space also makes the model analytically accessible via techniques from statistical mechanics.

What it loses: Continuous speed dynamics. Real vehicles do not jump between integer velocities. The NaSch model’s discrete velocities mean that individual vehicle trajectories are jagged, and the fine structure of acceleration and deceleration events is not captured. For applications requiring detailed individual trajectories (autonomous vehicle control, microsimulation of intersections), the IDM or similar continuous models are more appropriate.

Daganzo (2006) proved that in the deterministic limit, the NaSch model is mathematically equivalent to the LWR model: the cellular automaton’s evolution converges to the kinematic wave equation as the cell size goes to zero. The stochastic NaSch model (p > 0) adds fluctuations on top of this deterministic baseline, producing spontaneous jam formation that the LWR model cannot.

Further Reading