Nagel-Schreckenberg-Modell

Das Nagel-Schreckenberg-Modell (kurz NaSch-Modell) ist ein theoretisches Modell zur Simulation des Straßenverkehrs. Es wurde Anfang der 1990er Jahre von den Festkörperphysikern Kai Nagel und Michael Schreckenberg formuliert. Mit Hilfe elementarer Regeln liefert es Voraussagen zum Straßenverkehr, insbesondere zur Verkehrsdichte (Fahrzeuge je Streckenabschnitt) und zum Verkehrsfluss (vorbeifahrende Fahrzeuge je Zeiteinheit). Das Modell erklärte das erste Mal den Stau aus dem Nichts als Folge von Überreaktionen beim Bremsen der vorausfahrenden Fahrzeuge. Es berührt die Bereiche der Chaosforschung und der Spieltheorie.

Struktur des Modells

Im Modell setzt sich die Straße aus einzelnen Abschnitten, genannt Zellen zusammen. Die Sicht ist binär: eine Zelle ist leer oder wird von genau einem Fahrzeug besetzt, also überschreitet ein Fahrzeug auch keine Zellengrenzen. Auch die Zeit ist nach demselben Schema, genannt Runden, zerlegt. In jeder Runde wird zunächst gleichzeitig für alle Fahrzeuge festgelegt, wohin sie sich bewegen werden, dann erst werden die Fahrzeuge bewegt. Diese Struktur entspricht einem Zellularautomaten. Dem Modell liegt die Annahme des schlechtestmöglichen Verkehrs zugrunde, also der ständigen Angst vor dem Stau, da Überholen und Unfälle ausgeschlossen sind.

Rechnerisches Beispiel

Die Länge einer Zelle soll dem Platz entsprechen, den ein im Stau stehendes Fahrzeug benötigt. Dies ist die Summe aus der durchschnittlichen Länge eines Fahrzeugs und der Lücke zwischen zwei Fahrzeugen. Üblicherweise wird hierfür der Wert 7,5 Meter angenommen. Als Dauer einer Runde wird die typische Reaktionszeit eines Verkehrsteilnehmers von einer Sekunde gesetzt. Damit ergibt sich eine Geschwindigkeit von 7,5 Metern pro Sekunde (27 km/h), wenn ein Fahrzeug in einer Runde eine Zelle vorrückt. Als Höchstgeschwindigkeit nimmt man dann zumeist fünf Zellen pro Runde (also 135 km/h) an.

Ablauf einer Runde – die „Update-Regeln“

Pro Runde werden für alle Fahrzeuge folgende vier Schritte durchgeführt:

1. Falls die Maximalgeschwindigkeit eines Fahrzeuges noch nicht erreicht ist, wird seine Geschwindigkeit um eins erhöht. (Beschleunigen)
2. Falls die Lücke (in Zellen) zum nächsten Fahrzeug kleiner ist als die Geschwindigkeit (in Zellen), wird die Geschwindigkeit des Fahrzeugs auf die Größe der Lücke reduziert. (Kollisionsfreiheit)
3. Die Geschwindigkeit eines Fahrzeugs wird mit der Wahrscheinlichkeit p um eins reduziert, sofern es nicht schon steht. (Trödeln)
4. Alle Fahrzeuge werden ihrer momentanen Geschwindigkeit entsprechend vorwärts bewegt.

Mit dem dritten Schritt werden drei Phänomene gleichzeitig modelliert:

1. Ein Fahrzeug, das seine Maximalgeschwindigkeit noch nicht erreicht und daher zuvor beschleunigt hat, und das nicht abbremsen musste, weil es zu nah auf den Vordermann aufgefahren ist, kann durch das Trödeln seine Beschleunigung rückgängig machen. Der Fahrer nutzt die Möglichkeit zum Beschleunigen nicht aus.
2. Ein Fahrzeug, das bereits Maximalgeschwindigkeit hat, kann unter diese zurückfallen. Es kommt zu Fluktuationen im oberen Geschwindigkeitsbereich. Da in den USA ein großer Teil der Fahrzeuge einen Tempomat besitzt, bildet man dortiges Fahrverhalten besser ab, wenn man auf das Trödeln bei Maximalgeschwindigkeit verzichtet.
3. Ein Fahrzeug, das wegen eines zu geringen Abstandes zum Vordermann bereits bremsen musste, kann seine Geschwindigkeit durch das Trödeln noch ein weiteres Mal reduzieren. Der Fahrer überreagiert beim Bremsen also auf den langsamen Vordermann. Dieses Überreagieren wurde als Ursache für Staus aus dem Nichts identifiziert.

