Wie die Erklärung zur Entstehung von Verkehrsstaus mit mathematischen Mitteln möglich ist, zeigt diese Unterrichtseinheit. Mobilität spielt insbesondere in der modernen Gesellschaft eine wichtige Rolle. Im Alltag sind damit jedoch häufig Verkehrsstaus verbunden. Aber Staus kosten Nerven, verschlingen Zeit und Energie und produzieren zudem überflüssige Schadstoffe. Häufig entstehen bei dichtem Verkehr sogenannte "Staus aus dem Nichts". Wie sie entstehen und was jeder einzelne Verkehrsteilnehmer dazu beitragen kann, sie zu verhindern, zeigen einfache algorithmische Modelle und entsprechende Experimente. Um Verkehr im Detail zu simulieren und zu erklären, wie Stau entsteht, wird das Modell der zellulären Automaten herangezogen. Die Idee wird zunächst am "Spiel des Lebens" eingeführt und anschließend auf ein einfaches Modell zur Verkehrssimulation übertragen. Durch den Alltagsbezug werden auch Lernende angesprochen, die der Mathematik eher skeptisch gegenüberstehen. Die beigefügten Computerprogramme wurden in Python erstellt und können optional zum eigenen Experimentieren und Beobachten eingesetzt werden. Das "Spiel des Lebens": Einführung in zelluläre Automaten Das Modell stammt aus der Biologie und simuliert über Generationen das Entstehen und Vergehen von Zellen. Zelluläre Automaten zur Verkehrssimulation Mit zellulären Automaten lässt sich auch der Straßenverkehr recht einfach und gut simulieren. Einführung eines Trödelfaktors Mehr Realitätsbezug durch die Einführung des "Trödelfaktors" in das Modell, denn der Verkehr bewegt sich nicht absolut gleichmäßig. Die Schülerinnen und Schüler lernen am Beispiel von zellulären Automaten, einfache Algorithmen zu verstehen, anzuwenden und einige ihrer Eigenschaften zu analysieren. lernen Möglichkeiten und Grenzen von einfachen Modellen zur Verkehrssimulation kennen. variieren Eingabedaten für vorgegebene Programme zur Verkehrssimulation systematisch (Verkehrsdichte) und erkennen dabei grundlegende Eigenschaften des Verkehrsflusses in Abhängigkeit von den Eingabedaten. erkennen, dass die durch den Trödelfaktor eingeführte Individualisierung des Verkehrs die Wahrscheinlichkeit für das Auftreten von Staus erhöht. Modell aus der Biologie Um in das Prinzip der zellulären Automaten einzuführen, hat sich ein Einstieg über das sogenannte "Spiel des Lebens" bewährt, das 1970 von dem Mathematiker Conway entwickelt wurde. Dieses Modell hat einen völlig anderen Anwendungshintergrund (Biologie) als die Verkehrssimulation, benutzt aber ebenso wie diese einen zellulären Automaten. Zellentwicklung über Generationen Hier geht man aus von einem aus kleinen Quadraten (Zellen) bestehenden Gitter. Die Größe des Gitters kann frei gewählt werden (zum Beispiel 20 × 30 Zellen). Jede Zelle kann leben oder tot sein. Zu Beginn wird eine Anfangsgeneration lebender Zellen auf dem Spielfeld platziert. Die nächste Generation ergibt sich aus einigen einfachen Regeln. Auch diese Regeln entsprechen einem Algorithmus. Mathematisch entspricht das Entstehen jeder neuen Generation einem Iterationsschritt des durch die Regeln definierten Verfahrens. Populationen, die sich nicht (mehr) ändern, sind mathematisch gesehen Fixpunkte des Algorithmus. Bei Vorliegen einfacher Programmierkenntnisse können die (oder einige interessierte) Schülerinnen und Schüler das "Spiel des Lebens" auch selbst programmieren. Für diesen Fall empfiehlt sich der Hinweis, dass die Programmierung wesentlich einfacher ist, wenn man im Programm eine weitere (immer leere, hier gestrichelt dargestellte) Zellschicht rings um das eigentliche Spielfeld vorsieht, um eine Vielzahl sonst erforderlicher Fallunterscheidungen in Randnähe zu umgehen, wenn man die Anzahl der lebenden Nachbarzellen ermittelt. (Die Zellen am Rand oder in der Ecke des Spielfelds haben sonst im Programm weniger Nachbarn). 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. Das gleichförmige Verhalten im Modell entspricht nicht dem Verhalten, wie man es im realen Verkehr beobachten kann: Die Fahrzeuge bewegen sich in der Regel nicht alle mit der gleichen Geschwindigkeit und völlig gleichförmig vorwärts. Es gibt Überreaktionen beim Bremsen, welche die nachfolgenden Fahrzeuge ebenfalls zum heftigen Bremsen zwingen. Oft ist auch, gerade nach Staus oder bei auf Grün schaltenden Ampeln, ein verzögertes Beschleunigen zu beobachten. Ein derartiges Verhalten kann in unserem einfachen Modell durch die Einführung eines sogenannten Trödelfaktors nachgebildet werden. Der Algorithmus sieht dann folgendermaßen aus: 1. Beschleunigen vi = min {vi+1,vmax} 2. Bremsen Falls vi > d(i, i+1), so reduziere vi auf vi= d(i, i+1). Hierbei ist d(i, i+1) die Anzahl der leeren Zellen zwischen Fahrzeug i und Fahrzeug i + 1. 3. Trödeln Mit einer vorgegebenen Wahrscheinlichkeit p wird die Geschwindigkeit vi um 1 reduziert: vi= max {vi-1,0} mit Wahrscheinlichkeit p 4. Bewegen Jedes Fahrzeug i bewegt sich vi Zellen vorwärts. Für p=0 erhalten wir wieder das ursprüngliche Modell. H.-J. Bungartz, S. Zimmer, M. Buchholz und D. Pflüger Modellbildung und Simulation. Springer-Verlag, 2009. K. Nagel und M. Schreckenberg A cellular automaton model for freeway traffic. Journal de Physique I, 2:2221-2229, Dezember 1992.