Virtual formation train timetabling optimization of urban railway networks with rolling stock circulation plan: A coordinate descent-based decomposition method

Collaborative optimization of train timetables and rolling stock circulation plans (TTRC) under the virtual formation mode is challenging for urban railway networks due to their strong interdependence and combinatorial complexity. This study formulates the TTRC problem for network operation conditions as a mixed-integer nonlinear programming (MINLP) model, with the objectives of maximizing the number of rolling stock connections, minimizing the number of coupling and decoupling operations, and minimizing the total waiting time for arriving, detained, and transfer passengers. Inspired by coordinate descent, we design a customized distributed decomposition algorithm that incorporates a series of acceleration techniques to solve this MINLP model. Specifically, the original network problem is decomposed into a series of line-level subproblems that can be solved in parallel, and the train timetables obtained from these subproblems are used to efficiently recover feasible solutions to the original network problem. Additionally, McCormick envelopes are applied to convexify the bilinear terms in each subproblem, transforming each MINLP subproblem into a mixed-integer quadratic programming (MIQP) problem, which can provide a feasible solution to the corresponding MINLP subproblem. Logic-based domain reduction techniques are employed to further accelerate the solution of the MIQP subproblems. Numerical experiments are conducted on two case networks, including a small-scale synthetic network with three metro lines and a real-world network based on the Beijing metro, to validate the effectiveness and practicality of the proposed model and algorithm. The experimental results indicate that the proposed method effectively enhances the synchronization of train timetables, significantly reduces operation costs, and improves the service quality of urban railway networks. The designed decomposition algorithm is also more efficient than traditional heuristic algorithms.