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

发布时间：2017-04-16 15:06

  本文关键词：基于Hama的并行蚁群算法公交驾驶员排班问题研究，由笔耕文化传播整理发布。

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

• 致谢5-6
• 中文摘要6-7
• ABSTRACT7-15
• 1 引言15-19
• 1.1 研究背景与意义15
• 1.2 研究方法15-16
• 1.3 研究路线16-19
• 2 国内外研究现状19-31
• 2.1 公交驾驶员排班问题综述19-20
• 2.2 蚁群算法研究综述20-25
• 2.3 并行计算模型与框架发展综述25-29
• 2.4 本章小结29-31
• 3 公交驾驶员排班问题模型与求解方法31-41
• 3.1 驾驶员排班问题的相关概念31-33
• 3.2 公交驾驶员排班问题的模型33-34
• 3.3 公交驾驶员排班问题的求解34-39
• 3.3.1 生成可行班型35-36
• 3.3.2 基于蚁群算法求解的基本步骤36-39
• 3.4 本章小结39-41
• 4 基于HAMA的并行蚁群算法设计与实现41-61
• 4.1 BSP模型与Hama框架平台简介41-45
• 4.1.1 BSP模型41-45
• 4.1.2 Hama框架平台45
• 4.3 基础蚁群算法选择45-46
• 4.4 并行策略的选择46-48
• 4.5 粗粒度主从式互并行蚁群算法48-53
• 4.5.1 消息传递与处理49-51
• 4.5.2 信息素更新策略51
• 4.5.3 算法流程设计51-53
• 4.6 粗粒度最优解并行蚁群算法53-58
• 4.6.1 消息传递与处理54-55
• 4.6.2 信息素更新策略55
• 4.6.3 算法流程设计55-58
• 4.7 两种并行蚁群算法主要数据结构58-60
• 4.8 本章小结60-61
• 5 公交驾驶员排班问题案例分析61-79
• 5.1 构建并行运算环境61-65
• 5.1.1 Hama编程思路61-62
• 5.1.2 构建Hama集群运算平台62-63
• 5.1.3 平台功能性测试63-65
• 5.2 可行班型生成65-69
• 5.3 问题求解与结果对比69-77
• 5.3.1 基本蚁群算法求解70-73
• 5.3.2 并行蚁群算法求解与效果对比73-77
• 5.4 本章小结77-79
• 6 总结与展望79-81
• 6.1 论文总结79-80
• 6.2 研究展望80-81
• 参考文献81-87
• 附录A87-95
• 附录B95-103
• 作者简历及攻读硕士学位期间取得的研究成果103-107
• 学位论文数据集107

【相似文献】

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

1 高丽萍;彭敦陆;邓桂英;陈庆奎;;面向企业应用的“算法设计与分析”课程建设改革探索[J];中国电力教育;2011年20期

2 姜枫;;“算法设计与分析”课程教学改革探索[J];中国电力教育;2013年26期

3 苏安婕;吴志刚;;关键步分解法在算法设计与描述中的应用[J];成组技术与生产现代化;2011年03期

4 雷小园;;排列组合的算法设计与C++实现[J];中国新技术新产品;2010年10期

5 肖建华,何宏,陈展,欧阳湘江;算法中数学策略的应用与研究[J];湖南工程学院学报(自然科学版);2004年02期

6 余嵘华,张霆,张云;票证结存算法设计[J];合肥工业大学学报(自然科学版);2000年S1期

7 冯平;黄名选;;由频繁项集生成关联规则的算法设计和实现[J];广西工学院学报;2007年01期

8 王卿;路晓伟;;高等院校学分制教学排考问题算法设计[J];上海理工大学学报;2007年06期

9 刘永广;叶梧;冯穗力;庄宏成;;基于蚁群算法的无线Mesh网公平路由算法[J];华南理工大学学报(自然科学版);2009年01期

10 邢春峰,柳重堪;联想记忆系统的学习算法设计(I)[J];北京联合大学学报;1998年03期

中国重要会议论文全文数据库 前10条

