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