Beispiel für den Ablauf einer Runde

Symbolik	Bedeutung
1	Ein Fahrzeug besitzt die Geschwindigkeit 1 (= 1*27 km/h)
3	Ein Fahrzeug hat eben auf die Geschwindigkeit 3 (= 81 km/h) beschleunigt oder gebremst (bzw. getrödelt).
2	Ein Fahrzeug ist mit Geschwindigkeit 2 gefahren (also zwei Felder vorgerückt)

Konfiguration zur Zeit t:

5

4

2

1

1

---→

Schritt (1) – Beschleunigen (v_max = 5):

5

5

3

2

2

---→

Schritt (2) – Bremsen:

4

3

3

1

2

---→

Schritt (3) – Trödeln (ρ = 1/3):

4

3

3

0

1

---→

Schritt (4) – Fahren (= Konfiguration zur Zeit t + 1):

4

3

3

0

1

---→

Eigenschaften des Modells

• Mit dem Modell ist es gelungen, das Auftreten des „Staus aus dem Nichts“ als Folge von Trödeln und Überreagieren beim Bremsen zu erklären.
• Für eine realistischere Nachbildung der Staustruktur auf den Autobahnen muss die Trödelwahrscheinlichkeit beim Anfahren größer als in den anderen Fällen gesetzt werden (VDR-Modell – Velocity Dependent Randomization).
• Weitere Annäherungen an die Realität erreicht man durch Berücksichtigen des Effektes von Bremslichtern.
• Für eine Maximalgeschwindigkeit eins statt fünf und Trödelwahrscheinlichkeit p=0 entspricht das Nagel-Schreckenberg-Modell dem Zellularautomaten 184^[1] Stephen Wolframs bzw. dem deterministischen TASEP mit parallelem Update.
• Das Modell ist minimal. D. h. kein Element der Definition darf weggelassen werden, ohne dass man sofort essentielle Eigenschaften des Verkehrs verliert.
• Durch seine Einfachheit hat es einen zusätzlichen didaktischen Nutzen (z. B. für den schulischen Informatikunterricht).
• Eine Simulation von vielen Millionen Fahrzeugen ist mit Hilfe von parallel arbeitenden Computern möglich und wurde bereits realisiert (s. Anwendungen).

Illustration

In den folgenden Bildern ist eine 7,5 km lange in 1000 Zellen eingeteilte Ringstraße abgebildet, auf der Fahrzeuge von links nach rechts fahren. Am unteren Bildrand beginnend wird der Zustand der Straße Sekunde um Sekunde Zeile um Zeile nach oben hin gezeigt. Ein grüner Punkt steht für ein Fahrzeug, das sich zuletzt mit der Geschwindigkeit 5 bewegt hat, ein roter Punkt bedeutet ein stehendes Fahrzeug. Entsprechend stehen dazwischen liegende Farben für Geschwindigkeiten von einer bis fünf Zellen pro Runde.

• 

  150 von 1000 Straßenzellen sind von einem Fahrzeug belegt. Der Trödelparameter p ist p=0,0. Man erkennt, wie sich – zu Beginn zufällig bestehende – Staus auflösen.

• 

  Bei doppelter Dichte (300 Fahrzeuge) und p=0,15 erhöht sich die Zahl der Staus drastisch.

• 

  Im VDR-Modell ändert sich die Struktur der Staus. Auch hier sind 300 Fahrzeuge im Ring bei p=0,15 (für v>0; für v=0 ist p>0,15)

