A Lagrangian Relaxation Approach Based on a Time-Space-State Network for Railway Crew Scheduling

The crew scheduling problem 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 solve this optimization problem, a solution method is proposed based on a time-space-state network and Lagrangian relaxation. In this method, the "hard constraints" corresponding to the crew rules are described as the state of vertices in the time-space-state network. Based on the network, this problem is modeled as a network flow model, referred to as an initial model. To break the symmetry and improve the strength of the formulation, five valid inequalities are added. To solve the problem, we relax the coupling constraints by Lagrangian relaxation. The resulting subproblems are shortest path problems in the time-space-state networks. We propose a Lagrangian heuristic to find a feasible solution. Finally, the solution method is tested on real-world instances from an intercity rail line and a regional railway network in China. We discuss the effects of additional valid inequalities and the effects of different length of meal time windows.