Mathematics student visits all S-Bahn stations in Berlin by fastest route
Mathematics student Loes Knoben recently managed to visit all S-Bahn stations in Berlin in the fastest way possible, namely in 15 hours and 4 minutes, a new record. In order to achieve this, she programmed a mathematical tool in which all stations had to be visited at least once and where all connections had to be ridden at least once as well. Her tool eventually provided a travel plan which, despite a heavy storm, in practice would be 1 hour and 57 minutes faster than the previous record. At every station she took a picture as proof. The record attempt has been submitted to Guinness World Records, for an official mention.
The 23-year old student is currently working towards a master's degree in Applied Mathematics at the University of Twente. She performed the task together with her internship company Zuse Institute Berlin, a research institute for applied mathematics. The mission seemed simple: Find the shortest possible route to follow to visit all 166 S-Bahn stations in Berlin, over a distance of 331.5 kilometres. Knoben seized the challenge with both hands and started to programme a tool that showed the fastest route. The input required was an overview of the network and a timetable of departure times. Record attempts in public transport are very popular in several cities, for example in London and New York. Theoretically the tool could be used for other cities as well.
The shortest route
The programme designed by Knoben uses a network representation in the form of a graph, in which the entire timetable is being considered. Subsequently, the graph is converted into a travelling salesman problem via various mathematical transformations, a well-known problem in mathematics where various methods of solution are available. "The result of this is the eventual travelling schedule," according to Knoben. "I used this programme for the S-Bahn in Berlin, where we set the requirement that all stations and all connections have to be visited at least once. If multiple parallel lines exist between two stations it is sufficient to only use one of them. When determining the eventual schedule I also took the minimization of the odds of delay and the amount of delay into account, as the S-Bahn is not exactly known as a system that always continues to run on time. For that reason several back-up plans were made for risky transfers."
After months of preparation it was time for the attempt on 10 January. Together with colleague Isabel Beckenbach and two other interested people, Niels Lindner and David Kretz, Knoben went on her way. They started at Strausberg Nord station and finished at Erkner. The travel plan the tool provided was 3 hours and 17 minutes faster than the previous record, but because of a heavy storm the company was severely delayed. "The most realistic travel plan that we had calculated for the record attempt would take 13 hours and 44 minutes, but if we were lucky and managed to make a difficult transfer it could even be possible in 13 hours and 24 minutes. The first 7 hours went exactly according to schedule, which leads me to believe that if the weather is good the entire schedule should be possible. Now we had to wait for a long time at many stations and take detours because many trains didn't go and some parts of the tracks had been closed due to the storm. Next time it would be great to also optimize the weather. In the end we managed to do it in 15 hours and 4 minutes and that's still a new record," says Knoben.
Applied Mathematics is a two-year master's programme at the University of Twente. Knoben specializes in Operations Research, which focuses on the development of mathematical support for operational and logistic issues within the service sector, the industrial sector and within companies and organizations. The tool Knoben made will become available for continued development online. Guinness World Records will soon assess whether the record attempt will officially be recognized as the fastest.
Provided by University of Twente