馬 慧 , 湯 庸 , 梁瑞仕

1(電子科技大學(xué) 中山學(xué)院 計(jì)算機(jī)學(xué)院,廣東 中山 528400)

2(華南師范大學(xué) 計(jì)算機(jī)學(xué)院,廣東 廣州 510631)

公共交通網(wǎng)絡(luò)下的路徑查詢是地圖服務(wù)的一個(gè)重要應(yīng)用.私人交通網(wǎng)絡(luò)下的路徑查詢通常用路徑長(zhǎng)度、行駛時(shí)間、費(fèi)用等某方面的因素來衡量一條路徑的長(zhǎng)度;而公交網(wǎng)絡(luò)查詢需要考慮交通工具換乘的問題,因此需要考慮路徑上的相鄰邊之間的時(shí)間順序.此外,費(fèi)用也是公交網(wǎng)絡(luò)路徑查詢所要考慮的重要因素.例如,從廣州直飛到洛杉磯雖然耗時(shí)短但價(jià)格昂貴,用戶更想找到一條便宜的、可中途換乘的、旅途時(shí)間稍長(zhǎng)的路線.本文研究這樣的問題:一個(gè)旅行者計(jì)劃乘坐公共交通工具出行,他的預(yù)算有限,他想知道在不超過預(yù)算的前提下:(1)他計(jì)劃在t時(shí)刻或之后出發(fā),最早什么時(shí)候能到達(dá)?(2)他計(jì)劃在t′時(shí)刻或之前到達(dá),最晚需要什么時(shí)候出發(fā)?(3)他可以在t時(shí)刻或之后出發(fā),希望在t′時(shí)刻或之前到達(dá),想找一條旅途時(shí)間最短的路徑.上述3 種查詢分別稱為帶費(fèi)用限制的最早到達(dá)路徑查詢、最晚出發(fā)路徑查詢和最短耗時(shí)路經(jīng)查詢.3 種查詢的共同點(diǎn)是在費(fèi)用限制的前提下查找最快的路徑,因此下文統(tǒng)稱為帶費(fèi)用限制的最小時(shí)態(tài)路徑查詢.

與本文工作最相關(guān)的是文獻(xiàn)[1].Biswas 等人提出了在時(shí)間信息圖下求解帶費(fèi)用限制的最短路徑問題.他們假設(shè)圖中的每條邊附有出發(fā)時(shí)刻、到達(dá)時(shí)刻、長(zhǎng)度和費(fèi)用值,求解不超過費(fèi)用上限的、路徑上相鄰的邊滿足時(shí)間順序的、長(zhǎng)度最短的路徑.文獻(xiàn)[1]提出的兩種查詢算法的時(shí)間復(fù)雜度分別是O(|E|?log|E|+|E|?Δmax?Lopt)和O(|E|?P?(tβ-tα)),其中,|E|表示圖的邊數(shù),Δmax表示頂點(diǎn)的最大度數(shù),Lopt表示最短路徑的長(zhǎng)度,P表示費(fèi)用上限,tα和tβ分別表示查詢時(shí)間區(qū)間的下界和上界.第1 種算法的時(shí)間復(fù)雜度依賴于圖的規(guī)模,不適合大規(guī)模圖的實(shí)時(shí)查詢;第2 種算法的時(shí)間復(fù)雜度依賴于路徑長(zhǎng)度、費(fèi)用上限、查詢時(shí)間區(qū)間等數(shù)值,當(dāng)數(shù)值較大時(shí),顯然查詢速度變慢.此外,文獻(xiàn)[1]的實(shí)驗(yàn)中采用通過一條邊的時(shí)間作為邊的長(zhǎng)度,查找不超過費(fèi)用限制的最短路徑返回旅途中乘坐交通工具所花的總時(shí)間,而等待交通工具的時(shí)間并未計(jì)入,這在路徑規(guī)劃中是不合理的.Yang 等人用分段函數(shù)表示通過一條邊的費(fèi)用依賴于出發(fā)時(shí)刻變化[2],在這種連續(xù)時(shí)間模型上,提出了一種給定查詢時(shí)間區(qū)間的最小費(fèi)用路徑查詢方法Tow-Step;在文獻(xiàn)[3]中,Yang 等人還進(jìn)一步假設(shè)通過每條邊的時(shí)間也依賴于出發(fā)時(shí)刻變化,提出了Tow-Step 的改進(jìn)算法.Tow-Step 算法允許路徑在某個(gè)頂點(diǎn)上等待至恰當(dāng)?shù)臅r(shí)刻才繼續(xù)前行,以達(dá)到路徑費(fèi)用最小.這種模型更適用在私人交通網(wǎng)絡(luò),因?yàn)楣步煌ㄟ\(yùn)行有固定的時(shí)間表,不能在某個(gè)地方等待任意的時(shí)間.此外,Two-Step 算法也是基于原圖上做查詢,時(shí)間復(fù)雜度是O(k?|V|?log|V|+|E|?k2?logk),其中,|V|表示頂點(diǎn)數(shù),|E|表示邊數(shù),k表示邊上時(shí)間分區(qū)的段數(shù).同樣地,該算法復(fù)雜度過高,不適用于大規(guī)模圖的實(shí)時(shí)查詢.Li 等人認(rèn)為公交網(wǎng)絡(luò)中容易受堵車等不確定因素影響,所以用隨機(jī)網(wǎng)絡(luò)刻畫道路網(wǎng)絡(luò):每條邊的通行時(shí)間是基于一組隨機(jī)時(shí)間點(diǎn)的隨機(jī)變量[4],并針對(duì)此模型提出一種拉格朗日松弛算法求解.何勝學(xué)等人提出了一種考慮公交線路票價(jià)變化、并以總行程時(shí)間最短與換乘次數(shù)最少相結(jié)合的計(jì)算模型與尋路算法[5];魏金麗等人就公交車“限時(shí)免費(fèi)換乘”的模型,尋找限定時(shí)間最短時(shí)間與超時(shí)條件最低費(fèi)用的路徑[6].上述方法都是在原圖上做查詢,不適用于大圖的實(shí)時(shí)查詢.

另外,有更多工作研究非時(shí)間信息圖上的帶費(fèi)用限制的最短路徑查詢.這些研究假設(shè)圖中的每條邊帶有長(zhǎng)度和費(fèi)用兩個(gè)值,求解不超過費(fèi)用上限的長(zhǎng)度最短的路徑.由于這種查詢需要枚舉從起點(diǎn)到終點(diǎn)的所有路徑,因此是一個(gè)NP 難的問題[7].CSP-CH[8]借鑒路網(wǎng)中求最短路徑的高效算法Contraction Hierarchy[9]的思路建立索引.盡管查詢得到加速,但是在預(yù)處理階段添加的邊太多,導(dǎo)致索引太大.Lozano 等人提出了一種在大規(guī)模圖上求解的方法[10].Ma 提出一種快速的基于A*標(biāo)簽的算法求解受資源限制路徑的問題[11].此外,為了快速求解,學(xué)者提出了求近似解的方法[12-14].Tsaggouris 等人提出的方法保證近似解的路徑長(zhǎng)度在最優(yōu)解的路徑長(zhǎng)度的α倍范圍內(nèi)[12],其中,α是一個(gè)大于1 的預(yù)定義參數(shù).Wang 等人在文獻(xiàn)[13]的基礎(chǔ)上提出了更高效的α-dijk 算法求解近似解,并借鑒了路網(wǎng)下查找最短路徑的高效索引Hub Labelling[15]的思想設(shè)計(jì)了索引COLA[14],極大地提高了查詢速度,可應(yīng)用在真實(shí)的大規(guī)模路網(wǎng)的實(shí)時(shí)查詢.

此外,關(guān)于時(shí)間信息圖上的最小路徑查詢已經(jīng)有了很多的研究工作.Cooke 等人最早提出最早到達(dá)路徑、最晚出發(fā)路徑和最短耗時(shí)路徑這3 種查詢[16].隨著大規(guī)模圖的出現(xiàn),有學(xué)者提出事先在圖上建索引的方法加速查詢.Geisberger 提出的CHT[17]算法與上文提到的CSP-CH 類似,也是采用Contraction Hierarchy[9]的思路建立索引.文獻(xiàn)[18-20]對(duì)原圖的邊預(yù)先排序,可以在線性時(shí)間復(fù)雜度內(nèi)得到查詢結(jié)果.Wang 等人提出的TTL[21]和Daniel 等人提出的Public Transit Labelling[22]采用Hub Labelling 的思想,預(yù)先計(jì)算出圖中部分最短路徑信息,然后通過對(duì)部分路徑集合的線性掃描得到結(jié)果.文獻(xiàn)[23,24]對(duì)時(shí)間信息圖下求解最短路徑的前沿工作做了深入的研究.上述方法只關(guān)注路徑的時(shí)間信息,沒有考慮上費(fèi)用的限制.

