Einleitung

Wer zum Beispiel regelmäßig mit dem Auto zur Arbeit pendeln muss, der hört das Wort “Stau” gar nicht gerne. Oft lässt sich zäh fließender Verkehr zur Rush Hour nicht vermeiden, aber manchmal staut es sich auch ohne ersichtlichen Grund.

Auf einer Strecke, die ich öfter fahre, steht etwa ein Blitzer bei einer Geschwindigkeitsbegrenzung von 80km/h. Die wird nur irgendwie nie erreicht, meistens geht es so mit 60km/h vorwärts. Erst, wenn man am Blitzer vorbei ist, geht es plötzlich wieder deutlich schneller vorwärts. Ein anderes beliebtes Phänomen sind Unfälle auf der anderen Straßenseite, die die eigene Spur nicht beeinflussen sollten und doch stockt plötzlich der Verkehr. Es entsteht ein sogenannter “Stau aus dem Nichts”, welchen man mit dem Nagel-Schreckenberg Modell mit nur wenigen Regeln modellieren kann. Beschrieben haben die beiden ihr Modell 1992 in dem Paper A cellular automaton model for freeway traffic.

Inhaltsverzeichnis

1. Das Modell
2. Implementierung
   1. Initialisierungs
   2. Beschleunigung
   3. Bremsen
   4. Trödeln
   5. Bewegung
3. Ausführen des Modells
4. Fazit

Das Modell

Um eine Straße darzustellen, wird ein eindimensionales Array von Zahlen verwendet. Jeder Eintrag stellt einen Streckenabschnitt dar, der entweder ein Auto enthält oder leer ist. Befindet sich ein Auto aktuell auf einem Streckenabschnitt, setzen wir den Wert auf die Geschwindigkeit des Autos. Andernfalls werden wir als Platzhalter eine -1 in das Feld schreiben, rückwärts fahren darf man auf einer Autobahn ja eh nicht. Grundsätzlich gibt die Geschwindigkeit an, um wie viele Felder ein Auto pro Runde vorrückt. Als Höchstgeschwindigkeit wählen wir deshalb 5.

Als nächstes stellen wir vier Regeln auf, die jede Runde auf die Autos im Array angewendet werden, um ihre Position bei fortlaufender Zeit zu berechnen:

1. Beschleunigung: Jedes Auto, dass die Maximalgeschwindigkeit noch nicht erreicht hat, erhöht sie um 1.
2. Bremsen: Um den Sicherheitsabstand einzuhalten, verringern alle Autos ihre Geschwindigkeit auf die Anzahl an freien Feldern vor ihnen - sofern dieser Wert kleiner als ihre aktuelle Geschwindigkeit ist.
3. Trödeln: In Abhängigkeit von einer Wahrscheinlichkeit (bspw. 15%) verlangsamt ein Auto seine Geschwindigkeit wieder um 1.
4. Bewegung: Jedes Auto wird bei einer Geschwindigkeit von v um v Felder nach vorne gerückt.

Dazu ein kurzes Beispiel. Die leeren Felder werden als Bindestriche dargestellt:

Initialier Zustand: --3-----4--3------3-------2--1---1---
Beschleunigung:     --4-----5--4------4-------3--2---2---
Bremsen:            --4-----2--4------4-------2--2---2---
Trödeln:            --4-----2--3------4-------2--2---2---
Bewegung:           ------4---2---3---3---------2--2---2-

Implementierung

Beginnen wir mit ein paar Paramtern für das Modell:

const densityInPercent = 13
const dawdleChangeInPercent = 15
const maxSpeed = 5
const autobahnSize = 2000

var autobahn [autobahnSize]int

var source = rand.NewSource(time.Now().UnixNano())
var rng = rand.New(source)

Wir legen die Verkehrsdichte auf 13% fest, die Warscheinlichkeit, dass ein Fahrer trödelt, auf 15%. Als Maximalgeschwindigkeit wählen wir 5 und unsere Autobahn soll eine Länge von 2000 haben. Allerdings werden wir die Straße als Kreis umsetzen, damit die Verkehrsdichte konstant bleibt. Autos fahren also rechts aus unserem Array heraus und kommen links wieder rein. Außerdem bereiten wir einen Generator für Zufallszahlen vor.

Initialisierung

