Joint rolling stock rotation planning and depot deadhead scheduling in complicated urban rail transit lines

Dian Wang, D’Ariano, Andrea, Jun Zhao, Shuguang Zhan and Qiyuan Peng

European Journal of Operational Research, 2024, vol. 314, issue 2, 665-684

Abstract: This study investigates the joint rolling stock rotation planning and depot deadhead scheduling in complicated urban rail transit lines with multiple depots, multiple line services, and multiple compositions. The rotation planning aims at connecting the given train trips into train sequences (each of which is served by an individual rolling stock) and determining the routing plan of rolling stocks to pass through visited turnback stations while connecting train trips. The task of the depot deadhead scheduling is to determine conflict-free deadhead routes and deadhead timetables of rolling stocks between the origin/destination of each train sequence and corresponding depot. We formulate the studied problem as a generalized set partitioning-type model containing an exponential number of variables, by using a new time-space network representation and by proposing a novel modelling method for the departure–arrival headway requirement to control the number of constraints. Owing to the complexity of this model, a column generation-based algorithm is adopted to solve efficiently practical-size problems. We enhance a standard column generation (to compute tight lower bound) by further incorporating procedures of variable rounding and halted column generation, to strengthen the capability of searching for better quality solutions. Customized acceleration mechanisms are also explored to speed up the convergence of column generation and the computation of best-known integer solution. We compare our approach with three benchmark approaches and the trial-and-error-based empirical method used by rail dispatchers in practice. Computational results reveal that our approach outperforms these benchmark approaches by computing (near-)optimal solutions. Our optimized solution for a large real-world instance (computed within a practically reasonable computation time) is better than the empirical solution, in terms of all the considered objective function parts.

Keywords: Transportation; Rolling stock rotation planning; Depot deadhead scheduling; Binary linear programming; Column generation (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221723007695
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:314:y:2024:i:2:p:665-684

DOI: 10.1016/j.ejor.2023.10.012

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().