綜上所述,帶費(fèi)用限制的最短路徑查詢和時(shí)間信息圖下最小時(shí)態(tài)路徑查詢這兩個(gè)問題已經(jīng)有索引方法提供高效的查詢,但是目前,關(guān)于帶費(fèi)用限制的最小時(shí)態(tài)路徑查詢的研究均是在原圖上做搜索,在大規(guī)模圖上查詢效率低下,因此需要仿照?qǐng)D查詢的傳統(tǒng)做法,預(yù)先對(duì)圖建立索引,再設(shè)計(jì)相應(yīng)的查詢算法利用索引查詢結(jié)果.

本文的貢獻(xiàn)如下:提出了一種帶費(fèi)用限制最小時(shí)態(tài)路徑近似查詢的高效索引(approximate cost constrained time labelling,簡(jiǎn)稱ACCTL).ACCTL 對(duì)圖中每個(gè)頂點(diǎn)預(yù)先計(jì)算一些從該頂點(diǎn)出發(fā)的路徑和到達(dá)該頂點(diǎn)的路徑,使得任意查詢可以通過檢索ACCTL 中的路徑生成解,避免在原圖上做查詢,從而提高查詢效率.實(shí)驗(yàn)結(jié)果表明,基于ACCTL 的查詢比基于Dijkstra 的變種查詢算法快2 個(gè)～3 個(gè)數(shù)量級(jí).雖然ACCTL 與COLA[14]和TTL[21]一樣,都是采用Hub Labelling 的結(jié)構(gòu)建立索引,但ACCTL 并不是簡(jiǎn)單地將COLA 和TTL 合并:COLA 中的路徑長(zhǎng)度是全序關(guān)系,而ACCTL 中的時(shí)間區(qū)間是偏序關(guān)系,不能像長(zhǎng)度那樣可以兩兩比較出大小;TTL 中任意時(shí)刻出發(fā)的最快路徑只有一條,而ACCTL 中需要考慮上費(fèi)用,任意時(shí)刻出發(fā)的最快路徑有多條.在下文中,將會(huì)說明ACCTL 包含了許多精心設(shè)計(jì)和優(yōu)化.

本文第1 節(jié)給出問題的描述和相關(guān)符號(hào)的定義.第2 節(jié)給出一種基于Dijkstra 算法的方法,這種方法是構(gòu)建索引的核心算法.第3 節(jié)介紹ACCTL 的設(shè)計(jì)思路.第4 節(jié)介紹ACCTL 的查詢算法.第5 節(jié)介紹ACCTL 的預(yù)處理構(gòu)建索引算法.第6 節(jié)采用交通數(shù)據(jù)集測(cè)試ACCTL 的查詢效率、空間大小和建立索引的時(shí)間.最后總結(jié)全文.

1 問題描述

本文沿用文獻(xiàn)[1,17,19-22]中的時(shí)間信息圖來刻畫公共交通網(wǎng)絡(luò),并給每條邊添加一個(gè)費(fèi)用值.設(shè)G=(V,E)是一個(gè)有向多重圖,V是頂點(diǎn)的集合,每個(gè)頂點(diǎn)對(duì)應(yīng)公共交通網(wǎng)絡(luò)中的站點(diǎn);E是邊的集合,邊e=〈u,v,td,ta,c〉表示在td時(shí)刻從頂點(diǎn)u出發(fā),在ta時(shí)刻到達(dá)頂點(diǎn)v,所花費(fèi)用是c.兩點(diǎn)之間可以存在多條邊.本文假設(shè)td,ta和c都是非負(fù)整數(shù),這個(gè)假設(shè)是合理的,因?yàn)楝F(xiàn)實(shí)應(yīng)用中不存在費(fèi)用為負(fù)的開銷;此外,總可以找到一個(gè)最小單位粒度來度量時(shí)間和費(fèi)用.對(duì)于時(shí)刻t1和t2,用符號(hào)t1≤t2表示t1早于或等于t2,t1≥t2表示t1晚于或等于t2.定義P=〈e1,e2,…,ek〉是一條路徑,若對(duì)于1≤i

本文研究的帶費(fèi)用限制的最早到達(dá)路徑、最晚出發(fā)路徑和最短耗時(shí)路徑定義如下.

定義1(帶費(fèi)用限制的最早到達(dá)路徑).給定圖G,起點(diǎn)s,終點(diǎn)d,時(shí)刻t,費(fèi)用上限θ,帶費(fèi)用限制的最早到達(dá)路徑指所有在t時(shí)刻或之后從s出發(fā),到達(dá)d,費(fèi)用不超過θ的路徑中,具有最早到達(dá)時(shí)刻的路徑.

定義2(帶費(fèi)用限制的最晚出發(fā)路徑).給定圖G,起點(diǎn)s,終點(diǎn)d,時(shí)刻t′,費(fèi)用上限θ,帶費(fèi)用限制的最晚出發(fā)路徑指所有從s出發(fā),在t′時(shí)刻或之前到達(dá)d,費(fèi)用不超過θ的路徑中,具有最晚出發(fā)時(shí)刻的路徑.

定義3(帶費(fèi)用限制的最短耗時(shí)路徑).給定圖G,起點(diǎn)s,終點(diǎn)d,時(shí)刻t,t′,費(fèi)用上限θ,帶費(fèi)用限制的最短耗時(shí)路徑指所有在t時(shí)刻或之后從s出發(fā),在t′時(shí)刻或之前到達(dá)d,費(fèi)用不超過θ的路徑中,具有最短耗時(shí)的路徑.

約定:若查詢Q存在多條路徑具有最早的到達(dá)時(shí)刻(或最晚的出發(fā)時(shí)刻、或最短的耗時(shí)),則返回費(fèi)用最小的路徑作為解.圖1 是一個(gè)帶費(fèi)用值的時(shí)間信息圖,不同的線形表示不同的交通工具及班次.邊上的數(shù)字表示[出發(fā)時(shí)刻,達(dá)時(shí)刻]和費(fèi)用.假設(shè)查詢從v4到v2的費(fèi)用上限是30 的最早到達(dá)路徑,要求出發(fā)時(shí)刻≥3,則查詢應(yīng)該返回路徑〈e2,e3,e4〉.隨著圖的規(guī)模增大,兩個(gè)頂點(diǎn)之間的路徑數(shù)目暴漲.本文沿用CSP 問題的做法引入近似因子α來控制近似解與精確解的誤差程度.

Fig.1 A time information graph with costs圖1 一個(gè)帶費(fèi)用值的時(shí)間信息圖

定義4(帶費(fèi)用限制的最早到達(dá)路徑查詢的近似解).給定近似因子α,帶費(fèi)用限制的最早到達(dá)路徑查詢Q返回的近似解P滿足:(1)c(P)≤α?c(Popt);(2)P的到達(dá)時(shí)刻≤Popt的到達(dá)時(shí)刻.其中,Popt是Q的精確解.

定義5(帶費(fèi)用限制的最晚出發(fā)路徑查詢的近似解).給定近似因子α,帶費(fèi)用限制的最晚出發(fā)路徑查詢Q返回的近似解P滿足:(1)c(P)≤α?c(Popt);(2)P的出發(fā)時(shí)刻≥Popt的出發(fā)時(shí)刻.其中,Popt是Q的精確解.

定義6(帶費(fèi)用限制的最短耗時(shí)路徑查詢的近似解).給定近似因子α,帶費(fèi)用限制的最短耗時(shí)路徑查詢Q返回的近似解P滿足:(1)c(P)≤α?c(Popt);(2)P的耗時(shí)≤Popt的耗時(shí).其中,Popt是Q的精確解.

α是一個(gè)大于等于1 的實(shí)數(shù).當(dāng)α=1 時(shí),查詢得出的解即為精確解.假設(shè)在圖1 中查找從v4到v0的帶費(fèi)用限制的最晚出發(fā)路徑,t′=10,θ=21 精確解是〈e1,e3〉.若α取1.1,近似解是〈e2,e3〉.

