A Lagrangian relaxation approach based on a time-space-state network for railway crew scheduling. (October 2022)

• Record Type: Journal Article
• Authors: Wang, Ying; Zhang, Zheming; Huisman, Dennis; D'Ariano, Andrea; Zhang, Jinchuan
• Is Part Of: Computers & industrial engineering. Volume 172:Part A(2022)
• Publication Date: 2022-10
• Subjects: High-speed rail -- Crew scheduling -- Meal time window -- Time-space-state network -- Lagrangian relaxation -- Column generation; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2022.108509
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: A time-space-state network is constructed to address complex crew scheduling rules. We introduce an improved model to take into account the anonymity of pairings. We develop a problem-dedicated algorithm based on the Lagrangian relaxation. Our method solves the problem faster than Column Generation (CG) and CPLEX. The proposed algorithm is highly competitive with CG in terms of solution quality. Abstract: The Crew Scheduling Problem (CSP) is an important and difficult problem in railway crew management. In this paper, we focus on the railway crew scheduling problem with time window constraints caused by meal break rules. To address these complex crew scheduling rules, we construct a Time-Space-State Network (TSSN), formulate the studied problem as an initial network flow model and a strengthened network flow model. By exploring the characteristics of the TSSN and the improved model, we develop an efficient algorithm based on Lagrangian relaxation to get a valid lower bound. The latter algorithm is combined with solving a set covering model to get a good quality upper bound solution for the studied CSP problem. We compare the performance of our Lagrangian relaxation approach with a commercial solver (CPLEX) and Column Generation (CG) on several real-world instances based of Chinese high-speed railways. The computational experiments show that our method can solve the railway CSP in a very short computation time compared to both CPLEX and CG, while obtaining (near-)optimal solutions for all instances. We thus propose an innovative efficient and effective approach to improve the railway CSP with meal break constraints.