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

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

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

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