2147
18
0
2019-11-14 13:13:54
2019-11-14
馬慧,湯庸,梁瑞仕.公交網(wǎng)絡(luò)下的一種費用限制最小時態(tài)路徑查詢索引.軟件學(xué)報,2019,30(11):3469?3485.
http://www.jos.org.cn/jos/ch/reader/create_pdf.aspx?file_no=5623&journal_id=jos
摘 要: 私人交通網(wǎng)絡(luò)下的最短路徑查詢主要考慮路徑長度、行駛時間等因素,而公共交通網(wǎng)絡(luò)下的路徑查詢需 要考慮路徑上相鄰的邊的時間順序約束以及路徑的費用.研究了公共交通網(wǎng)絡(luò)下 3 種查詢:給定起點、終點、時間 區(qū)間和費用上限,查找在時間區(qū)間內(nèi)不超過費用上限的最早到達路徑、最晚出發(fā)路徑和最短耗時路徑.首先給出一 種 Dijkstra 變種算法 Dijk-CCMTP,在此基礎(chǔ)上給出 3 類查詢的查詢算法.然后提出一種高效的索引結(jié)構(gòu) ACCTL(approximate cost constrained time labelling).ACCTL 采用 Dijk-CCMTP 對圖中的每個頂點預(yù)先計算部分從 該頂點出發(fā)的和到達該頂點的基本路徑.對于任意從起點 s 到終點 d 的查詢,可以采用類似數(shù)據(jù)庫表連接的方式從 ACCTL 中連接從 s 出發(fā)的和到達 d 的路徑生成近似解,避免遍歷原圖搜索路徑.ACCTL 建立索引的時間復(fù)雜度是 O(|V|?Δmax?|E|?(log|E|+Δmax)),其中,|V|表示頂點數(shù),|E|表示邊數(shù),Δmax 表示頂點的最大度數(shù).實驗驗證 ACCTL 索引支持 的查詢速度比 Dijkstra 的變種算法的查詢速度快 2~3 個數(shù)量級,并分析了影響建立索引時間和空間大小的因素.
