Joint optimization of train timetabling and rolling stock circulation planning with flexible train composition for metro lines

To better satisfy the uneven space-time distribution for passenger demand, the flexible train composition in metro lines is investigated, where the train compositions can be changed flexibly at intermediate and terminal stations. A mixed-integer nonlinear programming (MINLP) model is proposed to jointly optimize train timetables and rolling stock circulation plans, in which the flexible train composition is considered, with the aim of minimizing the number of required train units and the number of stranded passengers, as well as maximizing the number of onboard passengers in the train units (i.e., minimizing the remaining capacity of train units). A set of binary variables characterizes flexible variations in train compositions to indicate whether train units are coupled or decoupled at stations. The proposed MINLP formulation can be transformed into a mixed-integer linear programming formulation by applying some linearization properties, which could then be solved by existing solvers. To improve the computational efficiency, we develop a Lagrangian relaxation algorithm to decompose the joint optimization problem into two subproblems, i.e., the train scheduling subproblem and the passenger flow subproblem. Based on a small-scale case and real data from Shanghai Metro Line 16, two sets of numerical experiments are conducted to validate the effectiveness and applicability of the proposed model and optimization algorithm. The computational results from the small-scale case indicate that the flexible train composition mode outperforms the traditional fixed train composition mode; however, the advantage of this flexible approach over multiple train composition modes diminishes as the time required for changing train compositions increases. The computational results calculated by real data demonstrate that, compared to the multiple train composition mode, the flexible train composition with a (de)coupling time of 60 seconds increases the metro line's capacity by 4.5\% during the morning peak period and by 2.1\% during the evening peak period.