基于預處理的交通網最短路徑實時查詢研究.pdf

1、最短路徑問題是圖論與算法設計中的經典問題，同時也在路徑規(guī)劃、物流規(guī)劃、GPS導航、社交網絡、基于位置的服務(LBS)等現實世界的應用中扮演著重要的角色。交通路網上最短路徑問題由最短路徑問題衍生而來，特點為交通網數據規(guī)模大（如北京市主干路網就包含了10萬個頂點與10萬條邊），計算請求頻繁且實時性要求很高，傳統(tǒng)的最短路徑算法并不能滿足計算需求。
　　“預處理——查詢”模型是一種交通路網上最短路徑問題的兩階段方法。在第一階段對數據進行預

2、處理，包括獲得待使用的中間數據，以降低問題的求解難度;第二階段被稱為查詢階段，給定查詢請求的源點與目標點，每個請求須在極短時間內進行響應。兩階段的想法源自路網是靜態(tài)的，因此預處理階段可以僅執(zhí)行一次，其結果可以應對相同路網上大規(guī)模的查詢請求。
　　本文主要工作有:
　　1，基于預處理——查詢模型的幾種點到點最短路徑算法性能分析
　　本文針對“預處理——查詢”模型上的兩類算法——空間相干為基礎的方法和頂點重要性為基礎的方法

3、，選出兩類方法中具有代表性的算法，就預處理時間、空間消耗、查詢效率進行分析比較。
　　2，針對一種基于代表元的有效最短路徑近似算法，對代表元選取策略進行研究
　　由于代表元的選取策略直接影響近似算法的求解精度，因此如何對路網進行區(qū)域劃分、如何在區(qū)域中分配代表元成為了算法是否高效的關鍵點。本文將結合已提出的高效劃分方案，提出一種適合最短路徑近似算法的劃分策略，并分析其與求解精度之間的聯系。
　　3，通過模擬真實環(huán)境下路網