Joint optimization of high-speed train timetables and speed profiles: A unified modeling approach using space-time-speed grid networks

This paper considers a high-speed rail corridor that requires high fidelity scheduling of train speed for a large number of trains with both tight power supply and temporal capacity constraints. This research aims to systematically integrate problems of macroscopic train timetabling and microscopic train trajectory calculations. We develop a unified modeling framework using three-dimensional space-time-speed grid networks to characterize both second-by-second train trajectory and segment-based timetables at different space and time resolutions. The discretized time lattices can approximately track the train position, speed, and acceleration solution through properly defined spacing and modeling time intervals. Within a Lagrangian relaxation-based solution framework, we propose a dynamic programming solution algorithm to find the speed/acceleration profile solutions with dualized train headway and power supply constraints. The proposed numerically tractable approach can better handle the non-linearity in solving the differential equations of motion, and systematically describe the complex connections between two problems that have been traditionally handled in a sequential way. We further use a real-world case study in the Beijing-Shanghai high-speed rail corridor to demonstrate the effectiveness and computational efficiency of our proposed methods and algorithms.