中文摘要：

列生成法是求解乘务调度问题的有效数学规划方法,但传统列生成法存在收敛速度慢的缺点.基于乘务问题特点,提出三种加速列生成求解的策略：在列生成迭代过程中,每隔一定周期移除受限主问题的部分“差”变量,以减小问题规模;提出基于乘务问题特征的强标号消除准则和基于该准则的二阶段子问题求解法以加速子问题求解;利用分支树求解整数解时,提出一个能充分利用已有解信息的班次池策略,以减小整数解求解时间.利用实际公共交通中的10组案例对所提加速策略进行测试.实验结果表明,这些加速策略能够有效加速列生成的求解,适用于求解大规模的乘务调度问题.

英文摘要：

Column generation is an efficient math programming approach to solve crew scheduling problems.However,it has the drawback of slow convergence.Three accelerating strategies are presented,based on problem-specific knowledge to speed up its solving process.The first one is to remove some ‘ bad＇ variables from the restricted master problem after a certain number of iterations.The second one is that a strong label cutting rule is presented,and a two-phase solution approach is proposed to solve the subproblem.The last one is that a shift pool strategy which can use the exiting solution information is proposed to reduce the time to solve integer solutions.Finally,ten real-world instances are tested,and the computational results show that the proposed strategies can accelerate the column generation algorithm.