Optimization method of railway crew planning based on column generation and tabu search

In this paper, crew planning problem is divided into crew scheduling problem and crew rostering problem for step-by-step optimization, and the application of column generation and tabu search in solving these two problems is studied. To solve the crew scheduling problem, a space-time network is established to describe crew routes, a set partitioning model is established to minimize the non-crew time, and a column generation algorithm is designed to solve the problem. To solve the crew rostering problem, the solution result of the crew scheduling problem is taken as the input, and a multi-objective optimization model is established. A tabu search algorithm is designed to solve the crew rostering problem, and rules of adding long breaks are added to the algorithm. Finally, the Beijing-Tianjin intercity railway is selected for a case analysis, which proves the effectiveness of the models and algorithms proposed in this paper.