原文传递
公交驾驶员排班与轮班问题的模型与算法研究
| 论文题名： | 公交驾驶员排班与轮班问题的模型与算法研究 |
| 关键词： | 公共交通;公交驾驶员;运营规划;驾驶员排班问题;整数规划;拉格朗日松弛;遗传算法 |
| 摘要： | 公交驾驶员调度问题包含驶员排班与驾驶员轮班两个子问题。驾驶员排班与驾驶员轮班问题是公交运营中最耗时和最繁重的任务，因为班型的生成常常包含各种各样的约束，并且不同的公交企业拥有不同的约束规则。更为重要的是从公交企业自身角度来看，公交驾驶员排班与轮班所占据的预算支出是最大的。因此，对这两个问题进行研究非常有必要。 论文对北京市的公交驾驶员排班与轮班问题进行研究，主要研究问题相应的数学模型和求解算法。论文的主要工作总结如下: (a)第一部分:公交驾驶员排班问题公交驾驶员排班问题是指为驾驶员生成和选择一组可行的班型来覆盖掉所有的车次链，其目标是极小化总的班次数。本研究在集划分与集覆盖问题的基础上建立了针对北京市的公交驾驶员排班问题的数学模型。 考虑到其特殊的约束和目标，设计了三种求解方法。首先是一个非常简单、快捷的贪婪方法;其次，使用一个树枚举算法来快速枚举出所有的有效班型，将集划分与集覆盖问题折减至可操作的规模;最后，分别采用基于贪婪算法与拉格朗日松弛的启发式方法求解折减后的集划分与集覆盖问题。 用来自北京公交集团的数据验证了算法的有效性，计算结果表明贪婪方法和基于拉格朗日松弛的启发式方法能在合理的时间内获得较好的解，可以进一步应用于更大规模的公交驾驶员排班问题。 (b)第二部分:公交驾驶员轮班问题论文研究了公交驾驶员均衡轮班问题。该问题是指为公交驾驶员寻找一个最优的班次指派，使得总的工作班时平均分配给每一个驾驶员。 首先，构建了该问题等价的多层次均衡指派问题;接着，设计了求解该问题的基于遗传算法的求解算法;最后，使用算例验证了该方法的应用效果。同时还与Carraresi和Gallo、Ceder提出的两个启发式算法进行了求解结果的对比。 对比结果表明所设计的方法能获得更加均衡的班次和更少的轮班模板。同时为了更好的了解算法的性能，论文最后对算法相关的参数进行了灵敏度分析。 |
| 作者： | 刘涛 |
| 专业： | 系统工程 |
| 导师： | 马继辉 |
| 授予学位： | 硕士 |
| 授予学位单位： | 北京交通大学 |
| 学位年度： | 2013 |
| 正文语种： | 中文 |
检索历史
应用推荐