需要說明的是,雖然允許近似解P比它對(duì)應(yīng)的查詢Q的精確解Popt的費(fèi)用稍大,但并不等同于任意在ACCTL 上的查詢返回的P的費(fèi)用總超過θ.實(shí)際上,ACCTL 的設(shè)計(jì)保證了:當(dāng)θ≥α?c(Popt)時(shí),ACCTL 查詢返回的解P即為精確解;當(dāng)θ＜α?c(Popt),即最優(yōu)路徑的費(fèi)用幾乎達(dá)到費(fèi)用上限時(shí),可能返回精確解,也可能返回近似解.若返回的P是近似解,α限定了P的超支范圍,同時(shí),作為超支的補(bǔ)償,P比Popt有更早的到達(dá)時(shí)刻或更晚的出發(fā)時(shí)刻或更短的耗時(shí).換句話說,僅在最優(yōu)解的費(fèi)用幾乎達(dá)到費(fèi)用上限時(shí),ACCTL 有可能返回費(fèi)用稍微超支,但時(shí)間更優(yōu)的近似解;其他情況下,ACCTL 返回精確解.下文將在第5.2 節(jié)的定理3 中給出證明.

表1 給出了全文常用的符號(hào)及含義.

Table 1 Table of notations表1 符號(hào)表

2 一種基于Dijkstra 算法的方法

本節(jié)給出一種基于Dijkstra 算法的Dijk-CCMTP(Dijkstra-cost constrained minimal temporal path)算法,出于兩點(diǎn)目的:首先,Dijk-CCMTP 是構(gòu)建ACCTL 索引的核心算法;其次,3 種查詢可以通過調(diào)用Dijk-CCMTP 的變種算法求得解,將作為實(shí)驗(yàn)中的對(duì)比算法.Dijk-CCMTP 與文獻(xiàn)[1]中的算法相似,但由于本文所求解的問題和文獻(xiàn)[1]不一樣,所以兩者的算法在細(xì)節(jié)上有差別.Dijk-CCMTP 按照費(fèi)用值從小到大的順序枚舉不超過費(fèi)用上限的路徑,從中選擇一條時(shí)間上最優(yōu)的路徑作為解;而文獻(xiàn)[1]的算法選擇長(zhǎng)度最短的路徑作為解.下文中首先給出Dijk-CCMTP 算法的細(xì)節(jié),再討論如何用Dijk-CCMTP 進(jìn)行精確查詢.

2.1 核心算法Dijk-CCMTP

求解帶費(fèi)用限制的最小時(shí)態(tài)路徑需要用到的一個(gè)關(guān)鍵概念叫做路徑支配.

定義7(路徑支配).設(shè)P1和P2是兩條連接相同起點(diǎn)和終點(diǎn)的路徑,稱P1支配P2,或P2被P1支配,如果滿足以下3 個(gè)條件:(1)c(P1)≤c(P2);(2)P1的出發(fā)時(shí)刻≥P2的出發(fā)時(shí)刻;(3)P1的到達(dá)時(shí)刻≤P2的到達(dá)時(shí)刻.

若P1支配P2,則表明P1在費(fèi)用和時(shí)間方面均不比P2的差.若路徑P不被其他路徑支配,則稱P是非支配路徑(若兩條路徑的起點(diǎn)、終點(diǎn)、出發(fā)時(shí)刻、到達(dá)時(shí)刻和費(fèi)用均相等,則任選一條作為非支配路徑).

引理1.設(shè)P是查詢Q的解,Psub是P上的一段子路.如果存在路徑支配Psub,則用代替Psub所得到的路徑也是Q的解.

算法1 描述了Dijk-CCMTP 算法的偽代碼,求解在t時(shí)刻從s出發(fā),費(fèi)用不超過θ,到達(dá)d的最早到達(dá)時(shí)刻.算法從s開始,按路徑的費(fèi)用值升序,費(fèi)用值相等的按到達(dá)時(shí)刻升序的順序擴(kuò)展路徑.這種順序可以在搜索的早期找到費(fèi)用值小的、到達(dá)時(shí)刻早的路徑,有助于利用引理1 剪枝掉被支配的路徑.算法維護(hù)一個(gè)最小堆H記錄當(dāng)前所找到的路徑.每條路徑用元組表示,指路徑在t時(shí)刻從s出發(fā),在時(shí)刻到達(dá)u,費(fèi)用是c*.Dijk-CCMTP 循環(huán)地從H中取出路徑擴(kuò)展出新路徑,直到H為空.

算法1.Dijk-CCMTP 算法.

算法維護(hù)兩個(gè)映射,幫助剪枝掉一些不可能生成解的路徑.映射T(u)記錄了當(dāng)前發(fā)現(xiàn)的到達(dá)u的最早到達(dá)時(shí)刻.在第8 行,如果,則ρ可以被剪枝掉,這是因?yàn)?(1)說明在ρ之前存在路徑ρ′出堆,ρ′的到達(dá)時(shí)刻更新了T(u)(第9 行),而由于路徑按費(fèi)用的升序出堆,ρ′的費(fèi)用小于等于ρ的費(fèi)用;(2)ρ和ρ′有相同的起點(diǎn)s和出發(fā)時(shí)刻t.因此,ρ′支配ρ,ρ可以被剪枝掉.另一個(gè)映射是C(e),記錄最后一條邊是e的路徑的最小費(fèi)用值.如果ρnew的費(fèi)用大于等于C(e),表明已存在路徑ρ′,ρ′和ρnew有相同的起點(diǎn)和終點(diǎn),且出發(fā)時(shí)刻與到達(dá)時(shí)刻也相同,但費(fèi)用小于等于ρnew的,因此ρ′支配ρnew,則ρnew可以被剪枝掉(第13 行).

除了上述兩個(gè)映射以外,還利用費(fèi)用值下限進(jìn)行剪枝.第13 行的c⊥(w,d)表示點(diǎn)w到d的費(fèi)用下限.可以從d出發(fā)調(diào)用一次逆向的Dijkstra 算法,擴(kuò)展路徑時(shí)不考慮邊與邊之間的時(shí)間順序約束,計(jì)算出圖中其他頂點(diǎn)到達(dá)d的費(fèi)用下限.如果ρnew的費(fèi)用(c*+c加上ρnew的終點(diǎn)w到達(dá)d的費(fèi)用的下限已超過θ,則ρnew不可能生成解,不需要加進(jìn)H.

引理2.H最多包含|E|條路徑,其中,|E|表示圖的邊數(shù).

證明:只需證明加進(jìn)H的路徑的最后一條邊各不相同.因?yàn)镠中的路徑是按照費(fèi)用值升序的順序出堆的,因此在所有的最后一條邊是e的路徑中,最早被發(fā)現(xiàn)的路徑具有最小費(fèi)用,加進(jìn)H;之后被發(fā)現(xiàn)的路徑受第13 行的條件c*+c≥C(e)的約束,不會(huì)加進(jìn)H.因此H的路徑總數(shù)不超過|E|.□

算法中采用費(fèi)用值而不是布爾類型變量記錄映射C(e),是為了優(yōu)化帶費(fèi)用限制的最短耗時(shí)路徑查詢,將在第2.2 節(jié)中加以說明.

引理3.算法Dijk-CCMTP 的時(shí)間復(fù)雜度是O(|E|?(log|E|+Δmax)),其中,|E|表示圖的邊數(shù),Δmax表示頂點(diǎn)的最大出度.

證明:H用二項(xiàng)堆實(shí)現(xiàn),第6 行ρ出堆的復(fù)雜度是O(log|E|).第10 行枚舉點(diǎn)的出邊,最多循環(huán)Δmax次,因此,H中處理每條路徑的時(shí)間復(fù)雜度是O(log|E|+Δmax).H最多包含|E|條路徑,因此時(shí)間復(fù)雜度是O(|E|?(log|E|+Δmax)).□

2.2 基于Dijk-CCMTP的查詢算法

本節(jié)首先討論如何調(diào)用Dijk-CCMTP 查詢帶費(fèi)用限制的最早到達(dá)路徑.考慮一個(gè)從s到d的、出發(fā)時(shí)刻≥t、費(fèi)用不超過θ的查詢.可以將Dijk-CCMTP 算法的第4 行的條件“出發(fā)時(shí)刻為t”改成“出發(fā)時(shí)刻≥t”.由引理1 可以證明,這個(gè)改動(dòng)仍然能夠保證算法的正確性.

帶費(fèi)用限制的最晚出發(fā)路徑查詢與帶費(fèi)用限制的最早到達(dá)路徑查詢是對(duì)稱的.帶費(fèi)用限制的最晚出發(fā)路徑查詢從終點(diǎn)d出發(fā)做反向搜索擴(kuò)展回起點(diǎn),即擴(kuò)展路徑時(shí)訪問頂點(diǎn)關(guān)聯(lián)的入邊.在最小堆H中,費(fèi)用小的路徑優(yōu)先出堆;費(fèi)用相等的路徑出發(fā)時(shí)刻晚的優(yōu)先出堆.

