Aaneengrenzende vakjes, tijdstappen en evolutieregels, meer heb je niet nodig om een cellulaire automaat te bouwen. Deze computersimulaties zijn een van de vele manieren om files te modelleren. Cellulaire automaten worden ook veel gebruikt in de informatica en theoretische biologie. In de eenvoudigste vorm bestaat een cellulaire automaat uit een strook cellen met daarin een 0 of een 1. In elke tijdstap wordt de nieuwe waarde voor een cel bepaald aan de hand van zijn eigen waarde en die van zijn buren. Zo’n automaat noemen we een één-dimensionale cellulaire automaat.
Voorbeeld van een een-dimensionale cellulaire automaat. Een 0 wordt weergegeven als een witte cel, een 1 wordt weergegeven met een zwarte cel. Per tijdstap wordt de volgende regel gebruikt: een cel wordt de volgende stap zwart als minstens een van zijn buurcellen op dat moment zwart is.
Met deze eenvoudige cellulaire automaat kunnen we een file modelleren. We delen dan de weg op in vakjes met elk waarde 0 of 1. Waarde 0 betekent dat er geen auto staat op dat moment en waarde 1 betekent dat er wél een auto staat. Dit model bevat alleen te weinig informatie om iets zinnigs over de werkelijkheid te zeggen. De vorming van files wordt immers door veel meer factoren bepaald dan het wel of niet een auto voor of achter je hebben. Wat is er nog nodig?
In 1992 bedachten Kai Nagel en Michael Schreckenberg een eenvoudig model voor filevorming, dat al een stuk realistischer is. In het model bestaat de weg uit één baan, voorgesteld door een een-dimensionale cellulaire automaat. Iedere cel kan precies één auto bevatten. Elke auto rijdt dezelfde richting op met een snelheid tussen 0 kilometer per uur en de maximaal toegestane snelheid vmax.
Voorbeeld van een begintoestand met vier auto’s. Bron: Andreas Schadschneiderhttp://www.thp.uni-koeln.de/~as/Mypage/traffic.html
Elke tijdstap doet de cellulaire automaat het volgende:
Versnellen: elke auto die nog niet met de maximale snelheid vmax rijdt, verhoogt zijn snelheid met 1 eenheid. Afstand houden: iedere auto met precies d lege plaatsen voor zich verlaagt zijn snelheid tot d (mits hij harder reed dan d). Toevalsaspect: met waarschijnlijkheid p verlaagt elke auto zijn snelheid met 1 eenheid. Toepassing resultaat: elke auto gaat x plaatsen vooruit, waarbij x de snelheid van de auto is.
Dit voorbeeld laat duidelijk zien hoe de stappen van het model werken. Bron: Andreas Schadschneider http://www.thp.uni-koeln.de/~as/Mypage/traffic.html
De variabelen vmax, d en p moeten van te voren bepaald worden. In dit model zijn al een aantal aspecten van het bekende file-rijden te zien: stukje rijden – stoppen – even stilstaan en weer een klein stukje rijden.
Een nadeel van het Nagel-Schreckenberg-model is, dat de meeste wegen waar grote files ontstaan tweebaans zijn. Een belangrijke factor die dan mee gaat tellen, is dat bestuurders van baan kunnen wisselen. Een beter model bestaat uit een twee-dimensionale cellulaire automaat, oftewel, twee een-dimensionale automaten onder elkaar. De auto’s kunnen zich nu ook verticaal verplaatsen.
Zo’n model bestaat uit twee fases: eerst wordt beslist welke auto’s van baan veranderen. Daarna worden in de tweede fase per baan de stappen van het eenbaansweg-model gedaan. Het wisselen van baan gebeurt volgens de volgende regels:
In dit model moeten nu ook de variabelen b1, b2, b3 en pw gekozen worden. Meestal wordt pw groter dan een half gekozen, zodat het effect van wisselen duidelijk zichtbaar is. De variabelen vmax, d en p kunnen eventueel verschillend gekozen worden voor de twee verschillende banen.
Natuurlijk zijn er nog een heleboel verbeteringen te verzinnen om dit model realistischer te maken: denk maar aan kruispunten of snelwegen met drie of meer banen. Toch geeft dit eenvoudige model een aardig inzicht in filevorming.
Zie ook:
- Applets met simulaties voor beide modellen (Engels)
- Het originele artikel van Nagel en Schreckenberg is hier te downloaden (Engels)
- Verdere uitleg bij het Nagel en Schreckenberg model (Engels en Duits)
- Een slide show over deze modellen met duidelijke illustraties (Engels)
- Artikel van RU Groningen waarin verschillende modellen voor filevorming vergeleken worden
- Artikel van TU-Delft waarin verschillende modellen voor filevorming vergeleken worden
- Meer over cellulaire automaten in het algemeen (Engels)
- Applet om zelf te spelen met een-dimensionale cellulaire automaten (Engels)
- Computer van slag (Kennislinkartikel)