基于生成与选择模式的公交驾驶员排班问题研究

发布时间：2017-10-11 06:35

  本文关键词：基于生成与选择模式的公交驾驶员排班问题研究

  更多相关文章： 公共交通 驾驶员排班 集覆盖模型 时间标记法 树枚举 遗传算法

【摘要】：本文主要研究了公交驾驶员排班问题,公交驾驶员排班问题是指构建合法班次集合满足行车计划的要求。求解目标是使班次数目和班次成本最低。本文基于“生成和选择”的模式对驾驶员排班问题进行求解。第一阶段：生成候选潜在合法班次集合生成阶段主要是采用启发式算法,根据约束条件生成一个大的候选班次集合。首先,根据集合覆盖模型的特点,集合覆盖模型中的变量对应于计划中班次,约束条件对应工作段。通常,工作段的数量是非常大的,一方面,大量的工作段会增加生成合法班次的数量,在实际的排班计划中,不可能生成所有的合法班次；另一方面,过多的工作段会增加约束条件的数量。本文运用基于时间标记法的启发式算法减少了参与生成班次的工作段数量。其次,在对潜在班次分析的基础上,运用树枚举算法的思想,生成潜在班次集合。第二阶段：班次集合的选择阶段这一部分设计了三种不同的遗传算法,在大量的潜在班次中选择一个接近最优的解或者最优解。运用不同的初始化,交叉和变异策略,三种遗传算法分别求解可行班次集合。本文以实际的公交运营数据,用生成和选择的方法求解驾驶员排班问题,并对三种算法的求解结果进行了比较和分析。对比结果表明,算法2中,针对班次求解改进的交叉策略能更快的求解可行班次集合；算法3中,基于班次评价的初始化策略,能使遗传算法在更短时间内求出较好的可行班次集合。
【关键词】：公共交通 驾驶员排班 集覆盖模型 时间标记法 树枚举 遗传算法
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：U492.2
【目录】：

• 致谢5-6
• 摘要6-7
• ABSTRACT7-10
• 1 引言10-14
• 1.1 研究背景和意义10-11
• 1.2 论文结构和主要内容11-12
• 1.3 关键技术12
• 1.4 技术路线图12-13
• 1.5 本章小结13-14
• 2 国内外研究的理论和方法综述14-21
• 2.1 国内外研究综述14-19
• 2.1.1 基本研究阶段14-15
• 2.1.2 早期纯启发式方法15
• 2.1.3 基于生成与选择模式的方法15-18
• 2.1.4 集成调度方法18-19
• 2.2 驾驶员排班系统的开发19-20
• 2.3 本章小结20-21
• 3 公交驾驶员排班问题分析21-26
• 3.1 公交驾驶员排班的相关概念21-22
• 3.2 公交驾驶员排班的目标22-23
• 3.3 公交驾驶员排班问题的集分割与集覆盖模型23-25
• 3.3.1 基本模型的阐述23-24
• 3.3.2 目标班次数的计算24-25
• 3.3.3 改进集合覆盖模型25
• 3.4 本章小结25-26
• 4 潜在合法班次的生成26-39
• 4.1 换班时间点的选取方法、26-31
• 4.1.1 选取方法基本原理介绍26-27
• 4.1.2 前后标记时间法27-28
• 4.1.3 时间标记法的实现和实例分析28-31
• 4.1.4 可能的风险分析31
• 4.2 初始班次集合的生成31-39
• 4.2.1 潜在班次分析32-34
• 4.2.2 树枚举候选班次集合34-36
• 4.2.3 班次结构评价36-38
• 4.2.4 本章小结38-39
• 5 遗传算法选择班次39-55
• 5.1 遗传算法概述及基本原理39-40
• 5.2 遗传算法求解驾驶员排班问题40-43
• 5.2.1 基于工作段的编码方式41
• 5.2.2 基于班次的编码方式41-43
• 5.3 遗传算法求解班次算法143-47
• 5.3.1 染色体表示43-44
• 5.3.2 初始化策略44
• 5.3.3 适应度函数44
• 5.3.4 交叉操作44-46
• 5.3.5 变异操作46-47
• 5.4 遗传算法的求解班次算法247-50
• 5.4.1 交叉策略47-50
• 5.5 遗传算法的求解班次算法350-53
• 5.5.1 初始化策略50-53
• 5.6 本章小结53-55
• 6 实例分析55-61
• 6.1 实验数据来源及实验平台55
• 6.2 实验结果分析55-60
• 6.3 本章小结60-61
• 7 总结和展望61-63
• 7.1 研究工作总结61
• 7.2 研究工作展望61-63
• 参考文献63-67
• 附录A67-73
• 附录B73-76
• 作者简历76-78
• 学位论文数据集78

【参考文献】

中国期刊全文数据库 前1条

1 沈吟东,倪郁东;基于整数规划的驾驶员调度系统—TRACSII[J];运筹与管理;2005年03期

中国硕士学位论文全文数据库 前2条

1 刘涛;公交驾驶员排班与轮班问题的模型与算法研究[D];北京交通大学;2013年

2 张学炜;集成化的公交运营计划编制方法研究[D];北京交通大学;2008年

，

本文编号：1011021