帶費(fèi)用限制的最短耗時(shí)路徑查詢并不能調(diào)用一次Dijk-CCMTP求解,這是因?yàn)槁窂降暮臅r(shí)與路徑的出發(fā)時(shí)刻、到達(dá)時(shí)刻均有關(guān)系,因此需要枚舉s的不同的出發(fā)時(shí)刻,多次調(diào)用Dijk-CCMTP 求解.留意到路徑P只可能被比出發(fā)時(shí)刻不早于它的路徑所支配,所以可以按出發(fā)時(shí)刻從晚到早的順序調(diào)用Dijk-CCMTP.每次調(diào)用Dijk-CCMTP 時(shí)重用前一輪調(diào)用Dijk-CCMTP 時(shí)設(shè)置的C(e)值,即調(diào)用了Dijk-CCMTP 求解在t1時(shí)刻出發(fā)的路徑以后,下一輪求在t2時(shí)刻(t2

定理1.Dijk-CCMTP 的變種算法查詢帶費(fèi)用限制的最早到達(dá)路徑和帶費(fèi)用限制的最晚出發(fā)路徑的時(shí)間復(fù)雜度是O(|E|?(log|E|+Δmax)),查詢帶費(fèi)用限制的最短耗時(shí)路徑的時(shí)間復(fù)雜度是O(Δmax?|E|?(log|E|+Δmax)),其中,|E|表示圖的邊數(shù),Δmax表示頂點(diǎn)的最大度數(shù).

定理1 可以由引理1 和引理3 推導(dǎo)證明.

3 索引ACCTL 的框架

本節(jié)介紹索引ACCTL 的設(shè)計(jì)思想.ACCTL 的構(gòu)建基于一個(gè)頂點(diǎn)的全序關(guān)系,全序關(guān)系用來衡量頂點(diǎn)在圖中的重要程度.在公共交通網(wǎng)絡(luò)中,一些交通樞紐很重要,因?yàn)橄嗑噍^遠(yuǎn)的兩個(gè)地方通常在交通樞紐換乘.表現(xiàn)在圖中,一個(gè)頂點(diǎn)所在的帶費(fèi)用限制的最小時(shí)態(tài)路徑越多,它就越重要,稱它等級(jí)越高.本文用o(v)表示將頂點(diǎn)按重要程度從高到低排序后,頂點(diǎn)v在序列中的位置.若o(v)

3.1 ACCTL的設(shè)計(jì)思想

設(shè)P是一條從點(diǎn)s到點(diǎn)d的路徑,v?是P上的頂點(diǎn)中等級(jí)最高的點(diǎn).v?在P中所處的位置有3 種可能:(1)v?=s;(2)v?=d;(3)v?≠s且v?≠d.設(shè)P上從s到v?的子路記為P+,從v?到d的子路記為P-.情況(1)和情況(2)可視為情況(3)的特例,即P+或P-為空.如果預(yù)先計(jì)算出一些從s到比s高級(jí)的頂點(diǎn)的路徑(這些路徑的集合記為S+)和一些從比d高級(jí)的頂點(diǎn)到d的路徑(這些路徑的集合記為S-),那么對(duì)于一個(gè)從s到d的查詢,可以從S+中查找P+、從S-中查找P-,使得P+和P-能夠連接成一條路徑生成解.這種查找方法類似于數(shù)據(jù)庫的表連接操作.如果設(shè)一張數(shù)據(jù)庫表T記錄任意查詢Q的解,ACCTL 的作用就是把T分解成兩張表T1和T2,使得T中的記錄可以通過T1和T2連接操作生成.于是,ACCTL 避免在原圖G上遍歷,從而減少搜索量.由引理1,任何查詢的解均可以由兩條非支配路徑生成,因此ACCTL 只需要保存一些基本路徑即可.

定義8(基本路徑).P是一條基本路徑,如果P滿足以下兩個(gè)條件:

(1)等級(jí)約束:P上的頂點(diǎn)中,起點(diǎn)或終點(diǎn)的等級(jí)最高;

(2)支配約束:P是非支配路徑.

假設(shè)圖1 中的頂點(diǎn)的等級(jí)由高到低依次為v0～v5.〈e2,e3〉是一條基本路徑;〈e2,e3,e4〉違反了等級(jí)約束,不是基本路徑.

隨著圖的規(guī)模增大,圖中基本路徑的數(shù)目會(huì)暴漲,因此,ACCTL 需要借助近似因子α去掉部分基本路徑,允許生成近似解.生成近似解的一個(gè)關(guān)鍵概念是路徑的α-支配.

定義9(路徑的α-支配).設(shè)P1和P2是兩條連接相同起點(diǎn)和終點(diǎn)的路徑,α是近似因子.稱P1α-支配P2,或P2被P1α-支配,如果滿足:(1)c(P1)≤α?c(P2);(2)P1的出發(fā)時(shí)刻≥P2的出發(fā)時(shí)刻;(3)P1的到達(dá)時(shí)刻≤P2的到達(dá)時(shí)刻.

定義9 與定義7 的區(qū)別在于,對(duì)路徑的費(fèi)用稍放寬至近似因子α倍范圍內(nèi).如圖1 所示,假設(shè)路徑P1=〈e1,e3〉,P2=〈e2,e3〉,α取1.1,則P2α-支配P1.結(jié)合定義4～定義6 和定義9,可以得到以下引理.

引理4.設(shè)P是查詢Q的精確解,P′α-支配P,則P′是Q的近似解.

表2 是ACCTL 的雛形.第2 列的每條標(biāo)簽〈u,td,ta,c,lptr〉表示路徑在td時(shí)刻從v出發(fā),在ta時(shí)刻到達(dá)u,費(fèi)用c,lptr指向表示前綴路徑的標(biāo)簽(表中每條標(biāo)簽的最后一個(gè)分量(lptr)為null 表示該標(biāo)簽對(duì)應(yīng)的路徑不存在前綴路徑,為*表示前綴路徑的標(biāo)簽不在表中),其具體含義將在定義10 中說明.例如,l0=〈v0,2,6,7,null〉表示在2 時(shí)刻從v2出發(fā),6 時(shí)刻到達(dá)v0,費(fèi)用是7.第3 列的標(biāo)簽表示從u到v的路徑.假設(shè)查詢從v4到v2的費(fèi)用上限是30 的最早到達(dá)路徑,要求出發(fā)時(shí)刻≥3.查詢過程將標(biāo)簽l7,l8,…,l11和l2,l3,l4進(jìn)行匹配.標(biāo)簽la和lb相匹配的意思是:(1)la表示的路徑的終點(diǎn)與lb表示的路徑的起點(diǎn)相同;(2)lb的出發(fā)時(shí)刻≥la的到達(dá)時(shí)刻;(3)la和lb的費(fèi)用之和不超過費(fèi)用上限.本例中,查詢返回l8和l2匹配的路徑,即〈e2,e3,e4〉,在3 時(shí)刻出發(fā),14 時(shí)刻到達(dá),費(fèi)用是30.

Table 2 Some canoical paths from/to v2～v4against Fig.1 with α=1.1表2 圖1 的v2～v4出發(fā)/到達(dá)的部分基本路徑,α=1.1

3.2 標(biāo)簽去冗余

表2 的標(biāo)簽存在冗余,影響到索引的存儲(chǔ)空間大小和查詢效率.例如l3和l4均表示從v1到v2的路徑,頂點(diǎn)v1只需要保存一份即可,無需在l3和l4中均保存.另外,僅具有共同端點(diǎn)的標(biāo)簽才有可能匹配上.例如查詢從v4到v2的路徑時(shí),可能與l9匹配的標(biāo)簽只有l(wèi)3和l4,因?yàn)樗鼈兊钠瘘c(diǎn)v1等于l9的終點(diǎn).l2的起點(diǎn)與l9的終點(diǎn)不相同,因此查詢時(shí)無需掃描l2.基于上述考慮,ACCTL 將表示連接相同頂點(diǎn)的路徑的標(biāo)簽分成一個(gè)標(biāo)簽組.表3 顯示了分組的標(biāo)簽,這也是ACCTL 的存儲(chǔ)格式.

定義10(ACCTL 索引).給定近似因子α,圖G的ACCTL 索引預(yù)先對(duì)每個(gè)頂點(diǎn)v計(jì)算兩個(gè)標(biāo)簽組集合L+(v)和L-(v),滿足:

(3)對(duì)于任意的從頂點(diǎn)s到頂點(diǎn)d的帶費(fèi)用限制的最小時(shí)態(tài)路徑查詢Q,設(shè)Popt是Q的精確解,則在L+(s)內(nèi)的某個(gè)標(biāo)簽組中,存在標(biāo)簽(下文中,對(duì)于標(biāo)簽中暫不需關(guān)注的項(xiàng)采用符號(hào)?表示)的對(duì)應(yīng)路徑P+,在L-(d)內(nèi)的某個(gè)標(biāo)簽組中,存在標(biāo)簽的對(duì)應(yīng)路徑P-,以下3 種情況之一成立.

(3.1)u=d,且P+α-支配Popt;

(3.2)v=s,且P-α-支配Popt;

(3.3)u=v,,且P+和P-連接起來的路徑α-支配Popt.

Table 3 L+(v)and L-(v)label sets of v2～v4of ACCTL against Fig.1 with α=1.1表3 圖1 的ACCTL 索引中v2～v4的L+(v)和L-(v)集合,α=1.1

下文為了表述清晰,首先在第4 節(jié)介紹查詢算法,然后在第5 節(jié)討論索引的構(gòu)建方法,因?yàn)樗饕龢?gòu)建方法比查詢方法復(fù)雜.

4 查詢算法

查詢從點(diǎn)s到點(diǎn)d的帶費(fèi)用限制的最小時(shí)態(tài)路徑分個(gè)兩階段:首先,檢索L+(s)和L-(d)得到符合查詢要求的標(biāo)簽;然后,將標(biāo)簽還原回一條圖G上的路徑.下文分別介紹查找標(biāo)簽和還原路徑的過程.

4.1 查找標(biāo)簽

本節(jié)討論如何用ACCTL 查詢從s到d、出發(fā)時(shí)刻≥t、費(fèi)用上限為θ的最早到達(dá)路徑近似解,另外兩種查詢可作近似的處理.定義10 的條件(3)大致給出了查詢過程.L+(s)和L-(d)內(nèi)的標(biāo)簽分別記錄了路徑的前半部分和后半部分的信息,查詢過程就是找出L+(s)和L-(d)內(nèi)的相匹配的標(biāo)簽,生成候選路徑,再從候選路徑中挑選具有最早到達(dá)時(shí)刻的路徑作為解.

算法2 描述了帶費(fèi)用限制的最早到達(dá)路徑的查詢算法.t⊥表示當(dāng)前找到的路徑的最早到達(dá)時(shí)刻,在查詢過程中,利用t⊥減少不必要的標(biāo)簽匹配.初始時(shí),t⊥=∞.c?是一個(gè)擴(kuò)大α倍的上限,允許近似解的費(fèi)用稍微超過θ.算法第2 行～第5 行處理定義10 中條件(3)的情況(3.1)和情況(3.2).

算法2.EAPQuery.

接下來,算法處理等級(jí)最高的點(diǎn)出現(xiàn)在路徑內(nèi)部的情況,對(duì)應(yīng)定義10 中條件(3)的情況(3.3).指針i和j分別指示當(dāng)前正在掃描L+(s)和L-(d)的第幾組標(biāo)簽.算法對(duì)L+(s)和L-(d)內(nèi)的標(biāo)簽組進(jìn)行線性掃描.假設(shè)當(dāng)前正在掃描L+(s)內(nèi)的標(biāo)簽組和L-(d)內(nèi)的標(biāo)簽組.如果o(ui)o(uj)令j指向下一組標(biāo)簽(第10 行).

當(dāng)o(ui)=o(uj),即ui=uj時(shí),內(nèi)的標(biāo)簽有可能與內(nèi)的標(biāo)簽匹配.留意到內(nèi)的標(biāo)簽按出發(fā)時(shí)刻升序排列,所以可調(diào)用二分查找快速定位到中的第1 條的標(biāo)簽(第12 行),符合要求的標(biāo)簽必定都排在l+之后.在匹配l+和內(nèi)的標(biāo)簽時(shí),從內(nèi)的第1 條標(biāo)簽開始按順序遍歷.記l-為當(dāng)前掃描的內(nèi)的標(biāo)簽.當(dāng)l-的到達(dá)時(shí)刻≥t⊥時(shí),對(duì)的遍歷便可終止,因?yàn)閮?nèi)的標(biāo)簽按到達(dá)時(shí)刻升序排列,排在l-之后的標(biāo)簽不可能生成到達(dá)時(shí)刻早于t⊥的解.

假設(shè)在表3 的ACCTL 索引中查找從v4到v2、在3 時(shí)刻或之后出發(fā)的、費(fèi)用不超過30 的最早到達(dá)路徑.初始時(shí)t⊥=∞.首先,L+(v4)中沒有終點(diǎn)是v2的標(biāo)簽組,L-(v2)中也沒有起點(diǎn)是v4的標(biāo)簽組;接著,從L+(v4)的終點(diǎn)為v0的標(biāo)簽組找到第1 條出發(fā)時(shí)刻≥3 的標(biāo)簽l8=〈3,10,22,l5〉;接著,檢查L(zhǎng)-(v2)中以v0為起點(diǎn)的第1 條標(biāo)簽l2=〈10,14,8,null〉,于是得到一條由l8和l2拼接的候選路徑,更新t⊥=14;接下來掃描L+(v4)的下一個(gè)標(biāo)簽組,由于中不存在出發(fā)時(shí)刻≥3 的標(biāo)簽,所以繼續(xù)檢查下一個(gè)標(biāo)簽組.由于L-(v2)不存在以v3為起點(diǎn)的標(biāo)簽組,所以此時(shí)L-(v2)的標(biāo)簽組掃描完畢,查詢結(jié)束,返回l8和l2,表示結(jié)果為從3 時(shí)刻出發(fā)、在14 時(shí)刻到達(dá)、費(fèi)用為30 的路徑.

4.2 路徑還原

算法2 僅獲得表示查詢的解的標(biāo)簽,需要將標(biāo)簽還原成圖G上的一條路徑.出于對(duì)稱性,下文僅討論如何將還原.假設(shè)表示一條從頂點(diǎn)u到d的路徑P-.設(shè)vpred表示P-上d的直接前驅(qū)頂點(diǎn).由定義10,lptr表示P-上從u到vpred的那一段子路(記為Ppred).于是,可通過還原lptr獲得Ppred.假設(shè)路徑由k條邊構(gòu)成,則還原路徑的復(fù)雜度是O(k).

本文為了表述清晰,用lptr指代表示路徑前綴的標(biāo)簽.在實(shí)際編碼中,lptr通過記錄vpred和pos實(shí)現(xiàn),其中,pos表示Ppred的標(biāo)簽在L-(vpred)中的標(biāo)簽組中的存放位置.需要說明的是,必定包含了lptr.這是因?yàn)?(1)Ppred上的頂點(diǎn)中,起點(diǎn)u的等級(jí)最高,理由是P-上u的等級(jí)最高;(2)下文將在第5.1 節(jié)中解釋,ACCTL 采用Dijk-CCMTP 算法構(gòu)造P-,Ppred是非支配路徑;并且在第5.2 節(jié)中解釋lptr會(huì)保留在ACCTL 中,不會(huì)被刪除.

5 ACCTL 索引的構(gòu)建

本節(jié)解釋如何構(gòu)建ACCTL 索引.ACCTL 的正確性依賴于兩點(diǎn):(1)對(duì)于任意查詢Q,設(shè)精確解是Popt,總可以在ACCTL 找到路徑P,使得Pα-支配Popt,由引理4,P是Q的近似解;(2)從ACCTL 中查找到的標(biāo)簽總可以還原成圖G上的一條路徑.因此,構(gòu)建ACCTL 的難點(diǎn)在于:(1)如何有效地、不遺漏地計(jì)算出所有基本路徑?(2)如何盡量多地去掉一些路徑,但仍能保證路徑被還原?對(duì)應(yīng)地,ACCTL 的構(gòu)建有兩個(gè)步驟:一是生成基本路徑;二是剪枝掉一些基本路徑.下文分別在第5.1 節(jié)和第5.2 節(jié)解釋這兩個(gè)步驟,在第5.3 節(jié)討論頂點(diǎn)的等級(jí)序o的計(jì)算.

5.1 計(jì)算基本路徑