1 雷咏梅;;椭圆曲线密码体制的算法设计与实现[A];西部大开发 科教先行与可持续发展——中国科协2000年学术年会文集[C];2000年

2 杨盘洪;朱军祥;赵建安;杨静;;机动目标跟踪的模糊变结构交互多模算法[A];2007'中国仪器仪表与测控技术交流大会论文集（二）[C];2007年

3 徐子珊;;《算法设计与分析》课程中的工程教育[A];2005年全国理论计算机科学学术年会论文集[C];2005年

4 王辉;刘治昌;;用一种新算法设计的安全系统[A];2007年中国智能自动化会议论文集[C];2007年

5 舒辉;柳清峰;杜祝平;周蓓;;实践教学模式在本科专业课程教学中的应用[A];中国电子教育学会高教分会2010年论文集[C];2010年

6 彭小宏;阳东升;刘忠;;基于聚类算法的组织协作网设计[A];2006中国控制与决策学术年会论文集[C];2006年

7 李皓;罗熊;;云存储部署优化的进化算法设计[A];2013年中国智能自动化学术会议论文集（第三分册）[C];2013年

8 罗长政;李熙莹;王镇波;罗东华;;一种大流量交叉路口的背景提取与更新算法[A];第十五届全国图象图形学学术会议论文集[C];2010年

9 杨利;李霖;昌月楼;阳国贵;;对称位向量及启发式并行散列连接算法[A];数据库研究与进展95——第十三届全国数据库学术会议论文集[C];1995年

10 张晋;;嵌入式电脑鼠运行算法的研究[A];全国第20届计算机技术与应用学术会议（CACIS·2009）暨全国第1届安全关键技术与应用学术会议论文集（上册）[C];2009年

中国重要报纸全文数据库 前1条

1 ;算法设计的策略[N];电脑报;2003年

中国博士学位论文全文数据库 前10条

1 谷伟哲;齐次光滑算法及其应用[D];天津大学;2010年

2 龙海侠;进化算法及其在生物信息中的应用[D];江南大学;2010年

3 谭跃;具有混沌局部搜索策略的粒子群优化算法研究[D];中南大学;2013年

4 尤海峰;求解隐式目标优化问题的交互式进化算法研究[D];中国科学技术大学;2011年

5 张常淳;基于MapReduce的大数据连接算法的设计与优化[D];中国科学技术大学;2014年

6 郭崇慧;地区中长期发展规划若干定量模型、算法及应用研究[D];大连理工大学;2002年

7 蒋蔚;粒子滤波改进算法研究与应用[D];哈尔滨工业大学;2010年

8 孙贺;算法设计中的若干前沿问题[D];复旦大学;2009年

9 陈宁涛;基于二分技术的高效算法设计及其应用[D];华中科技大学;2006年

10 娄晓文;无符号基因组切割再粘贴重组问题的算法研究[D];山东大学;2010年

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

1 李欣园;基于选择偏好的组合聚类算法研究与实现[D];内蒙古大学;2015年

2 杨潇;界约束非线性最小二乘问题的无导数算法[D];上海交通大学;2015年

3 王晓璐;基于Zynq的LS-SVM算法加速器设计[D];哈尔滨工业大学;2015年

4 楼磊磊;医疗保险数据异常行为检测算法和系统[D];浙江大学;2015年

5 齐海龙;基于改进人工蜂群算法的非线性系统辨识方法研究[D];北京化工大学;2015年

6 蔡平梅;结构化稀疏信号的恢复算法研究[D];上海大学;2015年

7 赵晨阳;基于蚁群算法的高阶图匹配方法研究[D];西安电子科技大学;2014年

8 苟清松;多目标粒子滤波检测前跟踪算法研究[D];电子科技大学;2015年

9 李枝勇;蝙蝠算法及其在函数优化中的应用研究[D];上海理工大学;2013年

10 李莲;基于蜂群和粗糙集的聚类算法研究[D];长沙理工大学;2014年

  本文关键词：基于Hama的并行蚁群算法公交驾驶员排班问题研究，由笔耕文化传播整理发布。

，

本文编号：311056