Je leest:

Eenvoudig model voor files

Eenvoudig model voor files

Auteur: | 17 januari 2004

Cellulaire automaten klinken misschien als iets heel ingewikkelds. Maar ze geven juist een verbluffend makkelijk te begrijpen wiskundig model voor filevorming.

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:

  • Afstand in eigen baan: als de afstand tot de volgende auto groter is dan b1, dan heeft het geen zin om van baan te wisselen. De volgende stappen worden overgeslagen. Anders: ga naar stap 2.
  • Afstand in andere baan: als de afstand b2 tot de volgende auto in de andere baan kleiner is dan b2, dan heeft het ook geen zin om van baan te wisselen. De volgende stappen worden dan overgeslagen. Anders: ga naar stap 3.
  • Plaats in de andere baan: er moet natuurlijk ook ruimte zijn om in te voegen. Als er op de andere baan minder dan b3 plaatsen achter de auto vrij zijn, dan mag er ook niet gewisseld worden. Stappen 4 en 5 worden overgeslagen. Anders: ga naar stap 4.
  • Toevalsaspect: een bestuurder heeft nu kans pw om ook daadwerkelijk van baan te wisselen
  • Toepassing resultaat: iedere auto die van baan wisselt wordt in het model verschoven.
  • 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.

    Dit artikel is een publicatie van NEMO Kennislink.
    © NEMO Kennislink, sommige rechten voorbehouden
    Dit artikel publiceerde NEMO Kennislink op 17 januari 2004

    Discussieer mee

    0

    Vragen, opmerkingen of bijdragen over dit artikel of het onderwerp? Neem deel aan de discussie.

    NEMO Kennislink nieuwsbrief
    Ontvang elke week onze nieuwsbrief met het laatste nieuws uit de wetenschap.