【摘要】：隨著移動智能設備的廣泛運用,基于位置服務(LBS)的應用得到了飛速發(fā)展,其中路徑規(guī)劃是基于位置服務的核心功能。路徑規(guī)劃系統(tǒng)的作用是為用戶提供一條查詢點間的優(yōu)質(zhì)路徑,提高出行效率。現(xiàn)有的路徑規(guī)劃系統(tǒng)以指標驅(qū)動,需要考慮路程、時間、費用等多個指標,但是對于多指標的綜合評估很難建立精確的模型,因此時常發(fā)生給出的路徑不符合用戶需求的情況。商業(yè)公司在提供服務的同時收集了大量的軌跡數(shù)據(jù),這些數(shù)據(jù)記錄了用戶的時空信息,反映了用戶的出行行為,具有較高的學習價值。很多研究都在嘗試利用軌跡數(shù)據(jù)來優(yōu)化路徑規(guī)劃的結果。不同于傳統(tǒng)的指標驅(qū)動的路徑規(guī)劃系統(tǒng),本文通過對收集到的原始采樣信息進行合理的處理及篩選,構建經(jīng)驗軌跡數(shù)據(jù)庫,用轉向概率、轉移概率兩種方法來量化經(jīng)驗軌跡數(shù)據(jù)庫中用戶的出行經(jīng)驗并計算產(chǎn)生經(jīng)驗路徑,最終將經(jīng)驗路徑推薦給用戶實現(xiàn)路徑規(guī)劃。最后我們在北京路網(wǎng)上設計并實現(xiàn)了基于經(jīng)驗路徑的路徑規(guī)劃系統(tǒng)。本文的主要貢獻可以概括為以下幾個方面:(1)給出了從原始采樣數(shù)據(jù)集中獲取經(jīng)驗軌跡的方法。該方法便于在分布式計算平臺上運用,滿足海量數(shù)據(jù)處理對算力的需求。(2)提出了用轉向概率、轉移概率兩種方法量化經(jīng)驗軌跡中的出行經(jīng)驗,并依據(jù)獲得的知識計算產(chǎn)生經(jīng)驗路徑。為了降低空間復雜度,進一步提出了基于分區(qū)的經(jīng)驗路徑的處理框架。(3)實現(xiàn)了基于經(jīng)驗路徑的路徑規(guī)劃系統(tǒng),并在真實數(shù)據(jù)集上進行試驗,通過與成熟的商業(yè)應用進行結果對比證明了該系統(tǒng)的實用性。
【圖文】：

索中h(n)相當于搜索的雷達，可以為搜索指明方向，對搜索域可視化時，如圖2-1所示A-Star算法通常會沿著目標方向搜索從而大大減少不必要的結點計算，因此h(n)預估代價的準確性會直接影響搜索的結果與性能。圖2-1 Dijkstra和A-Star搜索域?qū)Ρ?.1.2 Contraction Hierarchies算算法法Contraction Hierarchies(以下簡稱CH)算法[9]是一種圖上的索引技術。最短路徑問題可以通過經(jīng)典的算法如Dijkstra、A-Star等算法解決，，但在現(xiàn)今復雜的交通路網(wǎng)上這些經(jīng)典算法具有明顯的性能瓶頸，CH算法提出的目的是為了通過索引提高在大規(guī)模路網(wǎng)上進行路徑規(guī)劃的處理速度，在對路網(wǎng)的處理過程中引入了路網(wǎng)結點重要性的思想。對路網(wǎng)有向圖G = (N, E) 在預處理階段將所有的路口結點依據(jù)重要性進行排序，通常可以使用路口等級作為衡量結點重要性的標準，如果u<v則說明路口結點u的重要性小于路口結點v ,對于路徑<v,u,w>，當<v,u,w> 是v至w的最短路徑時可以通過捷徑邊<v,w> 來表示該條路徑，此時的u就是一個非重要路口結點

第二章 相關理論及技術 基于經(jīng)驗路徑的路徑規(guī)劃系統(tǒng)圖2-4 google map和用戶實際路徑相似性置工作環(huán)境的變化難以保證數(shù)據(jù)傳輸可靠性導致的數(shù)據(jù)缺失；國內(nèi)地圖數(shù)據(jù)坐標系問題導致的不同公司的GPS數(shù)據(jù)坐標表示標準各異，數(shù)據(jù)格式不統(tǒng)一；部分軌跡數(shù)據(jù)導出、備份導致的數(shù)據(jù)冗余問題等等。這些數(shù)據(jù)質(zhì)量問題導致原始軌跡數(shù)據(jù)不能直接使用，需要通過一些技術進行坐標轉換、數(shù)據(jù)校準、補全缺失數(shù)據(jù)后才能用于數(shù)據(jù)挖掘。一般而言，軌跡數(shù)據(jù)預處理主要包括數(shù)據(jù)清洗，軌跡分割，路網(wǎng)匹配[2, 29]這三個步驟。數(shù)據(jù)清洗(data cleaning)是把原始輸入的數(shù)據(jù)通過一系列的數(shù)據(jù)監(jiān)測和數(shù)據(jù)修復后轉換為干凈、可用數(shù)據(jù)的過程，并且去除軌跡中因為誤操作導致的冗余數(shù)據(jù)，冗余數(shù)據(jù)是指可以通過差值等計算導出的冗余采樣點或是由軟硬件設備異常導致的錯誤采樣點、缺失采樣點、不一致采樣點等。這種“問題“采樣點不僅占用了系統(tǒng)存儲、浪費了計算資源，還會極大的影響后續(xù)處理分析的結果[29]。現(xiàn)有的數(shù)據(jù)清洗方法主要是從單條軌跡的角度清洗數(shù)據(jù)，借鑒平滑曲線思想，使用軌跡清洗算法[30, 31]智能的選取少量具有“代表性“的采樣點，去除大量的冗余采樣，使得軌跡的完整時空投影依然能夠被有效表示。數(shù)據(jù)清洗的最終目的是提高數(shù)據(jù)質(zhì)量。軌跡分割(trajectory segmentation)是指對含有多次出行意圖的長軌跡進行合理切分
【學位授予單位】：蘇州大學
【學位級別】：碩士
【學位授予年份】：2018
【分類號】：TP391.3

【參考文獻】

相關期刊論文 前2條

1 許佳捷;鄭凱;池明e

本文編號：2680454