Anhand unserer Verkehrsdichte erschaffen wir entsprechend viele Autos, die mit Maximalgeschwindigkeit fahren, und verteilen sie gleichmäßig auf unserer Straße. Natürlich könnten wir Position und Geschwindigkeit ebenfalls dem Zufall überlassen, aber letztlich wollen wir ja einen Stau aus dem Nichts zeigen. Deshalb starten wir mit perfekten Bedingungen:

func initializeEqually() {
    numberOfCars := autobahnSize * densityInPercent / 100
    distanceBetweenCars := autobahnSize / numberOfCars
    for i := range autobahn {
        hasCar := i % distanceBetweenCars == 0
        if hasCar {
            autobahn[i] = maxSpeed
        } else {
            autobahn[i] = -1
        }
    }
}

Beschleunigung

Widmen wir uns als nächstes der Beschleunigung. Jedes Auto, das noch nicht eine Geschwindigkeit von 5 erreicht hat, beschleunigt um 1.

func acceleration() {
    for i := range autobahn {
        if autobahn[i] == -1 {
            continue
        }
        if autobahn[i] < maxSpeed {
            autobahn[i]++
        }
    }
}

Bremsen

Für die nächste Regel prüfen wir für jedes Auto den Abstand zum Vordermann. Autos, die unsere Array-Grenzen rechts verlassen würden, schieben wir links wieder herrein. Um also auch den Abstand entsprechend berechnen zu können, sieht die for-Schleife unserer Hilfsfunktion getDistanceToNextCar() etwas abenteuerlich aus. Denn sobald i zu groß wird, müssen wir es auf den Anfang zurück setzen. Das eigentliche Bremsmanöver findet anschließend in slowingDown() statt, indem wir hier den Abstand mit der aktuellen Geschwindigkeit des Autos vergleichen und ggf. korrigieren.

func slowingDown() {
    for i, streetSection := range autobahn {
        if streetSection == -1 {
            continue
        }

        distance := getDistanceToNextCar(i)
        if distance < streetSection {
            autobahn[i] = distance
        }
    }
}

func getDistanceToNextCar(i int) int {
    distance := 0

    for {
        i++
        if i >= len(autobahn) {
            i = 0
        }

        if autobahn[i] != -1 {
            return distance
        }
        distance++
        if distance > maxSpeed {
            return maxSpeed
        }
    }
}

Trödeln

Nachdem wir im ersten Schritt die Geschwindigkeit aller Autos um 1 erhöht haben, verringern wir sie jetzt mit einer bestimmten Wahrscheinlichkeit wieder um 1. In diesem Fall hätte sich die Geschwindigkeit des Autos in der aktuellen Runde nicht verändert, weil der Fahrer getrödelt hat.

func randomization() {
    for i, streetSection := range autobahn {
        if streetSection == -1 {
            continue
        }

        carIsDawdling := rng.Intn(100) <= dawdleChangeInPercent
        if carIsDawdling && streetSection > 0 {
            autobahn[i]--
        }
    }
}

Bewegung

Im letzten Schritt verschieben wir jedes Auto seiner Geschwindigkeit entsprechend viele Felder nach rechts. Da wir im zweiten Schritt sicher gegangen sind, dass alle Autos sich ihrer Geschindigkeit entsprechend viele Felder vorwärts bewegen können, ohne einen Auffahrunfall zu verursachen, kann i um die Geschwindigkeit des jeweiligen Autos erhöht werden. Anders formuliert kann ein einzelner Streckenabschnitt pro Runde von nur maximal einem Auto befahren werden. Es kann also jede Runde maximal ein Auto das Array rechts verlassen und links wieder herrein fahren und wir können die Schleife in diesem Fall vorzeitig unterbrechen.

func carMotion() {
    for i := 0; i < len(autobahn); {
        if autobahn[i] == -1 {
            i++
            continue
        }

        speed := autobahn[i]
        autobahn[i] = -1
        i += speed
        if i >= len(autobahn) {
            i = i - len(autobahn)
            autobahn[i] = speed
            break
        }
        autobahn[i] = speed
        i++
    }
}

Ausführen des Modells

Schnell noch eine kleine Hilfsfunktion, die unsere Autobahn in einen String verwandelt, um sie in der Konsole ausgeben zu können:

func autobahnAsString() string {
    s := ""
    for _, streetSection := range autobahn {
        if streetSection == -1 {
            s += " "
        } else {
            s += strconv.Itoa(streetSection)
        }
    }
    return s
}

Und schon können wir unsere Schritte nacheinander anwenden:

package main

func main() {
    initializeEqually()
    fmt.Println(autobahnAsString())
    for i := 0; i < 1000; i++ {
        acceleration()
        slowingDown()
        randomization()
        carMotion()
        fmt.Println(autobahnAsString())
    }

}