計(jì)算基本路徑的一種直觀的做法是:枚舉符合等級(jí)約束的路徑,從中選擇非支配路徑,得到基本路徑.初始時(shí),設(shè)G0=G,等級(jí)最高的頂點(diǎn)記為v0,G0中所有從v0出發(fā)和到達(dá)v0的路徑均滿足等級(jí)約束.接下來,將v0從G0中刪除,生成圖G1.在G1中,等級(jí)最高的頂點(diǎn)記為v1,從v1出發(fā)和到達(dá)v1的路徑均滿足等級(jí)約束,….重復(fù)上述步驟,即可計(jì)算出符合等級(jí)約束的路徑.算法3 描述了構(gòu)建索引算法BuildIndex.第3 行～第26 行的for 循環(huán)迭代地計(jì)算從vi出發(fā)的和到達(dá)vi的基本路徑,并選擇部分路徑生成標(biāo)簽加進(jìn)ACCTL 中.

算法3.BuildIndex.

如何從滿足等級(jí)約束的路徑中有效地計(jì)算出非支配路徑?假設(shè)計(jì)算從vi出發(fā)的基本路徑.由于在t時(shí)刻出發(fā)的路徑僅可能被在t′時(shí)刻(t′≥t)出發(fā)的路徑支配,所以按vi的出發(fā)時(shí)刻降序的順序調(diào)用Dijk-CCMTP(第6 行).第7 行～第17 行的處理與Dijk-CCMTP 類似,但做了以下改動(dòng).

(1)保存在堆H中的路徑ρ=〈u,ta,c,ρpred〉增加一個(gè)分量ρpred,表示ρ的前綴路徑.

(2)對(duì)于Gi中的每個(gè)頂點(diǎn)u,用一個(gè)包B(u)收集從vi到u的非支配路徑.ρ從H摘除后(第11 行),僅當(dāng)ρ不被B(u)中的路徑支配時(shí)才將ρ加進(jìn)B(u).回顧H中的路徑,按照費(fèi)用升序出堆;另一方面,第10 行～第17行的while 循環(huán)計(jì)算的路徑有相同的起點(diǎn)(s)和出發(fā)時(shí)刻(t),可推出路徑按到達(dá)時(shí)刻降序的順序加入B(u),所以只需要比較ρ和最近一條加入B(u)的路徑的到達(dá)時(shí)刻,即可得出ρ是否被B(u)內(nèi)的路徑支配(第12 行).

(3)由于終點(diǎn)d和費(fèi)用上限θ在構(gòu)建索引時(shí)未知,所以在BuildIndex 中不利用d和θ進(jìn)行剪枝.

當(dāng)在t時(shí)刻從vi出發(fā)的路徑遍歷完后,對(duì)于每個(gè)可達(dá)頂點(diǎn)u,它的包B(u)包含了到達(dá)u的非支配路徑.第19行的MarkPrune 算法從B(u)中選擇部分路徑加入ACCTL,選擇細(xì)節(jié)將在第5.2 節(jié)中討論.MarkPrune 獨(dú)立地選擇B(u)中的路徑加進(jìn)ACCTL,即是說,MarkPrune 在選擇B(u)中的路徑時(shí)并不考慮另一個(gè)頂點(diǎn)v的包B(v)內(nèi)的路徑,其后果可能導(dǎo)致還原路徑時(shí)出錯(cuò).假設(shè)在選擇B(u)中的路徑時(shí),路徑ρ=〈?,?,?,ρpred〉被選中,生成相應(yīng)的標(biāo)簽l加進(jìn)ACCTL.為了保證標(biāo)簽l能正確被還原,表示路徑ρpred的標(biāo)簽lptr必須在ACCTL 中.然而lptr可能不在ACCTL 中,因?yàn)镸arkPrune 在選擇B(vpred)內(nèi)的路徑(假設(shè)vpred是ρ上u的直接前驅(qū)頂點(diǎn))時(shí)并沒有考慮ρ.因此,在調(diào)用完MarkPrune 以后,需要自底向上地檢查每條被保留的路徑是否可被還原.加進(jìn)ACCTL 的標(biāo)簽是否可被還原,取決于它對(duì)應(yīng)的路徑ρ的前綴路徑ρpred是否也生成對(duì)應(yīng)的標(biāo)簽加進(jìn)ACCTL.對(duì)于每條被MarkPrune 算法標(biāo)記為保留的路徑ρ,如果ρpred也被標(biāo)記成保留,則對(duì)ρ的檢查結(jié)束;否則,將ρpred標(biāo)記成保留,并追溯ρpred的前綴路徑是否標(biāo)記為保留,直到遇到前綴路徑被標(biāo)記為保留為止.假設(shè)Gi中所有頂點(diǎn)u的B(u)集合的路徑總數(shù)為m,第20 行～第22行自底向上檢查的時(shí)間復(fù)雜度是O(m).由引理2,m不超過|E|.實(shí)際上,受出發(fā)時(shí)刻和路徑支配約束,m<<|E|.因此,第20 行～第22 行不會(huì)產(chǎn)生太大耗費(fèi).

對(duì)于每條標(biāo)記為保留的路徑,第23 行、第24 行生成標(biāo)簽l并加進(jìn)相應(yīng)的標(biāo)簽組.最后,第26 行調(diào)用反向Dijk-CCMTP 算法計(jì)算到達(dá)vi的基本路徑,計(jì)算過程與第4 行～第25 行相似.

5.2 選擇路徑

本節(jié)關(guān)注算法3 第19 行的MarkPrune 算法如何選擇B(u)中的路徑加進(jìn)ACCTL.B(u)包含了在t時(shí)刻出發(fā)的從vi到u的路徑.關(guān)鍵問題是:如何在B(u)中選擇盡量少的路徑加進(jìn)ACCTL,同時(shí)能夠保證對(duì)于任意的查詢Q,都能在ACCTL 中找到標(biāo)簽生成近似解?換句話說,對(duì)于任意路徑ρ∈B(u),如果表示ρ的標(biāo)簽沒有加進(jìn)ACCTL,則在ACCTL 中存在另一條標(biāo)簽對(duì)應(yīng)路徑ρ′,使得ρ′α-支配ρ.精確計(jì)算出保留的路徑的最小集合是一個(gè)NP-難問題,MarkPrune 采用貪心的策略選擇路徑,如算法4 所示.

算法4.MarkPrune.

假設(shè)加入B(u)的路徑的順序依次是ρ0,ρ1,…,ρk-1.由于路徑按費(fèi)用升序生成,受路徑支配的限制,ρ0,ρ1,…,ρk-1自動(dòng)按到達(dá)時(shí)刻降序排列.因此,ρi僅可能α-支配比它早加入B(u)的路徑ρj(j

回顧在BuildIndex 算法中,從vi出發(fā)的路徑按出發(fā)時(shí)刻從晚到早的順序生成,因此當(dāng)前內(nèi)的標(biāo)簽表示的路徑的出發(fā)時(shí)刻均晚于B(u)內(nèi)的路徑,也可能α-支配B(u)內(nèi)的某些路徑.直觀來說,如果在內(nèi)存在某條標(biāo)簽對(duì)應(yīng)的路徑ρ′α-支配B(u)內(nèi)的某條路徑ρ,則可以把ρ刪除.但這種判斷會(huì)引起錯(cuò)誤.假設(shè)α=1.1,B(u)中存在兩條路徑ρ10和ρ11,費(fèi)用分別是10 和11,且有ρ11α-支配ρ10.于是保留ρ11,刪除ρ10.假設(shè)中存在某條標(biāo)簽表示路徑ρ12,費(fèi)用12,且有ρ12α-支配ρ11.如果因?yàn)棣?2的存在刪除ρ11,則沒有路徑α-支配ρ10.因此,MarkPrune 采用d(ρ)記錄ρ的支配范圍,即ρ能夠α-支配的費(fèi)用最小的路徑是哪條.中,某條標(biāo)簽表示的路徑ρ′能夠刪除B(u)中的某條路徑ρ,僅當(dāng)ρ′α-支配d(ρ).

定理2.BuildIndex 算法生成的ACCTL 索引是正確的.

證明:假設(shè)Popt是一個(gè)從頂點(diǎn)s到頂點(diǎn)d的查詢Q的精確解,且Popt上任意一段子路都是非支配路徑.由引理1,這樣的路徑Popt是存在的.設(shè)v?是Popt上等級(jí)最高的點(diǎn),Popt上從s到v?的路段記為,從v?到d的路段記為.首先證明:在ACCTL 中能找到標(biāo)簽生成路徑P,使得Pα-支配Popt.BuildIndex 的第6 行～第17 行枚舉了所有從v?出發(fā)的基本路徑,保證生成了;第18 行、第19 行保證ACCTL 存在路徑P-,P-α-支配.對(duì)稱地,ACCTL 也存在路徑P+,P+α-支配在費(fèi)用方面,.在時(shí)間方面,P+的到達(dá)時(shí)刻≤的到達(dá)時(shí)刻≤的出發(fā)時(shí)刻≤P-的出發(fā)時(shí)刻,所以P+與P-能夠拼接成路徑;同時(shí),P+的出發(fā)時(shí)刻≥的,P-的到達(dá)時(shí)刻≤的,所以P+和P-拼接的路徑α-支配Popt.最后,第20 行～第22 行保證了每條路徑的前綴路徑的標(biāo)簽都在ACCTL 中,于是能夠?qū)?biāo)簽正確還原成G上的一條路徑.□

