隨著GPS設(shè)備的普及,基于軌跡搜索的路徑規(guī)劃技術(shù)逐漸成為一個熱門研究課題。給出一組有序的查詢點,為了挖掘出先前用戶對于路徑選擇的經(jīng)驗,傳統(tǒng)算法致力于搜索出距離查詢點最近的軌跡。然而這些軌跡往往不能滿足用戶的需求,它們存在兩大問題。第一,這些軌跡可能只靠近部分查詢點,而距離其余查詢點較遠(yuǎn);第二,這些軌跡可能經(jīng)過了查詢點以外的其他地點。如果用戶沿著這些軌跡行駛,問題一會導(dǎo)致用戶找不到某些查詢點,問題二會導(dǎo)致用戶承受額外的開銷。本文針對以上兩個問題提出一種新的模型,稱為基于軌跡分片的路徑規(guī)劃方法（RPBTS）。給出一系列查詢點,首先將這些查詢點轉(zhuǎn)換成它們附近的道路,找出相交于這些道路的軌跡片段,并利用這些片段拼接出行車路徑。這樣,可以保證得到的路徑接近每一個查詢點。此外,本文還提出基于方差的方法用于判斷軌跡片段在經(jīng)過兩個連續(xù)查詢點時是否存在異常行為。通過排除異常軌跡片段,可以保證得到的路徑在兩個連續(xù)查詢點之間沒有去往其他地點。接著,本文提出RPBTS的基礎(chǔ)解決方案,并且引入貪心算法的思想以提高算法效率。然后,本文提出三種優(yōu)化方法以進(jìn)一步提高算法效率。第一,基于網(wǎng)格索引的優(yōu)化方法,該方法可以快... 

【文章來源】：杭州電子科技大學(xué)浙江省

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

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

【部分圖文】：

T-Drive軌跡數(shù)據(jù)集分布

[57]由中科院軟件所基礎(chǔ)軟件中心信息及新型計算研究室提供。圖3.13展示了T-Drive軌跡數(shù)據(jù)集匹配到該路網(wǎng)之后的結(jié)果。該圖與圖3.11中的分布基本吻合，證明了該地圖數(shù)據(jù)的正確性。0 2 4 6 8 10 1200.050.10.150.20.250.30.35minutesproportion0 1000 2000 3000 4000 5000 6000 7000 800000.10.20.30.40.50.60.7metersproportion

地標(biāo)分布不均勻。提取top-k熱門的路徑作為地標(biāo)并不合理。本文嘗試提取最熱門的20602個路段作為地標(biāo)，并在圖4.2中展示了其分布情況。從圖中可以看出，地標(biāo)普遍集中在市中心。當(dāng)查詢點iq 分布在郊區(qū)時，其附近往往不存在地標(biāo)，查詢點不能被轉(zhuǎn)換成地標(biāo)，那么查詢路段序列QR 并不會因此減少。而當(dāng)查詢點 位于市區(qū)時，其附近存在過多的路標(biāo)，算法需要額外開銷去獲取距離查詢點最近的路標(biāo)。因此，在實際應(yīng)用中，只使用基于地標(biāo)的優(yōu)化方法，對GA算法的提高作用并不明顯。圖4.2：Top-20602地標(biāo)分布為解決查詢點轉(zhuǎn)換效率低和地標(biāo)分布不均勻的問題，本節(jié)將介紹網(wǎng)格索引，并在此基礎(chǔ)上提出區(qū)域地標(biāo)概念。首先介紹網(wǎng)格索引的構(gòu)建過程。例如在圖4.3中，在路網(wǎng)上構(gòu)建一些網(wǎng)格。網(wǎng)格索引的左上角為原點，每個格子的對角線長度為b 。借助網(wǎng)格索引，就能通過兩步快速找出滿足 ( , )i i bdist r q 的路段。第一，快速定位查詢點。網(wǎng)絡(luò)索引的左上角為原點，即坐標(biāo)為(0,0)。假設(shè)每個格子的邊長為1

【參考文獻(xiàn)】：
期刊論文
[1]一種基于LCSS的相似車輛軌跡查找方法[J]. 裴劍,彭敦陸.  小型微型計算機(jī)系統(tǒng). 2016(06)
[2]基于GPS軌跡數(shù)據(jù)的地圖匹配算法[J]. 李清泉,黃練.  測繪學(xué)報. 2010(02)
[3]基于編輯距離的軌跡相似性度量[J]. 劉坤,楊杰.  上海交通大學(xué)學(xué)報. 2009(11)

碩士論文
[1]基于Voronoi圖的路網(wǎng)軌跡數(shù)據(jù)查詢技術(shù)研究[D]. 陳宇.杭州電子科技大學(xué) 2015



本文編號：3282688