Als Ergebnis erhalten wir Diagramme, die auf ihrer horizontalen Achse die Straße darstellen und auf der vertikalen nach unten hin die fortlaufende Zeit.

Ich habe das Programm zwei Mal ausgeführt. Beide Male habe ich den Trödelfaktor auf 15% gesetzt, allerdings betrug die Verkehrsdichte einmal 12% und einmal 13%. Leitet man die Ausgabe in eine Textdatei um und setzt die Schriftgröße etwas kleiner, dann erkennt man den zurückgelegten Weg einzelner Autos nur als schemenhafte Linien. Allerdings fällt schnell auf, dass das zweite Diagramm deutlich schwärzere Teile besitzt:

Folgendes ist dabei interessant: Einerseits haben alle Autos mit dem gleichen Abstand gestartet. Die Verkehrsdichte ist in beiden Fällen so niedrig, dass jedes Auto mit Maximalgeschwindigkeit fahren könnte und dabei mehr als genug Abstand zu seinem Vorausfahrenden hat. Dennoch kommt es in beiden Fällen zu Staus. Andererseits sorgt die geringfügig höhere Verkehrsdichte bei sonst gleichen Parametern zu deutlich vielzähligeren und zäheren Staus. Teilweise wachsen die Staus mit zunehmender Zeit und teilweise lösen sie sich fast auf, erscheinen aber wenige Runden später an ähnlicher Stelle.

Fazit

Was kann man also aus diesem Modell ableiten? Zunächst einmal ist Trödeln jeglicher Art der Auslöser für einen Stau. Wobei hier natürlich verallgemeinert wird: Eventuell wird die fahrende Person durch den Beifahrer oder schreiende Kinder auf der Rücksitzbank abgelenkt. Vielleicht stellt sie das Navi ein oder den Radiosender um. Vielleicht kennt sie sich nicht so gut aus und sucht eine bestimmte Straße. Die Gründe sind so vielzählig wie menschlich.

Auf der anderen Seite bildet sich durch eine einzelne trödelnte Person keinen Stau. Der entsteht erst dadurch, dass die sich dahinter befindenden Autofahrer nicht vorausschauend fahren. Fährt das Auto vor einem langsamer als erwartet, bleibt einem keine andere Wahl als zu bremsen. Besonders bei einem geringen Abstand kann es schnell mal zu einer Vollbremsung führen. Und das wiederum führt zu dem Problem, dass Autos am Stauanfang ihre Geschwindigkeit schlagartig reduzieren, aber am Ende des Staus nur langsam wieder beschleunigen. Überschreitet die Verkehrsdichte dann einen bestimmten Punkt, fahren Autos schneller in den Stau rein, als ihn am anderen Ende welche verlassen. Auch das lässt sich nur schwer vermeiden. Denn die meisten Autos können innerhalb weniger Sekunden von 100km/h auf 0km/h bremsen, anders herum schaffen das deutlich weniger. Und selbst wenn man ein entsprechend motorisiertes Fahrzeug führt - am Stauende Vollgas zu geben ist in der Regel nicht sinvoll. Denn hat man wirklich das Stauende erreicht? Im zweiten Diagramm sieht man bspw. links unten einen Stau, der zwei geteilt ist. Kurzzeitig fließt der Verkehr also etwas besser, allerdings würde man bei starker Beschleunigung nur dafür sorgen, dass ein weiteres Auto früher im zweiten Stau ankommt und diesem somit verschlimmert.

Es ist und bleibt also schwierig. Navigationssysteme wie Google Maps können theoretisch Abhilfe schaffen. Denn sie zeigen vorausliegende Staus und stockenden Verkehr bereits einige Kilometer vorher an. Ähnlich wie wenn man auf eine rote Ampel zufährt, kann es Sinn ergeben, die Geschwindigkeit berits frühzeitig zu verringern und Abstand zu halten. Springt die Ampel auf grün um (und hat man keine Autos vor sich), kommt man auch ohne großartiges Beschleunigen zügig weg, da man nicht anhalten musste. Aber damit das einen Stau auflöst, müsste das jeder machen. Oder man fährt mit dem Fahrrad, ist eh gesünder!

• Nagel-Schreckenberg Modell
• Stau Aus Dem Nichts
• Verkehrssimulation
• Zellularautomaten
• Stau
• Verkehrsfluss
• Verkehrsdynamik