基于預(yù)處理的交通網(wǎng)最短路徑實時查詢研究.pdf

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

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

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