Optimizing train stopping patterns and schedules for high-speed passenger rail corridors

• Published in: Transportation research. Part C, Emerging technologies Emerging technologies, 2016-02, Vol.63, p.126-146
• Main Authors: Yue, Yixiang, Wang, Shifeng, Zhou, Leishan, Tong, Lu, Saat, M. Rapik
• Format: Article
• Language: English
• Subjects: Algorithms; Column generation; Demand; Mathematical models; Methodology; Optimization; Passenger trains; Railway service plan; Timetables; Train scheduling; Train stopping pattern; Trains
• ISSN: 0968-090X; 1879-2359
• DOI: 10.1016/j.trc.2015.12.007

•We introduce a new railway timetable optimization model to simultaneously consider the stopping patterns and train schedule.•We propose the use of an innovative column-generation-based heuristic to solve a very-large train timetable problem.•We illustrate the use of the model and algorithm to improve the timetable of a real-world HSR system. High-speed railway (HSR) systems have been developing rapidly in China and various other countries throughout the past decade; as a result, the question of how to efficiently operate such large-scale systems is posing a new challenge to the railway industry. A high-quality train timetable should take full advantage of the system’s capacity to meet transportation demands. This paper presents a mathematical model for optimizing a train timetable for an HSR system. We propose an innovative methodology using a column-generation-based heuristic algorithm to simultaneously account for both passenger service demands and train scheduling. First, we transform a mathematical model into a simple linear programming problem using a Lagrangian relaxation method. Second, we search for the optimal solution by updating the restricted master problem (RMP) and the sub-problems in an iterative process using the column-generation-based algorithm. Finally, we consider the Beijing–Shanghai HSR line as a real-world application of the methodology; the results show that the optimization model and algorithm can improve the defined profit function by approximately 30% and increase the line capacity by approximately 27%. This methodology has the potential to improve the service level and capacity of HSR lines with no additional high-cost capital investment (e.g., the addition of new tracks, bridges and tunnels on the mainline and/or at stations).