基于Hama的并行蚁群算法公交驾驶员排班问题研究

摘要

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

目录

声明

致谢

摘要

1 引言

1．1 研究背景与意义

1．2 研究方法

1．3 研究路线

2 国内外研究现状

2．1 公交驾驶员排班问题综述

2．2 蚁群算法研究综述

2．3 并行计算模型与框架发展综述

2．4 本章小结

3 公交驾驶员排班问题模型与求解方法

3．1 驾驶员排班问题的相关概念

3．2 公交驾驶员排班问题的模型

3．3 公交驾驶员排班问题的求解

3．3．1 生成可行班型

3．3．2 基于蚁群算法求解的基本步骤

3．4 本章小结

4 基于Hama的并行蚁群算法设计与实现

4．1 BSP模型与Hama框架平台简介

4．1．1 BSP模型

4．2．2 Hama框架平台

4．3 基础蚁群算法选择

4．4 并行策略的选择

4．5 粗粒度主从式互并行蚁群算法

4．5．1 消息传递与处理

4．5．2 信息素更新策略

4．5．3 算法流程设计

4．6 粗粒度最优解并行蚁群算法

4．6．1 消息传递与处理

4．6．2 信息素更新策略

4．6．3 算法流程设计

4．7 两种并行蚁群算法主要数据结构

4．8 本章小结

5 公交驾驶员排班问题案例分析

5．1 构建并行运算环境

5．1．1 Hama编程思路

5．1．2 构建Hama集群运算平台

5．1．3 平台功能性测试

5．2 可行班型生成

5．3 问题求解与结果对比

5．3．1 基本蚁群算法求解

5．3．2 并行蚁群算法求解与效果对比

5．4 本章小结

6 总结与展望

6．1 论文总结

6．2 研究展望

参考文献

附录

作者简历及攻读硕士学位期间取得的研究成果

学位论文数据集