原文传递
基于Hama的并行蚁群算法公交驾驶员排班问题研究
| 论文题名： | 基于Hama的并行蚁群算法公交驾驶员排班问题研究 |
| 关键词： | 公交驾驶员;排班问题;蚁群算法;最优解 |
| 摘要： | 论文对公交驾驶员排班问题进行论述，并研究了相关的数学模型和求解算法。针对求解算法中蚁群算法求解时间过长的不足，在基于开放的分布式计算平台Hama的基础上，设计与实现了基于Hama的两种并行蚁群算法模型以提高算法执行效率。论文的主要工作如下: 本文首先研究了公交驾驶排班问题的现状，分析了集成调度法、构建与优化和法生成与选择法三种思路的优缺点，讨论了蚁群算法和并行蚁群算法原理，确定了求解公交驾驶员排班问题的技术路线。 其次在研究Hama平台的基础上，提出了两种求解公交驾驶排班问题并行蚁群算法模型:粗粒度主从式并行蚁群算法模型和粗粒度最优解并行蚁群算法模型。这两种模型的基本算法均采用MMAS算法，粗粒度主从式并行蚁群算法模型中使用信息素矩阵作为交互内容，并通过设置主从节点的方式减少发送信息次数;粗粒度最优解并行以子蚁群的当前最优解及其路径作为交互内容。论文建立两种并行蚁群算法模型以期提高求解效率和得到更优结果，并详细阐述了实现过程中的重点问题。 最后论文选取北京市典型公交线路进行实证分析，试验环境采用四台虚拟机构造的并行计算集群，实验结果表明，在单机运算方面，普通蚁群算法求解结果与线路实际情况相比，可减少1个班型的使用，结果更优;在集群运算方面，同普通蚁群算法相比，两种并行算法均具有更好的求解效率，粗粒度主从式并行与粗粒度最优解并行的可达到最大加速比分别为2.90与3.41，其中，粗粒度主从式并行的求解质量要优于粗粒度最优解并行，因为粗粒度主从式并行采用信息素矩阵交互的策略，可以使搜索空间更大，在搜索过程中更有可能找到较优解。本文研究的基于Hama的并行蚁群算法在选择并行计算模型，设计并行蚁群交互策略等方面上具有一定的指导意义。 |
| 作者： | 余明捷 |
| 专业： | 系统工程 |
| 导师： | 马继辉 |
| 授予学位： | 硕士 |
| 授予学位单位： | 北京交通大学 |
| 学位年度： | 2016 |
| 正文语种： | 中文 |
检索历史
应用推荐
