Hadoop平台下基于路网加权分层和关联规则的最短路径算法研究

发布时间：2017-08-14 02:29

  本文关键词：Hadoop平台下基于路网加权分层和关联规则的最短路径算法研究

  更多相关文章： 最短路径算法 加权分层 关联规则 Hadoop

【摘要】：传统Dijkstra、Floyd、A*等算法适合于求解具有串行化、计算复杂度不高、存储消耗不大等特性的最短路径问题,在大规模复杂路网中的搜索效率不高。伴随着大数据技术的热潮,如何运用分布式存储、并行化计算和强大的分析处理能力实现快速、准确地求解最短路径问题,是交通领域学者关注和研究的重点之一。因此,本文基于Hadoop大数据平台的HDFS模块,分布式存储海量浮动车数据;基于新一代YARN计算框架,并行化迭代求解最短路径,减少算法的时间复杂度。在此基础上,分析处理交通路网加权分层所需要的动态、静态道路属性数据,并提取关联规则方法挖掘交叉口间关联性的浮动车出行路径集。然后,采用层次分析法对道路等级、车道数量、路段长度、红绿灯、收费站、平均行程速度和通行次数等影响因素进行权重加权计算,从而实现分层分区,从空间拓扑结构上简化路网搜索规模。接着,使用关联规则方法挖掘海量浮动车的出行路径数据,寻找分区内各交叉口间的强关联规则,减少搜索的节点数目。最后,搭建Hadoop集群实验平台,对比分析传统A*算法、基于YARN并行化迭代计算模型的最短路径算法、Hadoop平台下基于加权分层和关联规则的最短路径算法等的有效性能指标。实验结果表明,该算法在搜索速度上具有明显的优势,而且求解的最短路径结果符合出行者的行驶习惯,满足居民快捷出行的需求。
【关键词】：最短路径算法 加权分层 关联规则 Hadoop
【学位授予单位】：华南理工大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：U491
【目录】：

• 摘要5-6
• Abstract6-10
• 第一章 绪论10-18
• 1.1 研究背景和意义10
• 1.2 国内外研究现状分析10-14
• 1.2.1 国外研究现状10-12
• 1.2.2 国内研究现状12-14
• 1.2.3 研究现状分析总结14
• 1.3 研究内容14-15
• 1.4 技术路线与章节安排15-17
• 1.4.1 技术路线15-16
• 1.4.2 章节安排16-17
• 1.5 本章小结17-18
• 第二章 交通路网最短路径算法研究18-26
• 2.1 最短路径概述18-19
• 2.2 最短路径算法分类体系19-21
• 2.2.1 问题类型19-20
• 2.2.2 路网特性20-21
• 2.2.3 求解技术21
• 2.3 交通路网常用最短路径算法分析21-25
• 2.3.1 Dijkstra算法22
• 2.3.2 Floyd算法22-23
• 2.3.3 A*算法23-25
• 2.4 本章小结25-26
• 第三章 基于Hadoop大数据平台的最短路径算法研究26-38
• 3.1 交通大数据26
• 3.2 交通数据挖掘技术26-28
• 3.2.1 数据挖掘定义26-27
• 3.2.2 交通数据挖掘算法27
• 3.2.3 交通数据挖掘技术流程27-28
• 3.3 Hadoop平台28-35
• 3.3.1 MapReduce29-33
• 3.3.2 HDFS33-34
• 3.3.3 YARN34-35
• 3.4 基于YARN的最短路径算法设计35-37
• 3.5 本章小结37-38
• 第四章 基于加权分层和关联规则的最短路径算法研究38-60
• 4.1 交通路网概述38
• 4.2 交通路网分层策略38-42
• 4.2.1 交通路网分层模型描述38-41
• 4.2.2 交通路网分层原则41
• 4.2.3 交通路网分层数量41-42
• 4.3 交通路网加权分层42-52
• 4.3.1 层次分析法概述42-45
• 4.3.2 交通路网权重确定45-48
• 4.3.3 交通路网分层分区48-52
• 4.4 分区交叉口间关联规则挖掘52-57
• 4.4.1 关联规则概述52-53
• 4.4.2 交叉口间关联规则挖掘模型53-57
• 4.5 基于加权分层和关联规则的最短路径算法设计57-58
• 4.6 本章小结58-60
• 第五章 最短路径快速搜索算法验证与具体应用60-74
• 5.1 Hadoop集群实验平台搭建60-63
• 5.1.1 安装Ubuntu / SSH60
• 5.1.2 安装Java运行环境60-61
• 5.1.3 安装Hadoop平台61
• 5.1.4 Hadoop集群部署61-63
• 5.2 最短路径搜索算法的验证63-71
• 5.2.1 算法评价指标63-64
• 5.2.2 算法测试与分析64-70
• 5.2.3 算法有效性能对比总结70-71
• 5.3 最短路径快速搜索算法的具体应用71-73
• 5.4 本章小结73-74
• 结论与展望74-76
• 参考文献76-81
• 攻读硕士学位期间取得的研究成果81-82
• 致谢82-83
• 附件83

