本文關(guān)鍵詞：Hadoop平臺下基于路網(wǎng)加權(quán)分層和關(guān)聯(lián)規(guī)則的最短路徑算法研究

  更多相關(guān)文章： 最短路徑算法 加權(quán)分層 關(guān)聯(lián)規(guī)則 Hadoop

【摘要】：傳統(tǒng)Dijkstra、Floyd、A*等算法適合于求解具有串行化、計算復雜度不高、存儲消耗不大等特性的最短路徑問題,在大規(guī)模復雜路網(wǎng)中的搜索效率不高。伴隨著大數(shù)據(jù)技術(shù)的熱潮,如何運用分布式存儲、并行化計算和強大的分析處理能力實現(xiàn)快速、準確地求解最短路徑問題,是交通領(lǐng)域?qū)W者關(guān)注和研究的重點之一。因此,本文基于Hadoop大數(shù)據(jù)平臺的HDFS模塊,分布式存儲海量浮動車數(shù)據(jù);基于新一代YARN計算框架,并行化迭代求解最短路徑,減少算法的時間復雜度。在此基礎上,分析處理交通路網(wǎng)加權(quán)分層所需要的動態(tài)、靜態(tài)道路屬性數(shù)據(jù),并提取關(guān)聯(lián)規(guī)則方法挖掘交叉口間關(guān)聯(lián)性的浮動車出行路徑集。然后,采用層次分析法對道路等級、車道數(shù)量、路段長度、紅綠燈、收費站、平均行程速度和通行次數(shù)等影響因素進行權(quán)重加權(quán)計算,從而實現(xiàn)分層分區(qū),從空間拓撲結(jié)構(gòu)上簡化路網(wǎng)搜索規(guī)模。接著,使用關(guān)聯(lián)規(guī)則方法挖掘海量浮動車的出行路徑數(shù)據(jù),尋找分區(qū)內(nèi)各交叉口間的強關(guān)聯(lián)規(guī)則,減少搜索的節(jié)點數(shù)目。最后,搭建Hadoop集群實驗平臺,對比分析傳統(tǒng)A*算法、基于YARN并行化迭代計算模型的最短路徑算法、Hadoop平臺下基于加權(quán)分層和關(guān)聯(lián)規(guī)則的最短路徑算法等的有效性能指標。實驗結(jié)果表明,該算法在搜索速度上具有明顯的優(yōu)勢,而且求解的最短路徑結(jié)果符合出行者的行駛習慣,滿足居民快捷出行的需求。
【關(guān)鍵詞】：最短路徑算法 加權(quán)分層 關(guān)聯(lián)規(guī)則 Hadoop
【學位授予單位】：華南理工大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：U491
【目錄】：

• 摘要5-6
• Abstract6-10
• 第一章 緒論10-18
• 1.1 研究背景和意義10
• 1.2 國內(nèi)外研究現(xiàn)狀分析10-14
• 1.2.1 國外研究現(xiàn)狀10-12
• 1.2.2 國內(nèi)研究現(xiàn)狀12-14
• 1.2.3 研究現(xiàn)狀分析總結(jié)14
• 1.3 研究內(nèi)容14-15
• 1.4 技術(shù)路線與章節(jié)安排15-17
• 1.4.1 技術(shù)路線15-16
• 1.4.2 章節(jié)安排16-17
• 1.5 本章小結(jié)17-18
• 第二章 交通路網(wǎng)最短路徑算法研究18-26
• 2.1 最短路徑概述18-19
• 2.2 最短路徑算法分類體系19-21
• 2.2.1 問題類型19-20
• 2.2.2 路網(wǎng)特性20-21
• 2.2.3 求解技術(shù)21
• 2.3 交通路網(wǎng)常用最短路徑算法分析21-25
• 2.3.1 Dijkstra算法22
• 2.3.2 Floyd算法22-23
• 2.3.3 A*算法23-25
• 2.4 本章小結(jié)25-26
• 第三章 基于Hadoop大數(shù)據(jù)平臺的最短路徑算法研究26-38
• 3.1 交通大數(shù)據(jù)26
• 3.2 交通數(shù)據(jù)挖掘技術(shù)26-28
• 3.2.1 數(shù)據(jù)挖掘定義26-27
• 3.2.2 交通數(shù)據(jù)挖掘算法27
• 3.2.3 交通數(shù)據(jù)挖掘技術(shù)流程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 本章小結(jié)37-38
• 第四章 基于加權(quán)分層和關(guān)聯(lián)規(guī)則的最短路徑算法研究38-60
• 4.1 交通路網(wǎng)概述38
• 4.2 交通路網(wǎng)分層策略38-42
• 4.2.1 交通路網(wǎng)分層模型描述38-41
• 4.2.2 交通路網(wǎng)分層原則41
• 4.2.3 交通路網(wǎng)分層數(shù)量41-42
• 4.3 交通路網(wǎng)加權(quán)分層42-52
• 4.3.1 層次分析法概述42-45
• 4.3.2 交通路網(wǎng)權(quán)重確定45-48
• 4.3.3 交通路網(wǎng)分層分區(qū)48-52
• 4.4 分區(qū)交叉口間關(guān)聯(lián)規(guī)則挖掘52-57
• 4.4.1 關(guān)聯(lián)規(guī)則概述52-53
• 4.4.2 交叉口間關(guān)聯(lián)規(guī)則挖掘模型53-57
• 4.5 基于加權(quán)分層和關(guān)聯(lián)規(guī)則的最短路徑算法設計57-58
• 4.6 本章小結(jié)58-60
• 第五章 最短路徑快速搜索算法驗證與具體應用60-74
• 5.1 Hadoop集群實驗平臺搭建60-63
• 5.1.1 安裝Ubuntu / SSH60
• 5.1.2 安裝Java運行環(huán)境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 算法有效性能對比總結(jié)70-71
• 5.3 最短路徑快速搜索算法的具體應用71-73
• 5.4 本章小結(jié)73-74
• 結(jié)論與展望74-76
• 參考文獻76-81
• 攻讀碩士學位期間取得的研究成果81-82
• 致謝82-83
• 附件83

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 任剛;張永;周竹萍;;交通建模中的最短路徑算法分析與測試[J];中國科技論文在線;2009年10期

