摘要
列生成法是求解乘务调度问题的有效数学规划方法,但传统列生成法存在收敛速度慢的缺点.基于乘务问题特点,提出三种加速列生成求解的策略:在列生成迭代过程中,每隔一定周期移除受限主问题的部分'差'变量,以减小问题规模;提出基于乘务问题特征的强标号消除准则和基于该准则的二阶段子问题求解法以加速子问题求解;利用分支树求解整数解时,提出一个能充分利用已有解信息的班次池策略,以减小整数解求解时间.利用实际公共交通中的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.
出处
《交通运输系统工程与信息》
EI
CSCD
北大核心
2014年第1期144-149,179,共7页
Journal of Transportation Systems Engineering and Information Technology
基金
国家自然科学基金(70971044
71171087
61304175)
关键词
系统工程
列生成法
加速策略
乘务调度
问题特征
systems engineering
column generation
accelerating strategies
crew scheduling
problem-specific knowledge
