Hoe de NS voor hoofdpijn zorgt bij wiskundigen

VideoOnverwachte storingen bij de NS zorgen soms voor totale chaos op het spoor. Hoe kan het dat een enkele storing zo’n grote invloed heeft op het gehele netwerk? Informaticus Arend Rensink (Universiteit Twente) maakt in zijn onderzoek naar het Nederlandse treinsysteem gebruik van de grafentheorie. Hoe die werkt, legt hij uit in zijn college bij de Universiteit van Nederland*.

Bijdrage van Universiteit van Nederland 16 mei 2019

Om het treinsysteem en de moeilijkheid ervan aan de hand van de grafentheorie uit te leggen, moeten we eerst weten wat een graaf eigenlijk is. Simpel gezegd gaat het volgens Rensink in de grafentheorie om knopen (knooppunten) met kanten daartussen. In het voorbeeld van de NS zijn de knopen de stations en de kanten de sporen.

Om met deze knopen en kanten, oftewel stations en sporen, te rekenen heb je de graad van een knoop nodig. Een graad is het aantal kanten dat eraan zit. De meeste treinstations in Nederland hebben dan ook graad twee, omdat ze twee buurstations hebben. ,,Vanuit Utrecht kun je vijf verschillende kanten op; graad vijf. Het station met de grootste graad van Nederland is, op afstand, station Zwolle. Deze heeft graad zeven.” Vanuit dit station kun je dus zeven verschillende kanten op.

Hoe hoger het aantal graden van een station, hoe groter de chaos die ontstaat als zo’n station uitvalt. ,,Als je op sommige plaatsen één station weghaalt, is direct een deel van Nederland onbereikbaar.” Zwolle is er hier een van.

Verbondenheid

De NS zoekt dan ook naar een systeem waarbij de verbondenheid tussen de verschillende stations zo groot mogelijk is. Dit zodat de reizigers, wanneer een station uitvalt, nog steeds naar hun plaats van bestemming kunnen komen. Volgens Rensink heeft de NS vele mogelijkheden waarop ze treinen kan laten rijden; één zo’n mogelijkheid noemen we een graaf.

Door middel van de grafentheorie is het mogelijk te simuleren waar op het spoor alle treinen van de NS zich bevinden. Iedere keer dat een trein verplaatst, ontstaat een andere graaf, oftewel een nieuwe mogelijkheid waarop de treinen kunnen rijden. Met het aantal treinen, sporen en stations, kun je het aantal grafen berekenen. Echter, de NS heeft honderden treinen, duizenden sporen en vele stations.

,,Als je dan gaat rekenen, kom je er al snel achter dat het aantal treingrafen enorm de pan uit rijst.” Dit zorgt er dan ook voor dat het Nederlandse treinsysteem in heel veel grafen is weer te geven. ,,Het aantal treingrafen is zoveel groter dan het aantal atomen in dit heelal, dat daar ook met de snelste computer niet meer tegenaan te rekenen valt.”

De NS zelf maakt daarom maar twee schema’s. Een voor de normale dienstregeling en een voor bij slecht weer. ,,Onder de aanname dat alle treinen op tijd rijden.” Pas bij de volgende jaarlijkse dienstregeling wordt een nieuwe treingraaf ontworpen. ,,Dat gaat vaak goed, maar als er door een onverwachte gebeurtenis te veel afwijkingen zijn van het schema, moet je ter plekke een nieuw schema bedenken.” En dat is met die honderden treinen en duizenden sporen en stations niet gemakkelijk.

_{*Dit is een wekelijkse bijdrage van de Universiteit van Nederland}

De Universiteit van Nederland heeft ook een podcast. Vind afleveringen terug op Spotify (http://bit.do/UvNL-Spotify) en iTunes (http://bit.do/UvNL-iTunes).

Bekijk hieronder meer colleges van de Universiteit van Nederland: