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

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

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

【參考文獻(xiàn)】

相關(guān)期刊論文 前2條

1 許佳捷;鄭凱;池明e

本文編號(hào)：2680454