• 

  Diese Grafik ist ein vergrößerter Bildausschnitt der obigen Illustration mit dem Trödelparameter p=0,15. Farbige Quadrate kennzeichnen jeweils ein Fahrzeug mit seiner entsprechenden Geschwindigkeit. Jede Zeile repräsentiert den Besetzungszustand derselben Straße. Der Besetzungszustand jeweils über einer Zeile (der Straße), zeigt den Zustand in der darauffolgenden Sekunde an.

Fundamentaldiagramm

Als Fundamentaldiagramm bezeichnet man die Auftragung des Flusses über der Dichte. Fluss ist die Anzahl Fahrzeuge, die pro Runde eine bestimmte Markierung passieren (das kann auf einer einspurigen Straße maximal eines sein). Dichte ist der Anteil der durch Fahrzeuge überdeckten Fläche der Straße (ergo auch maximal eins). Diese Auftragung (Fluss als y-Koordinate, Dichte als x-Koordinate) ist so charakteristisch für eine bestimmte Parameterwahl eines bestimmten Modells, dass man sie Fundamentaldiagramm nennt.

Fundamentaldiagramme des NaSch-Modelles

Farbe	Modell	Trödelparameter p	Maximalgeschwindigkeit v
	deterministisch	0,0	1
	probabilistisch	0,15	1
	VDR	0,15	1
	deterministisch	0,0	5
	probabilistisch	0,15	5
	VDR	0,15	5

Die durchbrochenen Linien zeigen an, wie instabil der Verkehrsfluss an diesen Stellen ist. In der Realität gibt es sogar einen Hystereseeffekt: Nimmt der Verkehr langsam zu, erreicht man bei einer bestimmten Dichte noch einen recht hohen Fluss. Irgendwann bricht dieser durch Überreagieren eines Fahrers beim Bremsen zusammen und fällt auf einen deutlich niedrigeren Wert ab. Die Dichte des Verkehrs muss nun deutlich abnehmen, um wieder auf den ansteigenden Ast des Fundamentaldiagramms zu gelangen. Erst dann kann eine Erhöhung der Dichte wieder zu einem erhöhten Fluss führen. Auch dieser Effekt wurde bereits in Simulationen beobachtet.

Ein weiterer Punkt, in dem sich das reale Fundamentaldiagramm von den Fundamentaldiagrammen aller hier diskutierten Versionen des NaSch-Modelles unterscheidet, ist, dass der ansteigende Ast des Fundamentaldiagramms in der Realität eine Krümmung aufweist. Der Grund hierfür ist, dass in der Realität die Höchstgeschwindigkeit der Fahrzeuge unterschiedlich ist. Die Krümmung beginnt, wenn die ersten Fahrzeuge ihre Höchstgeschwindigkeit erreicht haben. Um dies im Modell umzusetzen, wurde das NaSch-Modell um Regeln für mehrspurigen Verkehr und Überholvorgänge erweitert. Ohne diese Regeln würden unterschiedliche Höchstgeschwindigkeiten prinzipiell immer zu Staus führen, da schnelle Fahrzeuge auf langsame auffahren würden, aber nicht überholen könnten.

Im deterministischen Fall ist das Maximum immer bei einer Dichte=1/(1+v). Für v=1 sind die Bewegungsregeln für Fahrzeuge identisch mit denen für Lücken (in die andere Richtung). Daher ist das Maximum dort leicht ersichtlich an der Stelle, wo sich Fahrzeuge wie Lücken ungehindert fortbewegen können (Dichte=0,5=1/(1+1)).

Anwendungen

Das NaSch-Modell wurde von Kai Nagel in den Vereinigten Staaten für Parallelrechner weiterentwickelt und unter dem Namen 'Transims' vermarktet. Interessant ist, dass sich der Algorithmus nicht einfach auf Vektorrechnern parallelisieren ließ und daher Beowulf-Cluster zum Einsatz kommen. Inzwischen wurde Transims angewandt, um den gesamten Schweizer Verkehr in Echtzeit zu simulieren, mit etwa 10 Millionen Fahrzeugen.

