基于GPS歷史軌跡的路徑規(guī)劃技術(shù)研究.pdf

1、隨著GPS設(shè)備的普及，基于軌跡搜索的路徑規(guī)劃技術(shù)逐漸成為一個(gè)熱門研究課題。給出一組有序的查詢點(diǎn)，為了挖掘出先前用戶對于路徑選擇的經(jīng)驗(yàn)，傳統(tǒng)算法致力于搜索出距離查詢點(diǎn)最近的軌跡。然而這些軌跡往往不能滿足用戶的需求，它們存在兩大問題。第一，這些軌跡可能只靠近部分查詢點(diǎn)，而距離其余查詢點(diǎn)較遠(yuǎn)；第二，這些軌跡可能經(jīng)過了查詢點(diǎn)以外的其他地點(diǎn)。如果用戶沿著這些軌跡行駛，問題一會導(dǎo)致用戶找不到某些查詢點(diǎn)，問題二會導(dǎo)致用戶承受額外的開銷。
　　本

2、文針對以上兩個(gè)問題提出一種新的模型，稱為基于軌跡分片的路徑規(guī)劃方法（RPBTS）。給出一系列查詢點(diǎn)，首先將這些查詢點(diǎn)轉(zhuǎn)換成它們附近的道路，找出相交于這些道路的軌跡片段，并利用這些片段拼接出行車路徑。這樣，可以保證得到的路徑接近每一個(gè)查詢點(diǎn)。此外，本文還提出基于方差的方法用于判斷軌跡片段在經(jīng)過兩個(gè)連續(xù)查詢點(diǎn)時(shí)是否存在異常行為。通過排除異常軌跡片段，可以保證得到的路徑在兩個(gè)連續(xù)查詢點(diǎn)之間沒有去往其他地點(diǎn)。
　　接著，本文提出RPBTS

3、的基礎(chǔ)解決方案，并且引入貪心算法的思想以提高算法效率。然后，本文提出三種優(yōu)化方法以進(jìn)一步提高算法效率。第一，基于網(wǎng)格索引的優(yōu)化方法，該方法可以快速定位到查詢點(diǎn)附近的路段；第二，基于區(qū)域地標(biāo)的優(yōu)化方法，該方法將查詢點(diǎn)轉(zhuǎn)換成其附近的熱門路段；第三，基于隨機(jī)選擇的優(yōu)化方法，該方法有效地減少了多方案擇優(yōu)的開銷。這些優(yōu)化方法合理地降低了算法的復(fù)雜度，并且使得整個(gè)規(guī)劃過程更加符合人們的常識。
　　最后，本文使用微軟研究院提供的T-drive軌