Scheduling methods for automated railway timetabling

However, the design of a timetable is a highly complex task, which at present time can only be solved by subdivision. Many of the existing railway networks are so large, that their operators are forced to divide the planning of a network-wide timetable into several sub-steps. Often, the planning of a network-wide timetable is divided by the geography of the network, into local scheduling problems and then manually or computer-aided, local results are merged back together to a consistent network-wide solution to the problem. Most often local results are merged using rules of practice, i.e., by heuristics or practical experience of human planners (e.g. high-speed trains have precedence over suburban trains, first come first serve strategies etc.). As a consequence of this process, computed timetables do often not correspond to the optimal network-wide timetable. Additionally, they clearly neglect a large set of possible solutions, some of which are likely to perform better than the results of current practice.

It is a major challenge in the organization of railways to improve current practices beyond rules of practice and find best possible solutions to all the problems of railway traffic management.

Network-wide optimal timetables

The research project conducted by Florin Leutwiler under the supervision of Francesco Corman, Professor of Transport Systems, focused on new methods and algorithms for the automation of railway scheduling. The approach exploited decomposition. While any type of decomposition is theoretically possible, the team decided to use as a starting point the geographic decomposition available at SBB. The idea behind the decomposition is that the effects of scheduling choices are mostly local, i.e., they are more likely to affect trains close in time and space than those far away. The novel contribution of the project was in the way to include the interference between trains, both close to each other and far away. Interference amongst trains leads to delay propagation, which is a well-known problem in densely used railway networks.

The approach was able to identify a set of equations that specify to which extent trains are free to be scheduled without any interference, and when the interference is unavoidable. Only in this second case, coordination is necessary. The resulting algorithm exploiting this approach clearly outperforms standard approaches in scalability and showed a much faster computational performance.

The novel method has been also extensively tested and enhanced based on statistical knowledge about recurrent situations in railway operations. This research went beyond the original goals of SBB, to understand a possible innovative approach in this domain. The scientist at ETH Zurich demonstrated, that recurrent situations can be partially learned, and the decomposition method can be accelerated.  

Can the method be further improved?

The project team also wanted to go further and investigated how computation could be made faster. They reformulated the problem into a different set of equations, which are equivalent to understanding which events are easy to be scheduled in their original target time, and which are not.

In this new structure, an optimal timetable can be found using a problem widely known in the literature, the set covering problem, which can be solved extremely efficiently. In practical experiments, the novel heuristic decomposition method proved extremely fast for problems of railway schedules, to determine the first feasible solution with good quality.

The work introduces several new approaches and enhancements for the automation of railway scheduling. Newly developed methods and algorithms show improved runtime and scaling behaviour compared to existing approaches. The results of the project have been extensively documented in the thesis of Florin Leutwiler and they provide a great foundation for the future development of fully automated systems for railway scheduling and a tool for computing network-wide optimal timetables.

Francesco Corman and Florin Leutwiler reflect on their successful collaboration on a project that had its fair share of challenges. The agile working methods and unfixed specifications posed difficulties, especially as the academic timeline differed from the industry timeline. Despite this, the team found real-world data to be instrumental for validating their research. Florin encountered unexpected additional processing work due to the complexity of the data, but the benefits of using real-world data outweighed the challenges.

The collaboration with SBB not only provided the team with crucial data but also allowed them to benefit from SBB's expertise in understanding and processing the data. Additionally, SBB played a crucial role in preparing the necessary IT systems for testing the new solutions, allowing Florin to focus on the core research issue. The team's vision and frequent exchanges were highly effective in finding short-term and innovative solutions to the research question, as well as enabling more risky approaches that only academia could deliver.

Julian Jordi from SBB appreciated the collaboration's smoothness and that the that the researchers took the real problem and current methodology as a starting point for investigating alternative methods and algorithms. The SBB team was happy with the multiple possibilities to provide inputs and advice on preferred potential solutions along the project.

The friendly competition between the two parties allowed both to work on improving the algorithmic methods used to solve the given problem, resulting in faster progress.

“The continuous collaboration with the researcher provided our team with a friendly competition. Both parties were simultaneously working on improving the algorithmic methods used to solve the given problem. This was fruitful for both parties and probably helped us progress faster than if we did not have this exchange.”

However, the business problem evolved rapidly, causing frequent changes to the requirements and data model. This posed a challenge to the researchers' need for stable instances and data models for reproducible research. Despite this, the collaboration was a great experience for both parties, and they would sign up for a collaboration project within the framework of the Mobility Initiative again. Florin successfully defended his PhD dissertation last October and shortly after joined SBB as application engineer.