In Deutschland ist das Modell – mit Erweiterungen – die Grundlage der OLSIM-Verkehrsprognose für den Autobahnverkehr in Nordrhein-Westfalen, welche auf der unten angegebenen Internetseite öffentlich zugänglich ist.

Siehe auch

• Verkehrsphysik

Literatur

• K. Nagel and M. Schreckenberg. A cellular automaton model for freeway traffic, J. Phys. I France 2 2221–2229 (1992).
• K. Nagel. High-speed microsimulations of traffic flow. Dissertation (1995).
• K. Nagel. Particle hopping models and traffic flow theory, Physical Review E 53 4655–4672 (1996).
• M. Rickert, K. Nagel, M. Schreckenberg, and A. Latour. Two Lane Traffic Simulations using Cellular Automats, Physica A 231 4 534-550 (1996).
• A. Schadschneider and M. Schreckenberg. Car-oriented mean-field theory for traffic flow models, J. Phys. A: Math. Gen. 30 L69-L75 (1997).
• K. Nagel, D.E. Wolf, P. Wagner, and P. Simon. Two-lane traffic rules for cellular automata: A systematic approach, Physical Review E 58 1425–1437 (1998).
• A. Schadschneider and M. Schreckenberg. Garden of Eden states in traffic models, J. Phys. A: Math. Gen. 31, L225–L231 (1998).
• D. Chowdhury, A. Pasupathy, and S. Sinha. Distributions of time- and distance-headways in the Nagel-Schreckenberg model of vehicular traffic: effects of hindrances, European Physical Journal B 5 3 781-786 (1998).
• R. Barlovic, L. Santen, A. Schadschneider, and M. Schreckenberg. Metastable states in cellular automata for traffic flow, European Physical Journal B 5 3 793-800 (1998).
• A. Schadschneider. Statistical Physics of Traffic Flow Models, Physica A 285 1-2 101-120 (2000).
• C. Burstedde, K. Klauck, A. Schadschneider, and J. Zittartz. Simulation of pedestrian dynamics using a two-dimensional cellular automaton, Physica A 295 3-4 507-525 (2001).
• R. Barlovic, A. Schadschneider, and M. Schreckenberg. Random walk theory of jamming in a cellular automaton model for traffic flow, Physica A 294 3-4 525-538 (2001).
• W. Knospe, L. Santen, A. Schadschneider, and M. Schreckenberg. A realistic two-lane traffic model for highway traffic, Journal of Physics A 35 3369-3388 (2002).
• B. Raney, A. Voellmy, N. Cetin, M. Vrtic, and K. Nagel. Towards a Microscopic Traffic Simulation of All of Switzerland, Computational Science — ICCS 2002 371-380 (2002).
• A. Pottmeier, R. Barlovic, W. Knospe, A. Schadschneider, and M. Schreckenberg. Localized defects in a cellular automaton model for traffic flow with phase separation, Physica A 308 1-4 471-482 (2002).
• H.K. Lee, R. Barlovic, M. Schreckenberg, and D. Kim. Mechanical Restriction versus Human Overreaction Triggering Congested Traffic States, Phys. Rev. Lett. 92, 238702 (2004).

Weblinks

• Die Originalarbeit: Kai Nagel und Michael Schreckenberg: „A cellular automaton model for freeway traffic“, J. Phys. I France 2 (1992) 2221–2229 (PDF, 1038 KB)
• Die OLSIM
• Verkehrssystemplanung und Verkehrstelematik der TU Berlin
• Forschung in Berlin (engl.) mit Artikel zu All-of-Switzerland
• Physik von Transport und Verkehr der Universität Duisburg-Essen
• NaSchSaver – ein einfacher Bildschirmschoner für Windows basierend auf dem NaSch-Modell
• Simulation mit Nagel-Schreckenberg-Modell (Applet)

Einzelnachweise

1. ↑ Vergl. Artikel in der engl. Wikipedia

Dieser Artikel wurde am 17. September 2006 in dieser Version in die Liste der lesenswerten Artikel aufgenommen.