Train shunting with service scheduling in a high-speed railway depot

At high-speed railways, trains cover services during the day and are required to undergo maintenance at depots each night. A low-quality train schedule in the depot may result in delays in the availability of trains during the day which influences the reliability of the train timetables. Accordingly, this study examines the problem of train shunting with service scheduling in a depot where daily maintenance, cleaning operation, and safety operational requirements are considered. To cope with this complex problem, we first construct a two-layer time-space network in which each layer can only be used by trains traveling in the same direction. We then formulate the considered problem as a minimum-cost multi-commodity network flow model with incompatible arc sets and operational constraints. To solve the network flow problem, we present a Lagrangian relaxation heuristic. Finally, several computational experiments with practical data based on the Hefei-Nan depot and randomly generated data on trains' arrival and departure times at the depot are conducted to confirm the effectiveness of our model and the efficiency of the proposed heuristics.