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

摘要： 传统列生成方法在求解乘务调度问题时,由于搜索二叉树的节点数呈指数级增长使其难以解决大规模问题。为避免搜索整个树节点,提出一种逐次缩小问题规模的迭代优化方法。针对乘务调度问题提出带有换班机会选择的最小费用网络流模型。利用Dantzig-Wolfe分解原理,将该模型转化为带有换班机会选择的集覆盖模型,并采取列生成方法求解其线性松弛解,以得到原问题的下界。在求解整数解时,利用线性松弛解信息,逐次确定不被使用的换班机会集,将问题转化为一系列规模逐次缩小的乘务调度问题。对城市公交中的多组乘务调度实例进行计算,将结果与问题下界和常用遗传算法的结果进行比较,表明大多数实例都能在合理的时间内取得最优解或近优解。

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