2 康太平;張曉剛;王宗峰;何尚錄;;基于k短路徑算法的多目標最短路徑算法[J];常州工學院學報;2011年Z1期

3 王蘇男，，宋偉，姜文生;最短路徑算法的比較[J];系統(tǒng)工程與電子技術(shù);1994年05期

4 伍貝妮;;兩種分級網(wǎng)絡最短路徑算法(一)[J];江蘇航空;2000年04期

5 伍貝妮;;兩種分級網(wǎng)絡最短路徑算法(二)[J];江蘇航空;2001年01期

6 余為波;吳曉光;王濤;陳立;周巍;;基于最短路徑算法的艦船通道逃逸路線研究[J];中國艦船研究;2008年02期

7 楊爭;;基于分區(qū)域最短路徑算法的警力調(diào)配系統(tǒng)[J];重慶理工大學學報(自然科學版);2010年06期

8 周培德;多面體面上任意兩點間最短路徑算法[J];北京理工大學學報;2005年04期

9 楊天石;劉曉東;于小平;;城市道路最短路徑算法的研究[J];長春工程學院學報(自然科學版);2006年02期

10 王昊;;一種電子地圖最短路徑算法研究[J];硅谷;2009年05期

中國重要會議論文全文數(shù)據(jù)庫 前9條

1 王闖;董志江;;最短路徑算法[A];吉林省測繪學會2008年學術(shù)年會論文集（下）[C];2008年

2 唐小勇;程琳;徐上;;考慮轉(zhuǎn)向延誤最短路徑算法及實現(xiàn)[A];2007第三屆中國智能交通年會論文集[C];2007年

3 陳再春;張云青;潘伯鳴;;最短路徑算法在公交查詢中的實現(xiàn)[A];首屆長三角科技論壇數(shù)字區(qū)域建設與地理空間技術(shù)論壇優(yōu)秀論文集[C];2004年

4 羅飛;魏開平;萬潤澤;;復雜網(wǎng)絡中最短路徑算法的研究及應用[A];2006全國復雜網(wǎng)絡學術(shù)會議論文集[C];2006年

5 王明福;彭群生;;基于編碼圖的求解最短路徑算法[A];中國計算機圖形學進展2008--第七屆中國計算機圖形學大會論文集[C];2008年

6 孫紹河;朱瑞艷;;GIS中最短路徑算法的研究[A];第二屆“測繪科學前沿技術(shù)論壇”論文精選[C];2010年

7 張惠謙;;電信規(guī)劃最短路徑算法的Excel宏實現(xiàn)[A];中國通信學會信息通信網(wǎng)絡技術(shù)委員會2005年年會論文集[C];2005年

8 王冬;張麗果;杜慧敏;韓俊剛;;基于R-Torus結(jié)構(gòu)和最短路徑算法的NoC建模[A];全國第19屆計算機技術(shù)與應用（CACIS）學術(shù)會議論文集（上冊）[C];2008年

9 馮盼盼;藺宏偉;于金輝;;投影法生成網(wǎng)格上的路徑[A];第六屆全國幾何設計與計算學術(shù)會議論文集[C];2013年

中國博士學位論文全文數(shù)據(jù)庫 前1條

1 廖遠;一對一最短路徑算法研究及車載導航系統(tǒng)設計[D];南昌大學;2012年

中國碩士學位論文全文數(shù)據(jù)庫 前10條

1 呂志超;面向資源優(yōu)化配置的集群航天器網(wǎng)絡拓撲管理研究[D];哈爾濱工業(yè)大學;2015年

2 湯博蔚;基于云計算的智能交通系統(tǒng)[D];南京郵電大學;2015年

3 尹伊伊;基于A*算法的多目標和約束條件下的k優(yōu)換乘方案研究[D];中國鐵道科學研究院;2015年

4 羅麗虹;考慮轉(zhuǎn)向限制的路網(wǎng)中最短路徑算法研究[D];清華大學;2015年

5 郭東;基于Virtools的煤礦井下逃生系統(tǒng)的研究[D];太原理工大學;2016年

6 吳友寶;Hadoop平臺下基于路網(wǎng)加權(quán)分層和關(guān)聯(lián)規(guī)則的最短路徑算法研究[D];華南理工大學;2016年

7 鄧禮禮;求圖中受限制的所有最短路徑算法的分析與研究[D];華東師范大學;2009年

8 楊蔓;最短路徑算法在煤礦安全分區(qū)分析中的應用研究[D];西安科技大學;2009年

9 張志敏;手機導航系統(tǒng)中最短路徑算法的優(yōu)化與實現(xiàn)[D];西北大學;2011年

10 王世明;典型城市路網(wǎng)中最短路徑算法研究及實現(xiàn)[D];山東大學;2012年

本文編號：670310