基于逐次确定换班机会集的乘务调度列生成方法

• 作者: 周伟刚 梁霄 许继影 陈仕军
• 来源期刊: 计算机集成制造系统
• 学科: 交通运输
• 关键词: 乘务调度 换班机会 列生成 集覆盖模型 调度
• 年，卷（期）: 2017,（1）
• 所属期刊栏目: 数字化/智能化/网络化制造技术
• 页码范围: 93-103
• 页数: 11页
• 分类号: U268.6
• 字数: 10060字
• 语种: 中文
• DOI: 10.13196/j.cims.2017.01.011

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈仕军	湖北文理学院数学与计算机学院	6	5	2.0	2.0
2	梁霄	湖北文理学院数学与计算机学院	3	0	0.0	0.0
3	周伟刚	湖北文理学院数学与计算机学院	7	5	1.0	2.0
4	许继影	湖北文理学院数学与计算机学院	3	2	1.0	1.0