关键词: 乘务调度, 换班机会, 列生成, 集覆盖模型, 调度

Abstract: The traditional Column Generation (CG) algorithm was an exact optimization method and was difficult to deal with large-scale crew scheduling problems due to the exponential growth of nodes numbe in the binary tree.To avoid traversing all nodes of binary tree,a heuristic-based column generation approach was proposed.Aiming at the crew scheduling problem,a minimum-cost network flow formulation with Relief Opportunities (ROs) selection was proposed,which was transformed into a Set Covering Formulation (SCF) by using Dantzig-Wolfe decomposition theory,and a column generation approach was adopted to solve the Linear Programming (LP) relaxation of SCF,thus a tight lower bound of the crew scheduling problem was obtained.With the information of LP relaxation solution,ROs set which might not be used for the optimal solution was fixed,and an iterative optimization algorithm that solved a series of size-reduced crew scheduling problems was designed.In the experiments of solving several real-world crew scheduling problems,the proposed approach was compared with the genetic algorithm,and the result showed that optimal or near-optimal integer solutions were to be obtained in a reasonable amount of time for most instances.

Key words: crew scheduling, relief opportunity, column generation, set covering formulation, scheduling