加速列生成法求解乘务调度问题

陈仕军,沈吟东

(华中科技大学 自动化学院,武汉 430074)

加速列生成法求解乘务调度问题

陈仕军,沈吟东*

(华中科技大学 自动化学院,武汉 430074)

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

系统工程;列生成法;加速策略;乘务调度;问题特征

1 引 言

乘务调度问题是公交企业普遍面对的重要问题,也是计算科学界的 NP 难题.有效的调度方法能提高管理效率,并节约大量的人力成本.从上世纪60年代开始,众多学者和交通领域专家对该问题进行了深入研究,提出了各种有效的优化模型和解决方法[1].

列生成方法是求解大规模线性规划问题(LP)的有效方法,它通常与分支定界方法结合,用于解决大规模整数规划问题(ILP)[2].该方法也被广泛用于求解各类交通领域(公共交通、铁路、航空等)的乘务调度问题[3,4].对于某……