Column Generation Accelerated Algorithm and Optimisation for a High-Speed Railway Train Timetabling Problem

Abstract

With the rapid development of high-speed railway (HSR) systems, the increasing demand for passenger traffic has put forward higher requirements for HSR train timetabling problems (HSRTTPs). This paper establishes two mathematical optimisation models with different optimisation objectives for an HSRTTP and solves these models through a column generation-based algorithm. However, the column generation-based algorithm has the disadvantage of a slow convergence rate, thus we put forward corresponding acceleration strategies for five stages of the algorithm: preprocessing, restricted master problem, pricing problem, branch-and-bound and postprocessing from a symmetry point between the computation efficiency and the accuracy. The effectiveness of the acceleration strategies was validated by a case study of the Beijing−Shanghai HSR. The results show that the proposed optimal acceleration strategies can increase the computation efficiency of the algorithm by 11.8× on average while ensuring the accuracy.

Keywords

• high-speed railway
• train timetable
• column generation
• space-time network
• acceleration strategies