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

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

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

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