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

ABSTRACT

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.

KEYWORDS:

• train timetabling
• scheduling
• optimization
• cumulative flow variable
• Lagrangian relaxation
• parallel computation

Acknowledgements

This work is supported by the National Key R&D Program of China under Grant [numbers 2018YFB1201403]. Moreover, the first author sincerely thanks the China Scholarship Council for supporting his visiting Ph.D. program.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by the National Key R&D Program of China [2018YFB1201403].