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

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

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

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

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