A Lagrangian relaxation approach based on a time-space-state network for railway crew scheduling

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.