Balancing a one-way corridor capacity and safety-oriented reliability: A stochastic optimization approach for metro train timetabling

In urban rail transit systems of large cities, the headway and following distance of successive trains have been compressed as much as possible to enhance the corridor capacity to satisfy extremely high passenger demand during peak hours. To prevent train collisions and ensure the safety of trains, a safe following distance of trains must be maintained. However, this requirement is subject to a series of complex factors, such as the uncertain train braking performance, train communication delay, and driver reaction time. In this paper, we propose a unified mathematical framework to analyze the safety-oriented reliability of metro train timetables with different corridor capacities, that is, the train traffic density, and determine the most reliable train timetable for metro lines in an uncertain environment. By employing a space-time network representation in the formulations, the reliability-based train timetabling problem is formulated as a nonlinear stochastic programming model, in which we use 0-1 variables to denote the time-dependent velocity and position of all involved trains. Several reformulation techniques are developed to obtain an equivalent mixed integer programming model with quadratic constraints (MIQCP) that can be solved to optimality by some commercial solvers. To improve the computational efficiency of the MIQCP model, we develop a dual decomposition solution framework that decomposes the primal problem into several sets of subproblems by dualizing the coupling constraints across different samples. An exact dynamic programming combined with search space reduction strategies is also developed to solve the exact optimal solutions of these subproblems. Two sets of numerical experiments, which involve a relatively small-scale case and a real-world instance based on the operation data of the Beijing subway Changping Line are implemented to verify the effectiveness of the proposed approaches.