Integrated optimization of rolling stock allocation and train timetables for urban rail transit networks: A benders decomposition approach

We investigate the integrated optimization of rolling stock allocation and train timetables (RATT) in an urban rail transit network with multiple connected lines and rolling stock depots. Different from most existing research on single-line cases, we consider that the rail manager plans to allocate a certain fleet of rolling stock to depots to implement the operational timetables of multiple lines, where each depot can serve more than one line but has limited capacity. By means of the construction of a space-time network, we formulate RATT into a bi-objective mixed-integer linear programming (MILP) model. The model can simultaneously generate the rolling stock allocation plan and train schedules for the considered lines, with the aim of optimizing both the investment cost of rolling stock and the service quality of passengers. Due to the computational complexity of large-scale real-world instances, we develop a Benders decomposition-based solution algorithm, which decomposes the MILP into a rolling stock assignment problem and a set of independent subproblems, i.e., a train scheduling subproblem for each line. As the subproblems also contain integral variables, we further prove that a large portion of the subproblems, after proper reformulation, has the integrality property and can be solved rapidly via linear relaxation. We test our integrated approach and solution algorithms on real-world instances from the Beijing rail transit network. The results show that our solution approach can obtain near optimal solutions, while the commercial solvers cannot even return feasible solutions on real-world instances. Compared to the existing plan in the Beijing metro, our RATT approach can improve the service quality by 17.6%, on average, using the same fleet size of rolling stock.