分層道路的頻繁路徑查詢算法研究.pdf

1、隨著移動(dòng)設(shè)備的普及，人們積累了大量的軌跡數(shù)據(jù)。基于軌跡的路徑推薦算法成為熱點(diǎn)的研究問題。頻繁路徑算法（MFP）是經(jīng)典的路徑推薦算法之一，它通過軌跡重構(gòu)權(quán)值圖，以每條邊被選擇的次數(shù)即頻繁度作為路徑權(quán)值，進(jìn)行路徑的推薦。MFP算法推薦的路徑雖然符合當(dāng)?shù)厝碎_車的習(xí)慣，但是它推薦的路徑可能包含過多的路口和過少的高等級(jí)路段（如高速路，快速路），并且算法的時(shí)間復(fù)雜度較大，實(shí)用性不強(qiáng)。為了解決MFP算法存在的問題，本文做了以下研究：
　　首先本

2、文提出了分層道路的頻繁路徑查詢算法（RLMFP）。該方法在MFP的基礎(chǔ)上，根據(jù)城市已有的道路級(jí)別規(guī)劃，引入了路網(wǎng)分層的思想，降低了算法的復(fù)雜度。算法根據(jù)每條道路自身的級(jí)別抽象出高等級(jí)道路網(wǎng)絡(luò)（快速路和高速路構(gòu)成的路網(wǎng)），通過高等級(jí)網(wǎng)絡(luò)利用廣度優(yōu)先遍歷算法進(jìn)行路網(wǎng)區(qū)域的劃分，使用樹結(jié)構(gòu)進(jìn)行分層網(wǎng)絡(luò)的存儲(chǔ)。然后算法通過分層網(wǎng)絡(luò)路徑推薦思想和MFP路徑算法進(jìn)行路徑的推薦。
　　接著本文采用基于嵌套哈希結(jié)構(gòu)的快速索引(FG)對(duì)RLMFP算

3、法展開了優(yōu)化，提出了RLMFPT算法。MFP算法是一個(gè)無方向的路徑查詢算法，在分層道路路徑算法中，它無法在低等級(jí)網(wǎng)絡(luò)選擇合適的升級(jí)點(diǎn)（高級(jí)網(wǎng)絡(luò)和低級(jí)網(wǎng)絡(luò)的交匯點(diǎn)）進(jìn)入高級(jí)路網(wǎng)，需要計(jì)算起始點(diǎn)到所有升級(jí)點(diǎn)的MFP路徑，這是造成RLMFP算法不穩(wěn)定的原因。FG通過軌跡構(gòu)建任意兩個(gè)區(qū)域內(nèi)的升級(jí)點(diǎn)索引結(jié)構(gòu)來使RLMFP算法具備選擇合適升級(jí)點(diǎn)的能力。FG的外層哈希表中，它以兩個(gè)路網(wǎng)區(qū)域ID的組合(假定為A區(qū)域內(nèi)的點(diǎn)前往B區(qū)域)為key，內(nèi)層哈希表

4、為value。內(nèi)層哈希表中，它以起始區(qū)域路網(wǎng)(這里為A)內(nèi)升級(jí)點(diǎn)為key，所有軌跡中滿足起點(diǎn)為區(qū)域A終點(diǎn)為區(qū)域B并且經(jīng)過該升級(jí)點(diǎn)的條件的軌跡總數(shù)作為value。
　　論文通過理論分析證明了以上兩個(gè)算法的合理性。論文在實(shí)際的出租車軌跡數(shù)據(jù)和模擬的軌跡數(shù)據(jù)上，通過實(shí)驗(yàn)說明RLMFP和RLMFPT算法推薦的路徑比MFP更加合理，同時(shí)具有更快的響應(yīng)速度。但是隨著地圖的增大，RLMFP算法的穩(wěn)定性不足，對(duì)于升級(jí)點(diǎn)的數(shù)量依賴性較大。而 RLM