【相似文献】

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

1 任刚;张永;周竹萍;;交通建模中的最短路径算法分析与测试[J];中国科技论文在线;2009年10期

2 康太平;张晓刚;王宗峰;何尚录;;基于k短路径算法的多目标最短路径算法[J];常州工学院学报;2011年Z1期

3 王苏男，，宋伟，姜文生;最短路径算法的比较[J];系统工程与电子技术;1994年05期

4 伍贝妮;;两种分级网络最短路径算法(一)[J];江苏航空;2000年04期

5 伍贝妮;;两种分级网络最短路径算法(二)[J];江苏航空;2001年01期

6 余为波;吴晓光;王涛;陈立;周巍;;基于最短路径算法的舰船通道逃逸路线研究[J];中国舰船研究;2008年02期

7 杨争;;基于分区域最短路径算法的警力调配系统[J];重庆理工大学学报(自然科学版);2010年06期

8 周培德;多面体面上任意两点间最短路径算法[J];北京理工大学学报;2005年04期

9 杨天石;刘晓东;于小平;;城市道路最短路径算法的研究[J];长春工程学院学报(自然科学版);2006年02期

10 王昊;;一种电子地图最短路径算法研究[J];硅谷;2009年05期

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

1 王闯;董志江;;最短路径算法[A];吉林省测绘学会2008年学术年会论文集（下）[C];2008年

2 唐小勇;程琳;徐上;;考虑转向延误最短路径算法及实现[A];2007第三届中国智能交通年会论文集[C];2007年

3 陈再春;张云青;潘伯鸣;;最短路径算法在公交查询中的实现[A];首届长三角科技论坛数字区域建设与地理空间技术论坛优秀论文集[C];2004年

4 罗飞;魏开平;万润泽;;复杂网络中最短路径算法的研究及应用[A];2006全国复杂网络学术会议论文集[C];2006年

5 王明福;彭群生;;基于编码图的求解最短路径算法[A];中国计算机图形学进展2008--第七届中国计算机图形学大会论文集[C];2008年

6 孙绍河;朱瑞艳;;GIS中最短路径算法的研究[A];第二届“测绘科学前沿技术论坛”论文精选[C];2010年

7 张惠谦;;电信规划最短路径算法的Excel宏实现[A];中国通信学会信息通信网络技术委员会2005年年会论文集[C];2005年

8 王冬;张丽果;杜慧敏;韩俊刚;;基于R-Torus结构和最短路径算法的NoC建模[A];全国第19届计算机技术与应用（CACIS）学术会议论文集（上册）[C];2008年

9 冯盼盼;蔺宏伟;于金辉;;投影法生成网格上的路径[A];第六届全国几何设计与计算学术会议论文集[C];2013年

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

1 廖远;一对一最短路径算法研究及车载导航系统设计[D];南昌大学;2012年

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

1 吕志超;面向资源优化配置的集群航天器网络拓扑管理研究[D];哈尔滨工业大学;2015年

2 汤博蔚;基于云计算的智能交通系统[D];南京邮电大学;2015年

3 尹伊伊;基于A*算法的多目标和约束条件下的k优换乘方案研究[D];中国铁道科学研究院;2015年

4 罗丽虹;考虑转向限制的路网中最短路径算法研究[D];清华大学;2015年

5 郭东;基于Virtools的煤矿井下逃生系统的研究[D];太原理工大学;2016年

6 吴友宝;Hadoop平台下基于路网加权分层和关联规则的最短路径算法研究[D];华南理工大学;2016年

7 邓礼礼;求图中受限制的所有最短路径算法的分析与研究[D];华东师范大学;2009年

8 杨蔓;最短路径算法在煤矿安全分区分析中的应用研究[D];西安科技大学;2009年

9 张志敏;手机导航系统中最短路径算法的优化与实现[D];西北大学;2011年

10 王世明;典型城市路网中最短路径算法研究及实现[D];山东大学;2012年

本文编号：670310