A simulated annealing solution approach for the urban rail transit rolling stock rotation planning problem with deadhead routing and maintenance scheduling

Background: Urban rail transit ensures efficient mobility in densely populated metropolitan areas. This study focuses on the Cairo Metro Network and addresses the Rolling Stock Rotation Planning Problem (RSRPP), aiming to improve operational efficiency and service quality. Methods: A Mixed-Integer Linear Programming (MILP) model is developed to integrate rolling stock rotation, deadhead routing, and maintenance scheduling. Two single-objective formulations are introduced to separately minimize denied passengers and the number of Electric Multiple Units (EMUs) used. To address scalability for larger instances, a Simulated Annealing (SA) metaheuristic is designed using a list-based solution representation and customized neighborhood operators that preserve feasibility. Results: Computational experiments based on real-world data validate the practical relevance of the model. The MILP achieves optimal solutions for small and medium-sized instances but becomes computationally infeasible for larger ones. In contrast, the SA algorithm consistently produces high-quality solutions with significantly reduced solve times. Conclusions: To the best of the authors' knowledge, this is the first study to apply SA to the urban rail RSRPP while jointly integrating deadhead routing and maintenance scheduling. The proposed approach proves to be robust and scalable for large metro systems such as Cairo's.