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

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.