定理3.設(shè)查詢Q的費(fèi)用限制是θ,Popt是Q的精確解,且Popt上任意一段子路都是非支配路徑.設(shè)P是用ACCTL 查詢所得解.

(1)若α?c(Popt)≤θ,則P是精確解;

(2)若θ<α?c(Popt),則P有可能是精確解,也可能是近似解;若P是近似解,滿足:

(2.1)c(P)≤α?c(Popt);

(2.2)P不早于Popt出發(fā)且不晚于Popt到達(dá).

?用反證法證明:(1)當(dāng)α?c(Popt)≤θ時(shí),P是精確解.因?yàn)镻opt上任意一段子路都是非支配路徑,所以是非支配路徑,于是在ACCTL 中存在標(biāo)簽,使得表示的路徑α-支配;同理,ACCTL 存在標(biāo)簽,使得表示的路徑α-支配.于是,拼接的路徑P滿足費(fèi)用限制:.另一方面,由α-支配的定義,P的出發(fā)時(shí)刻≥的,到達(dá)時(shí)刻≤的,與Popt是最優(yōu)解矛盾.

?(2)當(dāng)θ<α?c(Popt)時(shí),如果ACCTL 中存在的標(biāo)簽拼接的路徑P滿足c(P)≤θ,則同情形(1)的證明,P是精確解;若c(P)>θ,則P是近似解,可采用定理2 的證明過程證明情形(2.1)和情形(2.2).□

定理4.BuildIndex 算法的時(shí)間復(fù)雜度是O(|V|?Δmax?|E|?(log|E|+Δmax)),其中,|V|表示頂點(diǎn)數(shù),|E|表示邊數(shù),Δmax表示頂點(diǎn)的最大度數(shù).

5.3 點(diǎn)序o的計(jì)算

與文獻(xiàn)[14,15,21,22]相同,盡管頂點(diǎn)的等級(jí)序o的選取不影響查詢結(jié)果的正確性,但會(huì)影響索引所包含的標(biāo)簽數(shù)目,進(jìn)而影響查詢效率.要精確計(jì)算出o,使得索引所包含的的標(biāo)簽數(shù)最少是一個(gè)NP-難的問題.因此,本文采用文獻(xiàn)[14,21]的方法,對(duì)o進(jìn)行啟發(fā)式計(jì)算.如果頂點(diǎn)v在路徑P上,則稱v覆蓋P.ACCTL 的作用好比把一張記錄任意查詢Q的解的數(shù)據(jù)庫表T分解成兩張表T1和T2,使得T中的記錄可以通過T1和T2的連接操作生成.T1好比記錄了所有頂點(diǎn)v的L+(v)內(nèi)的標(biāo)簽,T2記錄了L-(v)內(nèi)的標(biāo)簽.為使T1和T2盡量小,應(yīng)該使得T1和T2之間能連接上的記錄盡量多.這等同于:v覆蓋的帶費(fèi)用限制的最小時(shí)態(tài)路徑越多,v的等級(jí)就應(yīng)該越高.由于帶費(fèi)用限制的最小時(shí)態(tài)路徑太多,不可能逐一枚舉,所以本文采用這樣的方法確定o:從圖中隨機(jī)選取一個(gè)頂點(diǎn)集合Vsub?V,分別從Vsub的每個(gè)頂點(diǎn)v出發(fā)擴(kuò)展路徑.留意到路徑具有時(shí)間和費(fèi)用兩個(gè)屬性,兩個(gè)點(diǎn)之間有多條不會(huì)被相互支配的路徑.本文采用近似的方法將路徑的時(shí)間和屬性量化成一個(gè)值:一條路徑P的“長(zhǎng)度”等于P的費(fèi)用×β+P的耗時(shí)×(1-β),其中,β是一個(gè)[0,1)范圍內(nèi)的實(shí)數(shù),在從v出發(fā)擴(kuò)展路徑之前隨機(jī)生成.這樣,從頂點(diǎn)v出發(fā),采用類Dijkstra 算法搜索全圖,可得出v到其他頂點(diǎn)的最短路徑,生成一棵以v為根的Dijkstra 樹.樹上任一頂點(diǎn)u到u的子孫的路徑也是最短路徑,因此u在圖中覆蓋的最短路數(shù)目等于以u(píng)為根的子樹包含的頂點(diǎn)數(shù),包括u自身.u在|Vsub|棵樹覆蓋的最短路徑的總數(shù)視為u覆蓋最短路徑數(shù).算法對(duì)|Vsub|棵樹分別做自底向上的掃描,統(tǒng)計(jì)出每個(gè)頂點(diǎn)覆蓋的最短路徑數(shù)目,從中選出覆蓋最短路徑數(shù)最多的點(diǎn)v0作為等級(jí)最高的頂點(diǎn);然后,在每棵樹中刪除以v0為根的子樹,再更新各個(gè)頂點(diǎn)覆蓋的最短路徑數(shù),在“剩下的”路徑中,選擇覆蓋數(shù)目最大的頂點(diǎn)v1作為等級(jí)次高的頂點(diǎn)...依此次類推.若|Vsub|棵樹刪除完后仍有頂點(diǎn)的o序未確定,則按頂點(diǎn)的度數(shù)從大到小排序確定.

6 實(shí) 驗(yàn)

實(shí)驗(yàn)采用C++語言編寫測(cè)試代碼,測(cè)試平臺(tái)Windows 10,64 位操作系統(tǒng),機(jī)器配置Intel(R)Core(TM)i7-8700K CPU,64GB 內(nèi)存.實(shí)驗(yàn)采用文獻(xiàn)[21]提供的數(shù)據(jù)集做測(cè)試.數(shù)據(jù)采集自GTFS[25],記錄了一些地區(qū)的公共交通數(shù)據(jù).數(shù)據(jù)集中每條邊e只記錄了出發(fā)時(shí)刻和到達(dá)時(shí)刻,實(shí)驗(yàn)給e生成一個(gè)費(fèi)用值.為了模擬真實(shí)環(huán)境,一條從u到v的邊的費(fèi)用取值圖中所有從u到v的邊的耗時(shí)的平均值.實(shí)驗(yàn)數(shù)據(jù)的特征見表4,|V|表示頂點(diǎn)數(shù),|E|表示邊數(shù),Δmax表示頂點(diǎn)最大度數(shù),表示平均頂點(diǎn)度數(shù).下文就ACCTL 索引的查詢時(shí)間、索引大小和建立索引的時(shí)間進(jìn)行分析.

Table 4 Characteristics of datasets表4 數(shù)據(jù)集特征

6.1 查詢時(shí)間

查詢沿用文獻(xiàn)[21]提供的查詢集.每個(gè)數(shù)據(jù)集的查詢集內(nèi)有10 萬個(gè)查詢.每個(gè)查詢包括起點(diǎn)s、終點(diǎn)d、時(shí)刻t和t′、費(fèi)用上限θ.s和d從頂點(diǎn)集中隨機(jī)產(chǎn)生,t和t′從數(shù)據(jù)集的時(shí)間域隨機(jī)產(chǎn)生.費(fèi)用上限θ是在[θmin,θmax]范圍內(nèi)的一個(gè)隨機(jī)數(shù):θmin表示不考慮路徑上相鄰的邊之間的時(shí)間順序,從s到d的最小費(fèi)用;θmax表示從s到d的某條隨機(jī)的邊出發(fā)的最短耗時(shí)路徑的費(fèi)用.帶費(fèi)用限制的最早到達(dá)路徑查詢使用s,d,t和θ作為查詢參數(shù);帶費(fèi)用限制的最晚出發(fā)路徑查詢使用s,d,t′和θ;帶費(fèi)用限制的最短耗時(shí)路徑查詢使用s,d,t,t′和θ.

