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