A resource-oriented decomposition approach for train timetabling problem with variant running time and minimum headway

Solving the practical train timetabling problem under complex real-life train operation environment is challenging. This article addresses the train timetabling problem considering the variant parameters (i.e. running time and minimum headway) depending on stop-decisions. Based on a resource-oriented decomposition representation of safety headway, the train timetabling is modeled by cumulative flow variables considering the variant parameters depending on stop-decisions. A Lagrangian relaxation-based approach (LR) is used to decompose the combinatorial train timetabling problem into train-independent shortest path sub-problems, which can be solved simultaneously by parallel computation by relaxing the capacity constraint. A capacity assessment-based heuristic is proposed for improving the feasibility reparing of LR solutions. The solution quality and efficiency are analyzed employing the real-life operational data of Wuhan to Guangzhou high-speed railway in China. The benefits of the improved heuristic and parallel computation are demonstrated in contrast with the existed approach.