„Nagel-Schreckenberg-Modell“ – Versionsunterschied

Das Nagel-Schreckenberg-Modell (kurz NaSch-Modell) ist ein theoretisches Modell zur Simulation des Straßenverkehrs. Es wurde 1992 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 Zeitspanne). Das Modell erklärte das erste Mal den Stau aus dem Nichts als Folge der Nicht-Einhaltung des Sicherheitsabstandes. Es berührt die Bereiche der Chaosforschung und der Spieltheorie.

Animiertes Nagel-Schreckenberg-Modell mit 15 Autos auf einer Straße der Länge 50. Die Trödelwahrscheinlichkeit liegt bei 10 %. Obwohl keine Hindernisse vorliegen, bilden sich immer wieder kurze Phantomstaus.

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 pro Runde), 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 Tempomaten 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.

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 (vmax = 5):
5					5				3				2		2		---→
Schritt (2) – Bremsen:
4					3				3				1		2		---→
Schritt (3) – Trödeln (p = 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 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 vier 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 $\varrho ={\frac {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 ($\varrho =0,5=1\cdot {\frac {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

• Kai Nagel, Michael Schreckenberg: A cellular automaton model for freeway traffic. In: Journal de Physique I. Band 2, Nr. 12, 1992, S. 2221–2229, doi:10.1051/jp1:1992277. 
• Kai Nagel: High-speed microsimulations of traffic flow. Dissertation, 1995.
• Kai Nagel: Particle hopping models and traffic flow theory. In: Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics. Band 53, Nr. 5, 1996, S. 4655–4672, doi:10.1103/physreve.53.4655. 
• M. Rickert, Kai Nagel, Michael Schreckenberg, A. Latour: Two lane traffic simulations using cellular automata. In: Physica A Statistical Mechanics and its Applications. Band 231, Nr. 4, 1996, S. 534–550, doi:10.1016/0378-4371(95)00442-4. 
• Andreas Schadschneider, Michael Schreckenberg: Car-oriented mean-field theory for traffic flow models. In: Journal of Physics A Mathematical and General. Band 30, Nr. 4, 1997, S. L69–L75, doi:10.1088/0305-4470/30/4/005. 
• Kai Nagel, Dietrich E. Wolf, Péter Wagner, P. Simon: Two-lane traffic rules for cellular automata: A systematic approach. In: Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics. Band 58, Nr. 2, 1998, S. 1425–1437, doi:10.1103/physreve.58.1425. 
• Andreas Schadschneider, Michael Schreckenberg: Garden of Eden states in traffic models. In: Journal of Physics A Mathematical and General. Band 31, Nr. 11, 1998, S. L225–L231, doi:10.1088/0305-4470/31/11/003. 
• Debashish Chowdhury, Abhay N. Pasupathy, Shishir Sinha: Distributions of time- and distance-headways in the Nagel-Schreckenberg model of vehicular traffic: effects of hindrances. In: The European Physical Journal B. Band 5, Nr. 3, 1998, S. 781–786, doi:10.1007/s100510050502. 
• Robert Barlović, Ludger Santen, Andreas Schadschneider, Michael Schreckenberg: Metastable states in cellular automata for traffic flow. In: The European Physical Journal B. Band 5, Nr. 3, 1998, S. 793–800, doi:10.1007/s100510050504. 
• Andreas Schadschneider: Statistical physics of traffic flow. In: Physica A Statistical Mechanics and its Applications. Band 285, Nr. 1-2, 2000, S. 101–120, doi:10.1016/s0378-4371(00)00274-0. 
• Carsten Burstedde, Kai Klauck, Andreas Schadschneider, J. Zittartz: Simulation of pedestrian dynamics using a two-dimensional cellular automaton. In: Physica A Statistical Mechanics and its Applications. Band 295, Nr. 3-4, 2001, S. 507–525, doi:10.1016/s0378-4371(01)00141-8. 
• Robert Barlović, Andreas Schadschneider, Michael Schreckenberg: Random walk theory of jamming in a cellular automaton model for traffic flow. In: Physica A Statistical Mechanics and its Applications. Band 294, Nr. 3-4, 2001, S. 525–538, doi:10.1016/s0378-4371(01)00111-x. 
• Wolfgang Knospe, Ludger Santen, Andreas Schadschneider, Michael Schreckenberg: A realistic two-lane traffic model for highway traffic. In: Journal of Physics A Mathematical and General. Band 35, Nr. 15, 2002, S. 3369–3388, doi:10.1088/0305-4470/35/15/302. 
• Bryan Raney, Andreas Voellmy, Nurhan Cetin, Milenko Vrtic, Kai Nagel: Towards a Microscopic Traffic Simulation of All of Switzerland. In: Lecture notes in computer science. 2002, S. 371–380, doi:10.1007/3-540-46043-8_37. 
• Andreas Pottmeier et al.: Localized Defects in a Cellular Automaton Model for Traffic Flow with Phase Separation. In: Springer eBooks. 2003, S. 109–114, doi:10.1007/978-3-662-10583-2_10. 
• Andreas Pottmeier, Robert Barlović, Wolfgang Knospe, Andreas Schadschneider, Michael Schreckenberg: Localized defects in a cellular automaton model for traffic flow with phase separation. In: Physica A Statistical Mechanics and its Applications. Band 308, Nr. 1-4, 2002, S. 471–482, doi:10.1016/s0378-4371(02)00547-2. 
• Hyun Keun Lee, Robert Barlović, Michael Schreckenberg, Doochul Kim: Mechanical Restriction versus Human Overreaction Triggering Congested Traffic States. In: Physical Review Letters. Band 92, Nr. 23, 2004, doi:10.1103/physrevlett.92.238702. 

Weblinks

• Die Originalarbeit: Kai Nagel, Michael Schreckenberg: A cellular automaton model for freeway traffic. (PDF; 673 kB) In: J. Phys. I France, 2, 1992, S. 2221–2229
• 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
• Simulation mit Nagel-Schreckenberg-Modell (Applet)