Zelluläre Automaten zur Verkehrssimulation

Rahmenbedingungen

Dazu wird eine Straße in einzelne Abschnitte einer festen Länge (zum Beispiel 7,50 m, was der Länge eines Autos plus einem Mindestabstand zu anderen Autos entspricht) aufgeteilt. Jeder solche Abschnitt ist eine Zelle. In unserem Modell können diese Abschnitte (oder Zellen) zu einem festen Zeitpunkt entweder genau ein Auto mit einer bestimmten momentanen Geschwindigkeit enthalten, oder sie sind leer. Jedes Auto hat eine individuelle Eigengeschwindigkeit, kann bei freier Strecke beschleunigen und hält bestimmte einfache Abstandsregeln zu dem vorausfahrenden Fahrzeug ein. (Mathematisch gesehen entsprechen diese Regeln bereits einem Algorithmus!)

Wann kommt es zum Stau?

Fahren jetzt alle Autos mit exakt der gleichen Geschwindigkeit und ist der Verkehr so dünn, dass genügend Abstand zu den jeweils vorausfahrenden Fahrzeugen besteht, entsteht kein Stau. Dies ändert sich jedoch, wenn man individuelle Abweichungen der Geschwindigkeiten zulässt, zum Beispiel durch die Einführung eines (zufallsgesteuerten) "Trödelfaktors" oder durch "Drängler", die beim Abbremsen des vorausfahrenden Fahrzeugs schärfer bremsen müssen, was sich zu einer Kettenreaktion mit anschließendem Stau aufschaukeln kann.

Einspurige Ringstraße

Wir betrachten eine einfache einspurige Ringstraße, auf der sich Autos nur in eine Richtung fortbewegen. Überholvorgänge und Gegenverkehr sind in dem Modell nicht enthalten. Diese Straße teilen wir in Zellen von 7,50 m Länge ein. Autos können sich in einem Zeitschritt nur um eine ganze Zahl von Zellen vorwärts bewegen. Geht man von einer Zeitschrittdauer von einer Sekunde aus, so entspricht eine Vorwärtsbewegung von einer Zelle pro Zeitschritt einer Geschwindigkeit von

7,5 m / 1s = 27 km/h.

Einer Vorwärtsbewegung von 5 Zellen pro Sekunde entspricht dann einer Geschwindigkeit von 5 · 27 km/h = 135 km/h. Da dies in etwa der Richtgeschwindigkeit auf den deutschen Autobahnen entspricht, werden wir dies als Höchstgeschwindigkeit vmax ansetzen. Die Autos können sich also in jedem Zeitschritt um 0 bis 5 Zellen vorwärts bewegen. Ferner muss Kollisionsfreiheit garantiert sein, das heißt auf einer Zelle darf sich immer nur höchstens ein Fahrzeug befinden.

Ablauf in drei Schritten

Das einfachste Modell, das wir hier betrachten wollen, besteht in jedem Zeitschritt aus drei Teilschritten. In den ersten beiden Teilschritten wird die neue Geschwindigkeit des Fahrzeugs so ermittelt, dass Kollisionen verhindert werden. Erst im dritten Teilschritt bewegen sich die Fahrzeuge vorwärts:

1. Beschleunigen

Jedes Fahrzeug erhöht seine Geschwindigkeit um 1 Zelle pro Zeiteinheit, bis es die Maximalgeschwindigkeit erreicht hat.

2. Bremsen

Jedes Fahrzeug prüft, ob es mit der gerade berechneten Geschwindigkeit auf ein anderes Fahrzeug auffahren oder dieses überholen würde. Ist dies der Fall, so reduziert es seine Geschwindigkeit sofort so weit, dass eine Kollision vermieden wird.

3. Bewegen

Jedes Fahrzeug bewegt sich einen Zeitschritt mit der aktuellen Geschwindigkeit vorwärts.

Dies können wir in einem einfachen Algorithmus präzisieren. Wir haben i = 1,...,n Fahrzeuge. Jedes Fahrzeug hat eine individuelle Eigengeschwindigkeit v_i. Die Höchstgeschwindigkeit ist v_max = 5. Jeder der folgenden drei Teilschritte wird dann gleichzeitig für alle Fahrzeuge durchgeführt:

1. Beschleunigen

v_i= min {v_i+1,v_max}

2. Bremsen

Falls v_i > d(i, i+1), so reduziere v_i auf v_i= d(i, i+1). Hierbei ist d(i, i+1) die Anzahl der leeren Zellen zwischen Fahrzeug i und Fahrzeug i + 1.

3. Bewegen

Jedes Fahrzeug i bewegt sich v_i Zellen vorwärts.

Das bisher dargestellte Modell kann bei einem höheren Verkehrsaufkommen Staus erzeugen. Auch das gleichzeitige Auftreten von Teilstrecken, auf denen mit hohen Geschwindigkeiten gefahren werden kann, und Teilstrecken, auf denen ein Stau entstanden ist, werden vom Modell dargestellt. Das völlig stationäre Verkehrsverhalten (Staus bewegen sich völlig gleichmäßig entgegen der Fahrtrichtung nach hinten fort) und das völlig gleichförmige Verhalten aller Fahrzeuge sind jedoch weit von der Realität entfernt. Herzu wird das Modell im nächsten Schritt noch erweitert.