Demand-driven integrated optimization of train route, timetable and rolling stock scheduling in urban rail transit: A flexible composition strategy for in-service and additional trains

Flexible composition and additional train insertion play distinct yet complementary roles in addressing demand imbalances in urban rail transit; however, integrating them into a unified scheduling framework remains challenging due to the combinatorial complexity of coordinating dynamic capacity allocation with fixed infrastructure. This study focuses on the integrated scheduling of in-service and additional trains with flexible composition in extended-length metro corridors, aiming to efficiently match time-varying demand across multiple periods. Leveraging extended station functionalities, we construct a modular Space-Time-State network and develop a lightweight Mixed-Integer Nonlinear Programming (MINLP) model to simultaneously optimize the train service route, composition plan, timetable and rolling stock scheduling to minimize passenger waiting and train operation costs. The model coordinates train composition transitions for dynamic passenger demand matching, while enforcing constraints on rolling stock, depot capacities and turnaround operations. Additionally, linearization techniques convert the MINLP model into an equivalent mixed-integer linear programming model for exact solutions. For large-scale instances, we further propose a customized heuristic search framework based on a Parallel Time-Dependent Shortest Path Algorithm to sequentially search train operation plans within feasible time-composition windows. To mitigate myopic decision-making where local optima dominate individual train planning, we embed three penalty terms with Bayesian optimized weights. Experimental results demonstrate that our algorithm efficiently handles real-world cases involving 132 trains, outperforming Gurobi and the variable-type-based decomposition algorithm. Compared to the original plan from Nanjing Metro, our solution achieves up to 63.64% reduction in combined passenger waiting and operation costs while requiring 72 fewer operational rolling stock units.