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

交通运输系统工程与信息 ›› 2014, Vol. 14 ›› Issue (1): 144-149.

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

陈仕军，沈吟东^*

华中科技大学自动化学院，武汉 430074

收稿日期:2013-09-09 修回日期:2013-10-31 出版日期:2014-02-25 发布日期:2014-07-07
作者简介:陈仕军（1980-），男，湖北襄阳人，博士生.
基金资助:
国家自然科学基金（70971044，71171087，61304175）.

Accelerating Column Generation for Solving Crew Scheduling Problems

CHEN Shi-jun， SHEN Yin-dong

School of Automation, Huazhong University of Science and Technology, Wuhan 430074, China

Received:2013-09-09 Revised:2013-10-31 Online:2014-02-25 Published:2014-07-07

摘要/Abstract

摘要：

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

关键词: 系统工程, 列生成法, 加速策略, 乘务调度, 问题特征

Abstract:

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.

Key words: systems engineering, column generation, accelerating strategies, crew scheduling, problem-specific knowledge

中图分类号:

U268.6

陈仕军，沈吟东. 加速列生成法求解乘务调度问题[J]. 交通运输系统工程与信息, 2014, 14(1): 144-149.

CHEN Shi-jun， SHEN Yin-dong. Accelerating Column Generation for Solving Crew Scheduling Problems[J]. Journal of Transportation Systems Engineering and Information Technology, 2014, 14(1): 144-149.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract18725.shtml

http://www.tseit.org.cn/CN/Y2014/V14/I1/144

参考文献

[1] Hickman M, Mirchandani P, Voß S (Eds.). Computer-aided systems in public transport[M]. Lecture notes in economics and mathematical systems, Berlin:Springer, 2008, volume 600. 

[2] Lubbecke M E, Desrosiers J. Selected topics in column generation[J]. Operations Research, 2005, 53(6): 1007-1023.

[3] Abbink E, Albino L, Dollevoet T, et al. Solving large scale crew scheduling problems in practice[J]. Public Transport, 2011, 3(2): 149-164.

[4] Gamache M, Soumis F, Marquis G, et al. A column generation approach for large-scale aircrew rostering problems[J]. Operations Research, 1999, 47(2): 247-263.

[5] Gondzio J,González-Brevis P,Munari P.New developments in the primal-dual column generation technique[J]. European Journal of Operational Research, 2013, 224(1): 41-51.

[6] Elhallaoui I, Villeneuve D, Soumis F, et al. Dynamic aggregation of set-partitioning constraints in column generation[J]. Operations Research, 2005, 53(4): 632-45.

[7] Righini G, Salani M. Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints[J]. Discrete Optimization, 2006, 3(3): 255-273.

[8] Righini G, Salani M. New dynamic programming algorithms for the resource constrained elementary shortest path problem[J]. Networks, 2008, 51(3): 155-70.

[9] Leitner M, Raidl G R, Pferschy U. Accelerating column generation for a survivable network design problem[C]//Proceedings of the International Network Optimization Conference, 2009. 

[10] Alves C, De Carvalho J M V. Accelerating column generation for variable sized bin-packing problems[J]. European Journal of Operational Research, 2007, 183(3): 1333-1352.

[11] Feillet D, Dejax P, Gendreau M, et al. An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems[J]. Networks, 2004, 44(3): 216-229.

[12] Chen S, Shen Y. An improved column generation algorithm for crew scheduling problems[J]. Journal of Information and Computational Science, 2013, 10 (1): 175-183.

[13] Shen Y, Peng K, Chen K, et al. Evolutionary crew scheduling with adaptive chromosomes[J]. Transportation Research Part B, 2013, 56(10): 174-185. [14] Fores S, Proll L, Wren A. TRACS II: a hybrid IP/heuristic driver scheduling system for public transport[J]. Journal of the Operational Research Society, 2002, 53(10): 1093-100.

[1]	戴庆, 林正奎, 曲毅, 张佳佳. 并列瓶颈路网下个人与家庭混合通勤行为研究[J]. 交通运输系统工程与信息, 2022, 22(1): 182-194.
[2]	王庆云, 毛保华, 张国伍. 我国交通运输系统工程的演化[J]. 交通运输系统工程与信息, 2021, 21(5): 2-11.
[3]	张毅, 姚丹亚, 李力, 裴华鑫, 晏松, 葛经纬. 智能车路协同系统关键技术与应用[J]. 交通运输系统工程与信息, 2021, 21(5): 40-51.
[4]	黄爱玲，徐笑涵，关伟，段梦媛. 基于加权耦合映像格子的地铁网络稳定性演化研究[J]. 交通运输系统工程与信息, 2021, 21(3): 140-149.
[5]	金华，陈绍宽，王志美，张翕然，许凤志. 基于地铁乘务资源共享的排班计划优化方法[J]. 交通运输系统工程与信息, 2021, 21(2): 126-132.
[6]	关伟，吴建军，高自友. 交通运输网络系统工程[J]. 交通运输系统工程与信息, 2020, 20(6): 9-21.
[7]	张水潮，蔡逸飞，黄锐，周竹萍. 基于预约需求的共享停车平台泊位分配方法[J]. 交通运输系统工程与信息, 2020, 20(3): 137-143.
[8]	王庆云. 交通发展中的技术及技术含量的判断[J]. 交通运输系统工程与信息, 2019, 19(6): 1-5.
[9]	段力，刘聪健，方炽霖，程紫微. 信号控制与交通分配协同模型的自适应IOA 算法[J]. 交通运输系统工程与信息, 2019, 19(6): 77-84.
[10]	贾文峥，王艳辉，苏宏明，刘悦，林帅. 基于风险网络的轨道交通车辆风险评价[J]. 交通运输系统工程与信息, 2019, 19(4): 143-148.
[11]	许小卫，谢新连，李猛，赵家保. 基于R-THIOWGA集成算子的模糊关联多属性群决策方法[J]. 交通运输系统工程与信息, 2019, 19(1): 6-12.
[12]	王海星，梁倩倩. 危险货物道路运输风险复杂系统及风险测度模型与应用——以液氯运输为例[J]. 交通运输系统工程与信息, 2018, 18(4): 142-147.
[13]	江磊，王小敏，蔺伟. 基于动态贝叶斯网络的列控中心可靠性及可用性评估[J]. 交通运输系统工程与信息, 2018, 18(3): 182-188.
[14]	李岩，周文辉，南斯睿，陈宽民. 基于可靠度的单轨道交通施工区建设方案优化[J]. 交通运输系统工程与信息, 2017, 17(5): 250-256.
[15]	蔡晓琰，周国光. 收费公路PPP 项目运营期收益调节的期权价值分析[J]. 交通运输系统工程与信息, 2017, 17(3): 7-11.