Enkel en alleen wiskunde

Jooooooooooooow!

Met het risico dat ik vanavond toch weer over treinen droom, tik ik speciaal voor jullie dit stukje . Voor wie het na twee weken al weer was vergeten, dit stukje gaat enkel en alleen over mijn opdracht. Ik zal het proberen interessant te houden, maar mocht je toch afhaken, lees dan in ieder geval het eind voor een belangrijke mededeling. Goed, komtie...

In Australie werkt het treinsysteem anders dan in Europa. Tussen de grote steden bevindt zich enkel outback, waardoor niemand aan overstappen doet. Je stapt gewoon op de trein naar de juiste stad en that's it. “Maar wat valt er dan nog aan te berekenen?”, zal menig lezer denken. Welnu, vanwege de gigantische afstanden ligt er tussen de meeste steden slechts één spoor. En daar moeten treinen over in twee richtingen. Elkaar tegemoet komende treinen kunnen elkaar slechts op enkele punten, de zogeheten crossing loops, passeren. Een crossing loop is een extra stukje spoor, waar treinen op kunnen wachten, zodat andere treinen kunnen passeren. Voor een plaatje van zo'n crossing loop, zie figuur 1 op http://picasaweb.google.com.au/jasperov/Verslag02?authkey=Gv1sRgCK_el5XktarMCA&feat=directlink

Mijn taak was om een methode te bedenken voor het voorspellen van aankomsttijden, zo dat slechts een bepaald percentage (zeg 5%) te laat zal arriveren. Dus dan is het eerst handig om te weten hoe ze het op dit moment doen bij de treinmaatschappij. Dit gaat als volgt: Een stel mensen (de schedulers) tekenen met pen en papier een zo geheten train graph. (trein grafiek) met op de verticale as positie, en op de horizontale as tijd. Crossing loops zijn op elk tijdstip natuurlijk op dezelfde plaats, dus dit zijn horizontale lijnen. Treinen verplaatsen van loop tot loop, en gaan dus diagonaal als ze rijden en horizontaal als ze wachten. Zie ook figuur 2.
Dit is natuurlijk slechts een voorbeeld met slechts twee crossing loops, twee stations en vier treinen om het simpel te houden. Het systeem waar ik vooral op heb getest is te zien in figuur 3.

Als reistijd tussen twee loops nemen de schedulers de verwachte tijd plus een bepaalde marge. En voor de niet-wiskundige lezers, met verwachte reistijd bedoel ik de gemiddelde reistijd. Als niet-wiskundigen verwachten ergens op een bepaald moment te zijn, zijn ze soms op tijd en soms later. Als wiskundigen iets verwachten, zijn ze soms te laat, maar andere keren net zoveel te vroeg om te compenseren voor de keren dat ze te laat zijn.
Vervolgens kijken de schedulers op welk tijdstip de treinen op hun eindpunt aankomen en kiezen deze waardes als aankomsttijden in hun treinschema's. “Een mooie methode”, zou je zeggen.

En hoewel de methode ook wel logisch klinkt, wordt er iets compleet over het hoofd gezien. De daadwerkelijke reistijd tussen twee loops is namelijk nooit gelijk aan de verwachte reistijd. “Maar daar is de marge toch voor?” Maar het probleem is dat als je de verwachte aankomsttijden verkeerd inschat en dan een marge neemt, sommige treinen in 2% van de gevallen te laat zijn en anderen in 8%.

En dat is precies wat er met de huidige methode gebeurt. Als in de huidige methode treinen elkaar passeren, zal één van de treinen helemaal niet hoeven te wachten, en zal de andere trein een vertraging oplopen afhankelijk van hoever de ene trein toevallig van de crossing loop verwijderd is op het moment dat hij begint met wachten. Er wordt dus eigenlijk uit gegaan van een vertraging, op basis van één toevallige situatie, die wegens de marges niet eens de meest waarschijnlijke situatie is!

Daarom lijkt het realistischer om een verwachte vertraging per trein te rekenen op basis van als de treinen elkaar op een willekeurig moment zouden passeren. Het probleem is alleen dat het ongelovelijk ingewikkeld wordt als je precies de kansverdeling van dit willeurige moment wilt uitrekenen. Maar gelukkig hebben toegepaste wiskundigen voor alle problemen een zeer eenvoudige oplossing, ze maken aannames. En mijn aanname was meteen een hele makkelijke: Op het moment dat één van de treinen arriveert op de crossing loop, waar hij gepasseerd gaat worden, is de positie van de andere trein uniform verdeeld over het hele spoorsegment tot aan de volgende crossing loop. Voor de niet-wiskundigen, uniform verdeeld betekent simpelweg dat iedere afstand een gelijke kans heeft.

Natuurlijk zal zo'n aanname nooit precies kloppen. Er is natuurlijk een punt waar de treinen de meeste kans hebben elkaar te kruisen, en des te verder van dat punt, des te kleiner de kans dat ze daar kruisen. Maar, omdat het gaat om de afstand tot de volgende crossing loop, en niet om de afstand tot één vast punt lijkt het wel aannamelijk. Maar of de aanname klopt, dat weet je natuurlijk pas als je de resultaten ziet.

