A decomposition approach to solve the individual railway crew Re-planning problem

Crew re-planning is an important and difficult task in railway crew management. In this paper, we establish a path-based model solving the Individual Crew Re-planning Problem (ICRP). The individual indicates that we focus the problem on specific (non-anonymous) crew members, considering their roles (leader and cabin crew) and qualifications. This problem is inspired by the crew planning problem faced in Chinese high-speed railway operations. To generate feasible paths, we construct a multi-layer time-space connection network and develop a heuristic algorithm. To decrease the complexity and scale of the model, we decompose the ICRP into two subproblems (for leaders and for cabin crew members respectively) which can be solved in sequence. In addition, we develop a Lagrangian relaxation (LR) algorithm to get valid paths quickly for both sub-problems. We combine the LR algorithm with solving the restricted decomposed models to get a good quality solution for the studied ICRP problem. We test our methods on several realworld instances from Chinese high-speed railways. The computational experiments show that our LR algorithm with a decomposition strategy can solve the decomposed models in a relatively short computation time compared to solving the original model directly, while obtaining (near-) optimal solutions for all instances.