實(shí)驗(yàn)將ACCTL 與文獻(xiàn)[1]提出的一種Dijkstra 變種算法作對(duì)比.因?yàn)槲墨I(xiàn)[1]解決的問題與本文的有差別(回顧文獻(xiàn)[1]求解不超過費(fèi)用上限的、路徑上相鄰的邊滿足時(shí)間順序約束的、長(zhǎng)度最短的路徑),因此將文獻(xiàn)[1]的Dijkstra 變種算法修改成解決本文問題的算法,也即第2 節(jié)討論的Dijk-CCMTP 的變種算法進(jìn)行3 類查詢.下文中,對(duì)用基于Dijkstra 方法求解帶費(fèi)用限制的最早到達(dá)路徑、最晚出發(fā)路徑和最短耗時(shí)路徑的方法標(biāo)記為Dijk-CCEAP、Dijk-CCLDP 和Dijk-CCSDP;對(duì)采用ACCTL 索引查詢的方法標(biāo)記為ACCTL-CCEAP、ACCTLCCLDP 和ACCTL-CCSDP.

圖2 顯示了基于Dijkstra 變種算法和基于ACCTL 索引方法的查詢時(shí)間對(duì)比.實(shí)驗(yàn)一共測(cè)試了11 組數(shù)據(jù),y軸以ms 為單位,用對(duì)數(shù)的比例顯示每組數(shù)據(jù)的平均查詢時(shí)間.ACCTL 索引的α取1 求精確解,即調(diào)用BuildIndex時(shí)不執(zhí)行第18 行～第22 行去掉部分α-支配路徑的代碼.

Fig.2 Query times of the Dijkstra variant method and ACCTL圖2 基于Dijkstra 搜索的變種算法和ACCTL 索引的查詢時(shí)間

總體看來,基于ACCTL 索引的平均查詢時(shí)間比基于Dijkstra 的搜索快2 個(gè)～3 個(gè)數(shù)量級(jí).這是因?yàn)锳CTTL在預(yù)先計(jì)算的路徑集中查找路徑生成解,避免在原圖上盲目搜索.就各組數(shù)據(jù)的基于ACCTL 索引的查詢時(shí)間對(duì)比,查詢時(shí)間與索引大小和圖的度數(shù)有關(guān).總體來說,索引越大,查詢時(shí)間就越長(zhǎng).圖3 的各組數(shù)據(jù)的第1 根柱子顯示了α=1 時(shí)的索引大小.留意到Madrid 的索引比LosAngeles 和Berlin 的都小,但查詢時(shí)間長(zhǎng).這是因?yàn)镸adrid的平均頂點(diǎn)度數(shù)大.頂點(diǎn)v的度數(shù)越大,v到達(dá)圖中其他頂點(diǎn)(或從圖中其他頂點(diǎn)到達(dá)v)的可能性越大,即L+(s)和L-(d)有擁有相同端點(diǎn)的標(biāo)簽組越多,所以需要匹配的標(biāo)簽組越多,查詢時(shí)間越長(zhǎng).此外,最短耗時(shí)路徑查詢的速度比最早到達(dá)路徑查詢的稍慢,甚至在個(gè)別數(shù)據(jù)中最短耗時(shí)路徑的查詢比最早到達(dá)路徑的更快(例如Berlin 的Dijk-CCEAP 與Dijk-CCSDP、SaltLakeCity 的ACCTL-CCEAP 與ACCTL-CCSDP),這是因?yàn)樽疃毯臅r(shí)路徑查詢受到到達(dá)時(shí)刻t′的約束,可以幫助剪枝掉部分搜索;而最早到達(dá)路徑的到達(dá)時(shí)刻沒有t′的約束,所以搜索量反而更大.

Fig.3 Index size (MB)of group A and B,with α=1,1.1,1.2 respectively圖3 A 組α取1、1.1、1.2 和B 組α取1.1、1.2 時(shí),各個(gè)圖的索引大小(MB)

6.2 索引的大小

本節(jié)討論α取值以及路徑的費(fèi)用值浮動(dòng)對(duì)索引大小的影響.實(shí)驗(yàn)設(shè)置兩大組數(shù)據(jù)集:A 組數(shù)據(jù)集的設(shè)置如上文所述,一條從u到v的邊的費(fèi)用取值圖中所有從u到v的邊的耗時(shí)的平均值;B 組數(shù)據(jù)集的圖中一條邊e的費(fèi)用取值為[0.7×π,1.3×π]范圍內(nèi)的一個(gè)隨機(jī)整數(shù),其中,π表示通過e的耗時(shí),即令邊的費(fèi)用取值多樣化.換句話說,A 組的圖的邊的費(fèi)用取值單一,B 組的圖的邊的費(fèi)用取值多樣.

圖3 的每組數(shù)據(jù)的前3 根柱子顯示了A 組數(shù)據(jù)集下α取1,1.1 和1.2 時(shí)各個(gè)圖的索引大小,以MB 為單位,分別標(biāo)記為(A)1、(A)1.1、(A)1.2.當(dāng)α遞增時(shí),索引變小.因?yàn)锳CCTL 利用α-支配去掉部分基本路徑,α放得越寬,可以被去掉的基本路徑就越多.另一方面,α從1.1 遞增到1.2 時(shí),索引變小的幅度明顯比α從1 遞增到1.1 時(shí)的小.這是因?yàn)锳CCTL 需要保證原圖中(α=1 時(shí))的每條基本路徑P,在索引中都存在路徑α-支配P,而不是在α=1.1 時(shí)保留的路徑的基礎(chǔ)上去掉α-支配的路徑.

圖3 的每組數(shù)據(jù)的后兩根柱子表示B 組數(shù)據(jù)集取α=1.1 和α=1.2 的索引大小,分別標(biāo)記為(B)1.1 和(B)1.2.留意到B 組的索引明顯比A 組要大.因?yàn)锽 組的圖中邊的費(fèi)用取值多樣,導(dǎo)致兩點(diǎn)間路徑的費(fèi)用取值也多樣,因此基本路徑數(shù)也比A 組要多.在B 組數(shù)據(jù)集中,從α=1.1 遞增到α=1.2 時(shí),索引大小有40%～50%的降幅.這是因?yàn)槁窂劫M(fèi)用值取值多樣,使得α變大后,有更多的路徑因?yàn)棣?支配被去掉.

綜合上述比較,索引大小與α取值和圖的費(fèi)用值浮動(dòng)的大小有關(guān):α越大,索引越小,但隨著α的增大,索引大小降幅變慢.另一方面,當(dāng)圖的路徑的費(fèi)用值浮動(dòng)越大時(shí),α的影響也越大.

6.3 建立索引的時(shí)間

圖4 顯示了兩大組數(shù)據(jù)建立索引的時(shí)間(單位:s).總體來說,A 組的建立索引時(shí)間小于B 組,因?yàn)锳 組的基本路徑數(shù)小于B 組.兩組數(shù)據(jù)的α=1.1 和α=1.2 的建立索引時(shí)間差別不大,可見,建立索引的瓶頸在于生成基本路徑,不在于計(jì)算α-支配路徑.這與第5.1 節(jié)對(duì)BuildIndex 算法的第18 行～第22 行的討論一致.在A 組數(shù)據(jù)內(nèi),α=1時(shí)建立索引的時(shí)間略小于α=1.1 和1.2,因?yàn)棣?1 時(shí)不需要執(zhí)行BuildeIndex 的第18 行～第22 行.留意到圖Sweden在α=1 時(shí)的執(zhí)行時(shí)間反而大于α=1.1 和1.2,這是因?yàn)棣?1 時(shí)基本路徑數(shù)多,對(duì)標(biāo)簽進(jìn)行排序的時(shí)間不可忽略.

Fig.4 Index construction time of group A and B,with with α=1,1.1,1.2 respectively圖4 A 組α取1、1.1、1.2 和B 組α取1.1、1.2 時(shí),各個(gè)圖建立索引的時(shí)間

7 結(jié)束語

本文研究了公交網(wǎng)絡(luò)下帶費(fèi)用限制的最小時(shí)態(tài)路徑查詢問題,提出了一種高效索引結(jié)構(gòu)ACCTL.ACCTL通過預(yù)計(jì)算圖中部分路徑的信息,使得任意查詢可以通過在ACCTL 中檢索路徑生成近似解,避免在原圖上盲目搜索,從而提高查詢效率.本文對(duì)ACCTL 的存儲(chǔ)結(jié)構(gòu)、建立索引方法和查詢算法做了多方面的討論和優(yōu)化.實(shí)驗(yàn)驗(yàn)證了ACCTL 索引支持的查詢速度比在原圖上采用Dijkstra 變種算法的查詢速度快2 個(gè)～3 個(gè)數(shù)量級(jí),并分析了ACCTL 的存儲(chǔ)空間和建立索引的時(shí)間的影響因素.