Maar goed, over de uniforme verdeling is genoeg bekend, zo dat het niet meer heel moeilijk was om de verwachte vertragingen, maar ook de variantie (een waarde die de afwijking van het gemiddelde aangeeft) uit te rekenen. Ik had natuurlijk een rekenmachientje kunnen pakken, om zelf de verwachte vertragingen uit te rekenen, maar het is makkelijker om een programmatje te schrijven dat telt welke treinen elkaar moeten passeren en op basis daarvan vertragingen aan de treinen toekent. Zeker als je de methode vaker wilt gaan gebruiken.

Wel belangrijk is dat door deze vertragingen treinen meer ander treinen kunnen passeren. Dus het programma rekent op basis van deze vertragingen nieuwe aankomsttijden uit, waarna het aantal keer passeren opnieuw geteld wordt. En dit proces gaat door totdat geen nieuwe vertragingen worden gevonden. Hiermee komen we dan eindelijk tot definitieve verwachte aankomsttijden. Door hier per trein het juiste aantal varianties bij op te tellen, komen we zelfs tot een verantwoorde marge, in plaats van het natte vinger werk dat nu plaatsvindt.

Tenslotte is het dan nog tijd om de nieuwe methode, die we de Cross counting methode noemen te testen. En hoewel de Cross counting methode wel in een uurtje wel geprogrammeerd was, kostte het maken van een programma dat de huidige methode simuleert een stuk meer werk. In plaats van simpel te tellen en wat kansen uit te rekenen, moet er een heel regelsysteem ingevoerd worden, zodat elke virtuele trein weet wanneer hij moest stoppen en doorrijden. Ook moet het programma natuurlijk bijhouden wanneer de treinen op hun eindpunt aankomen en moet het mooie train graphs kunnen maken, zodat ik kan checken welke bugs er nog in zitten. (En dat waren er zonder te overdrijven honderden.)

Gelukkig kan het programma van de huidige methode met een kleine aanpassing dubbel fungeren als een 'Monte Carlo'-simulatie: door in plaats van verwachte reistijden plus marges, willekeurige reistijden te nemen simuleer je de werkelijkheid. Als je dit maar vaak genoeg (100000 keer) doet en het gemiddelde te nemen heb je een goede schatting van de daadwerkelijke aankomsttijden. En door te kijken hoeveel van deze treinen later waren dan de schattingen van de huidige methode en de cross counting method is te zien welke methode beter werkt.

En de resultaten zijn prima. Het duurde even voordat we een geschikte marge hadden gevonden voor de huidige methode, maar in het beste geval liggen de percentages overal tussen de 2 en de 8 procent, met af en toe uitschieters, terwijl de Cross counting methode percentages tussen de 4 en de 6 procent geeft, met af en toe uitschieters. Hoewel de schattingen voor de meeste treinen dus behoorlijk goed zijn, heb je uitschieters, waarvan af en toe zelfs 50% te laat komt.

Het blijkt dat de meeste uitschieters treinen zijn die kort voor of na andere treinen vertrekken. Na vele aanpassingen op de methode is het nog niet gelukt om de aankomsttijden van deze treinen beter in te schatten. Ik heb al wel goede vermoedens van alle oorzaken die deze treinen te laat doen komen. Bovendien is het natuurlijk ook niet heel logisch om twee treinen vlak na elkaar te laten vertrekken, aangezien dat erg onveilig is op een enkel spoort Voor systemen met logische vertrektijden werkt de Cross counting methode dus prima.

Samengevat heb ik dus een methode ontwikkeld die sneller en beter is dan de huidige methode voor de meeste logische systemen. En mijn onderzoek naar de oorzaken van de verkeerde schattingen staat uitgelegd in mijn verslag, zodat mijn begeleiders er verder mee kunnen werken.

Het was een erg interessantge opdracht, zeker omdat ik dus al tijdens mijn opdracht leerde over de Australische cultuur. Terugkijkend valt me op dat ik het probleem heb opgelost met logisch redeneren, programmeren en vooral eerstejaars wiskunde. Toch heb ik het idee dat ik erg veel heb geleerd over hoe het er aan toe gaat met onderzoeken. Ik was voor mijn opdracht al zeven jaar lang uitgekeken op wiskunde, maar nu begin ik toch na te denken of promoveren niet iets voor mij is. Maar gelukkig heb ik nog een hele afstudeeropdracht om daar achter te komen.

En dan nog en belangrijke mededeling: 19 december is er feest! Of jullie het nu zien als welkom-terug-feest, ik-heb-mijn-bachelor-gehaald-feest, ik-heb-hopelijk-mijn-stage-gehaald-feest, vertraagd-verjaardagsfeest, vertraagd-sinterklaasfeest of te-vroeg-kerstfeest doet er niet toe. Onafhankelijk van de reden wordt het erg gezellig. Ik stuur nog wel echte uitnodigingen, maar zet de datum vast in je agenda, en zorg dat je rond die tijd in Enschede bent!

En eigenlijk heb ik dan ook nog een verzoek: wie heeft er vanaf 12 december een kamer beschikbaar in Enschede? Ik ken namelijk iemand die dan een kamer nodig gaat hebben.

En dan natuurlijk nog over de volgende keer. Als jullie dit lezen, ben ik in waarschijnlijk in Alice Springs. Ik heb vet veel gezien, maar nog geen tijd gehad om er over te tikken. Hopelijk heb ik in de bus naar Darwin wel genoeg tijd. In dat geval kunnen jullie waarschijnlijk over vijf dagen een deel van mijn avonturen in de outback lezen.