Nieuw record: snelste route via de Berlijnse S-Bahn

De 23-jarige student volgt momenteel de master Applied Mathematics aan de Universiteit Twente. In samenwerking met haar stagebedrijf Zuse Institute Berlin, een onderzoeksinstituut voor toegepaste wiskunde, voerde ze de opdracht uit. De missie klonk simpel: Vind een zo kort mogelijke route waarbij je alle 166 S-Bahn stations over een lengte van 331,5 kilometer in Berlijn bezoekt. Knoben pakte de uitdaging met beide handen aan en begon met het programmeren van een tool die de snelste route weergeeft. Als input is de structuur van het netwerk nodig met de timetable van vertrektijden. Recordpogingen in het openbaar vervoer zijn in een aantal steden erg populair, bijvoorbeeld in Londen en New York. In theorie zou de tool ook voor andere steden gebruikt kunnen worden.

Snelste route

Het programma dat Knoben ontwierp, gebruikt een netwerkrepresentatie in de vorm van een graaf, waarbij de gehele timetable in overweging wordt genomen. Vervolgens wordt de graaf via diverse wiskundige transformaties omgezet in een handelsreizigersprobleem, een bekend probleem in de wiskunde waarvoor oplossingsmethoden beschikbaar zijn. "Het resultaat dat eruit komt rollen is uiteindelijk het reisschema", aldus Knoben. "Ik heb dit programma gebruikt voor de S-Bahn in Berlijn, waarbij we de eis hebben gesteld dat alle stations en alle connecties minstens een keer moeten worden bezocht. Wanneer er meer parallelle lijnen zijn tussen twee stations is het genoeg om er hiervan één te gebruiken. Bij het bepalen van het uiteindelijke schema heb ik ook rekening gehouden met het minimaliseren van de kans op vertraging en de hoeveelheid vertraging. De S-Bahn staat namelijk niet echt bekend als een systeem dat altijd netjes op tijd rijdt. Daarom zijn er ook enkele back-up plannen gemaakt voor overstappen die risicovol zijn."

Tegenslag

Na maanden voorbereiding was het op 10 januari zover. Knoben ging samen met collega Isabel Beckenbach en twee andere geïnteresseerden, Niels Lindner en David Kretz, op weg. Ze startten bij station Strausberg Nord en eindigden bij Erkner. Het reisplan dat uit de tool kwam rollen was 3 uur en 17 minuten sneller dan het vorige record maar door een zware storm liep het gezelschap veel vertraging op.

"Het meest realistische reisplan dat we voor de recordpoging hadden berekend zou 13 uur en 44 minuten duren, maar als we twee keer geluk hadden en een lastige overstap haalden dan zou het zelfs in 13 uur in 24 minuten kunnen. De eerste 7 uur gingen precies volgens schema, waardoor ik denk dat met goed weer het hele schema mogelijk zou moeten zijn. Nu hebben we op veel stations lang moeten wachten en omwegen moeten nemen omdat veel treinen niet reden en sommige stukken spoor afgesloten waren vanwege de storm. Volgende keer zou het dus ook goed zijn om het weer te optimaliseren. Uiteindelijk hebben we het voor elkaar gekregen in 15 uur en 4 minuten en dat is alsnog een nieuw record", zegt Knoben.

Applied mathematics

De opleiding Applied Mathematics is een tweejarige masteropleiding aan de Universiteit Twente.  Knoben volgt de specialisatie Operations Research, welke zich richt op het ontwikkelen van wiskundige ondersteuning voor operationele en logistieke vraagstukken binnen de dienstensector, de industrie en binnen bedrijven en organisaties. De tool die Knoben heeft gemaakt komt online beschikbaar voor verdere ontwikkeling. Of de recordpoging ook daadwerkelijk erkend wordt als de snelste zal Guinness World Records binnenkort beoordelen.