Integrated rolling stock deadhead routing and timetabling in urban rail transit lines

Dian Wang, D’Ariano, Andrea, Jun Zhao, Qingwei Zhong and Qiyuan Peng

European Journal of Operational Research, 2022, vol. 298, issue 2, 526-559

Abstract: This paper investigates an integrated rolling stock deadhead routing and timetabling problem from the rolling stock scheduling in a complicated urban rail transit line. Given the train sequences composed of passenger train trips within an operation day, the deadhead routing sub-problem aims at selecting the rolling stock deadhead routes between the depots and the first/last stations of each train sequence. The task of the deadhead timetabling sub-problem is to determine the arrival and departure times of rolling stocks along these selected routes. By means of a time-space network representation, we formulate the studied problem as a new (generalized set partitioning type) binary linear model, to minimize the weighted sum of total deadhead distance and total deadhead running time of rolling stocks during the depot exiting and entering operations. Owing to large numbers of constraints and decision variables in our model, a row and column generation-based algorithm is developed to solve practical-size problems efficiently. A row generation and a column generation are executed iteratively to reduce the numbers of considered constraints and decision variables in our algorithm, respectively. The pricing sub-problem (to identify new variables) in column generation is decomposed into multiple simplified problems, each of which is equivalent to a shortest path problem in the constructed time-space sub-network for any candidate route of each train sequence. These shortest path problems can be solved efficiently by using an existing shortest path algorithm. Computational experiments on a set of hypothetical, realistic, and real-world instances demonstrate that our approach can compute both tight lower bounds and (near-)optimal solutions (with a maximum relative optimality gap of 1.07%) for all the tested instances within a maximum computation time of approximately 3 hours for the studied tactical problem. Furthermore, our best-known solution for the real-world instance is better than the empirical solution designed by the rail managers mainly based on experience.

Keywords: Transportation; Urban rail transit; Rolling stock scheduling; Deadhead routing and timetabling; Binary linear model; Row and column generation-based algorithm (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721004811
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:298:y:2022:i:2:p:526-559

DOI: 10.1016/j.ejor.2021.05.053

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 ().