A rolling horizon-based decomposition algorithm for the railway network train timetabling problem

Abstract

This article presents the train timetabling problem in the complex railway network (including single-track line, double-track line, mixed-track line and terminal) and a solution algorithm. The problem is to determine the arrival, departure or through time of each train at each station on its predetermined route to satisfy several operational and safety requirements and minimise multiple objectives corresponding to train and engine time. The problem is formulated as a large-scale mixed integer nonlinear programming model with multiple objectives to simultaneously minimise the total train travel time, the total train connection time and the total engine turnaround time with several practical constraints. The model can be easily modified to simulate different scenarios of train timetabling problems. By aggregating the objectives and simplifying some constraints, a rolling horizon-based decomposition algorithm is developed based on the unique structure of the railway network and the characteristic of the train timetable. The algorithm decomposes the network into several single lines and progressively adds the train timetable of a new line into the current partial network train timetable until a complete network train timetable is obtained. The rolling horizon method is designed to determine the train timetable of each single line in iterations. Each iteration is restricted into a subregion of the feasible region, and the feasible solution to that subregion is determined by a timetable evaluation procedure and a boundary detection procedure. Lastly, computational test on real-world data shows that the presented approach can produce high-quality solutions for large-scale problems within a reasonable computation time.

Keywords:

• railway scheduling
• train timetabling problem
• optimisation model
• decomposition algorithm
• rolling horizon method

Acknowledgements

This work was supported by the National Nature Science Foundation of China under Grant U1234206. Parts of the work were supported by the Sichuan Province Key Laboratory of Comprehensive Transportation. The authors thank the Ministry of Railways Technology Development Plan under grant 2012X007-A and the Fundamental Research Funds for the Central Universities. The useful contributions and discussions from project partners are also acknowledged.