Hierarchical decomposition methods for periodic railway timetabling problems

Abstract

Today many European railway networks are operating near capacity. Developing timetables for these dense and often highly congested networks is becoming increasingly difficult. Several algorithmic approaches for solving timetabling problems have been developed in recent years, but the problem size, computational complexity, and lack of transparent interfaces for planners slow down adoption of these approaches in practice. This research proposed an iterative method based on train hierarchies to solve large periodic timetabling problems. The proposed method added a new group of trains to the schedule in each step of the process while holding trains added in previous steps fixed within a specified time interval. A case study with real-world data was used to analyze the influence of the number of decomposition steps and time interval on computation time and timetable quality. The results showed that setting parameters to a compromise between the extremes of a purely sequential or a purely simultaneous timetable planning approach was very effective at reducing computation time while still providing optimal or close-to-optimal timetables.