發(fā)布時間：2022-01-12 17:49

　　隨著經(jīng)濟(jì)的發(fā)展,城市道路建設(shè)也日漸完善。然而城市化進(jìn)程的飛快加速,使得道路建設(shè)的速度仍趕不上人民對交通的需求的增長速度,而道路交通作為國民經(jīng)濟(jì)的基礎(chǔ)設(shè)施,對國家的經(jīng)濟(jì)發(fā)展起著重要作用,因此,城市道路交通的協(xié)調(diào)與優(yōu)化變得十分重要。優(yōu)化出行路線是緩解交通壓力的有效手段,也是當(dāng)前世界各國的研究熱點。傳統(tǒng)的路徑推薦方法通常從路徑距離或行程耗時等方面考慮,將路網(wǎng)轉(zhuǎn)化為圖,根據(jù)深度優(yōu)先搜索或廣度優(yōu)先搜索對路徑進(jìn)行窮舉,計算得出符合要求的最優(yōu)路徑。然而由于它需要對路徑進(jìn)行窮舉,因此在路網(wǎng)龐大的情況下往往成為困難問題,無法滿足計算效率上的需求。并且,在有海量GPS歷史數(shù)據(jù)做為支撐的情況下,可以結(jié)合數(shù)據(jù)挖掘?qū)β窂竭M(jìn)行推薦。因此,本文結(jié)合海量GPS歷史軌跡數(shù)據(jù),從路徑使用頻率的角度出發(fā),引入頻繁模式挖掘,對兩點間的路徑進(jìn)行推薦。在數(shù)據(jù)預(yù)處理階段,本文首先針對所使用的開源GPS數(shù)據(jù)的特點,提出了有效的數(shù)據(jù)清洗方法,對缺陷數(shù)據(jù)、定位點信息遺漏以及采樣稀疏的軌跡數(shù)據(jù)進(jìn)行識別與過濾,同時對軌跡中的漂移數(shù)據(jù)進(jìn)行了平滑處理,從而保證了軌跡數(shù)據(jù)信息的完整與豐富。其次,本文從軌跡形態(tài)出發(fā),通過計算軌跡的方向角對路網(wǎng)路口進(jìn)... 

【文章來源】：西南交通大學(xué)四川省 211工程院校 教育部直屬院校

【文章頁數(shù)】：69 頁

【學(xué)位級別】：碩士

【部分圖文】：

道路交叉點判斷示意圖

利用相交路口定位點密度更大的特點，通過對固定范圍內(nèi)的道路自動識別路口交叉點。但第一步中滾動式聚類只在定位點嚴(yán)格以有較高的效率，而一般情況下，定位點的存儲在空間上是呈雜定位點 p 進(jìn)行一次聚類，就需要對所有定位點進(jìn)行一次遍歷才離閾值的定位點。假設(shè)定位點個數(shù)為 N，最終聚合得到的道路作的時間復(fù)雜度約為 O(nN)。于基于密度的道路交叉點識別算法外，文獻(xiàn)[43]中提出了一種基點提取算法，利用于道路之間的方向角來識別道路交叉點。它的跡點進(jìn)行預(yù)處理，對于鄰域密度過大、相鄰點運動方向角過大，利用快速滑動擬合算法對連續(xù)的空間軌跡數(shù)據(jù)進(jìn)行擬合，在引入一個集合對已識別過的點進(jìn)行保存，在遍歷點的過程中不免對點的重復(fù)計算；最后運用 K-階夾角求解擬合的方向向量，勢進(jìn)行分析，當(dāng)某一點的 K-階夾角大于給定閾值時，將此點加后對可能的路口進(jìn)行聚合，提取出路口。算法執(zhí)行流程如圖 2

路點密度的方法，對原始 GPS 定位點數(shù)據(jù)的采樣密度有更好的包容性，但其的根據(jù)滑動擬合來計算 K-階夾角的方法較為復(fù)雜。.2 路徑推薦算法隨著城市化進(jìn)程的飛快加速，城市道路的規(guī)模也在不斷地龐大，兩點之間來越復(fù)雜交錯。這在給人民生活帶來便捷的同時，也給從兩點間的繁多道路最優(yōu)路徑帶來了更大的困難與挑戰(zhàn)。如何快速地向用戶推薦最適宜的路徑成重要的課題。針對此問題，有許多學(xué)科領(lǐng)域的學(xué)者進(jìn)行對此進(jìn)行了研究，本些研究做出一定的歸納與分析。2.1 基于圖論的最短路徑選擇基于圖論的最短路徑選擇是提出較早也較為經(jīng)典的一類算法。它的問題原設(shè)存在一個連通結(jié)構(gòu)如下圖 2-3(a)左所示，在給定的兩個位置(圖中黑點所示多條可達(dá)路線，如何從中選擇最短的路徑。

【參考文獻(xiàn)】：
期刊論文
[1]SA*:一種多線程路徑規(guī)劃算法[J]. 孫經(jīng)緯,孫廣中,詹石巖,毛睿,周英華.  地球信息科學(xué)學(xué)報. 2018(06)
[2]基于混合多種群自適應(yīng)蟻群算法的無人機(jī)航路規(guī)劃[J]. 李增,顧文燦,張宏亮,魏斌,黃雷.  計算機(jī)測量與控制. 2015(05)
[3]基于步行GPS軌跡的路網(wǎng)提取方法[J]. 歐陽鴻,劉建勛,劉毅志,廖祝華,陳佘喜.  計算機(jī)與現(xiàn)代化. 2014(02)
[4]遺傳算法研究綜述[J]. 葛繼科,邱玉輝,吳春明,蒲國林.  計算機(jī)應(yīng)用研究. 2008(10)
[5]GIS支持下的城市交通網(wǎng)絡(luò)最短路徑研究[J]. 王行風(fēng),賈凌.  計算機(jī)與現(xiàn)代化. 2005(03)
[6]最短路徑算法:分類體系與研究進(jìn)展[J]. 陸鋒.  測繪學(xué)報. 2001(03)
[7]模擬退火算法綜述[J]. 謝云.  計算機(jī)應(yīng)用研究. 1998(05)
[8]關(guān)于最短路徑的SPFA快速算法[J]. 段凡丁.  西南交通大學(xué)學(xué)報. 1994(02)

碩士論文
[1]基于GPS數(shù)據(jù)的地圖拓?fù)涮崛〉年P(guān)鍵技術(shù)與應(yīng)用研究[D]. 王玉林.西安理工大學(xué) 2018
[2]基于GPS數(shù)據(jù)的交通行為及出租車行駛路線推薦研究[D]. 杜娜娜.北京郵電大學(xué) 2018
[3]多影響因素下的導(dǎo)航路網(wǎng)數(shù)據(jù)路徑規(guī)劃研究[D]. 孔祥麗.武漢大學(xué) 2018
[4]分層道路的頻繁路徑查詢算法研究[D]. 葛恩泉.杭州電子科技大學(xué) 2016
[5]基于GPS軌跡的道路拓?fù)錁?gòu)建和路徑選擇方法研究[D]. 譚康.湖南科技大學(xué) 2015
[6]大規(guī)模動態(tài)自適應(yīng)圖劃分算法[D]. 許金鳳.寧波大學(xué) 2015
[7]城市客流分布與出租車出行路線推薦算法的研究[D]. 孔蕙心.北京郵電大學(xué) 2015
[8]基于Pick-up樹的路徑推薦研究[D]. 胡昊然.南京大學(xué) 2013



本文編號：3585200