A branch-and-price approach for trip sequence planning of high-speed train units. (April 2020)

• Record Type: Journal Article
• Authors: Gao, Yuan; Schmidt, Marie; Yang, Lixing; Gao, Ziyou
• Is Part Of: Omega. Volume 92(2020)
• Publication Date: 2020-04
• Subjects: Train units scheduling -- Trip sequence planning -- Maintenance -- High-speed railway -- Branch-and-price algorithm; Management -- Periodicals; 658.4005
• DOI: 10.1016/j.omega.2019.102150
• Languages: English
• ISSNs: 0305-0483

Abstract

Highlights: A trip sequence graph is developed to express the circulation and coupling/splitting of train units in the high-speed railway network. A path-based model and an arc-based model are formulated for the trip sequence planning problem based on the trip sequence graph. A customized branch-and-price algorithm is proposed to solve the path-based model. The proposed models are applied on the cases from the Chinese high-speed railway network. Abstract: In high-speed railway operations, a trip sequence plan is made once the timetable is determined, and serves as a reference in the subsequent operations of train units scheduling. In light of the maintenance requirements of train units and periodicity characteristics of trip sequences, we introduce a trip sequence graph to describe the train units' movement and coupling/splitting in a railway network. Based on the trip sequence graph, two integer linear programming models are then formulated, namely a path-based model and an arc-based model. Integrated with the characteristics of the trip sequence graph, a customized branch-and-price algorithm is developed to solve the path-based model. The two models are applied to the high-speed railway network in eastern China, and through numerical experiments, the effectiveness and applicability of the models are discussed.