公交網絡下的一種費用限制最小時態路徑查詢索引?

馬 慧 , 湯 庸 , 梁瑞仕

1(電子科技大學 中山學院 計算機學院,廣東 中山 528400)

2(華南師范大學 計算機學院,廣東 廣州 510631)

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

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

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

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

綜上所述,帶費用限制的最短路徑查詢和時間信息圖下最小時態路徑查詢這兩個問題已經有索引方法提供高效的查詢,但是目前,關于帶費用限制的最小時態路徑查詢的研究均是在原圖上做搜索,在大規模圖上查詢效率低下,因此需要仿照圖查詢的傳統做法,預先對圖建立索引,再設計相應的查詢算法利用索引查詢結果.

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

本文第1 節給出問題的描述和相關符號的定義.第2 節給出一種基于Dijkstra 算法的方法,這種方法是構建索引的核心算法.第3 節介紹ACCTL 的設計思路.第4 節介紹ACCTL 的查詢算法.第5 節介紹ACCTL 的預處理構建索引算法.第6 節采用交通數據集測試ACCTL 的查詢效率、空間大小和建立索引的時間.最后總結全文.

1 問題描述

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

本文研究的帶費用限制的最早到達路徑、最晚出發路徑和最短耗時路徑定義如下.

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

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

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

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

Fig.1 A time information graph with costs圖1 一個帶費用值的時間信息圖

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

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

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

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

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

表1 給出了全文常用的符號及含義.

Table 1 Table of notations表1 符號表

2 一種基于Dijkstra 算法的方法

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

2.1 核心算法Dijk-CCMTP

求解帶費用限制的最小時態路徑需要用到的一個關鍵概念叫做路徑支配.

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

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

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

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

算法1.Dijk-CCMTP 算法.

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

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

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

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

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

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

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

2.2 基于Dijk-CCMTP的查詢算法

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

帶費用限制的最晚出發路徑查詢與帶費用限制的最早到達路徑查詢是對稱的.帶費用限制的最晚出發路徑查詢從終點d出發做反向搜索擴展回起點,即擴展路徑時訪問頂點關聯的入邊.在最小堆H中,費用小的路徑優先出堆;費用相等的路徑出發時刻晚的優先出堆.

帶費用限制的最短耗時路徑查詢并不能調用一次Dijk-CCMTP求解,這是因為路徑的耗時與路徑的出發時刻、到達時刻均有關系,因此需要枚舉s的不同的出發時刻,多次調用Dijk-CCMTP 求解.留意到路徑P只可能被比出發時刻不早于它的路徑所支配,所以可以按出發時刻從晚到早的順序調用Dijk-CCMTP.每次調用Dijk-CCMTP 時重用前一輪調用Dijk-CCMTP 時設置的C(e)值,即調用了Dijk-CCMTP 求解在t1時刻出發的路徑以后,下一輪求在t2時刻(t2

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

定理1 可以由引理1 和引理3 推導證明.

3 索引ACCTL 的框架

本節介紹索引ACCTL 的設計思想.ACCTL 的構建基于一個頂點的全序關系,全序關系用來衡量頂點在圖中的重要程度.在公共交通網絡中,一些交通樞紐很重要,因為相距較遠的兩個地方通常在交通樞紐換乘.表現在圖中,一個頂點所在的帶費用限制的最小時態路徑越多,它就越重要,稱它等級越高.本文用o(v)表示將頂點按重要程度從高到低排序后,頂點v在序列中的位置.若o(v)

3.1 ACCTL的設計思想

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

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

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

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

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

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

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

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

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

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

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

3.2 標簽去冗余

表2 的標簽存在冗余,影響到索引的存儲空間大小和查詢效率.例如l3和l4均表示從v1到v2的路徑,頂點v1只需要保存一份即可,無需在l3和l4中均保存.另外,僅具有共同端點的標簽才有可能匹配上.例如查詢從v4到v2的路徑時,可能與l9匹配的標簽只有l3和l4,因為它們的起點v1等于l9的終點.l2的起點與l9的終點不相同,因此查詢時無需掃描l2.基于上述考慮,ACCTL 將表示連接相同頂點的路徑的標簽分成一個標簽組.表3 顯示了分組的標簽,這也是ACCTL 的存儲格式.

定義10(ACCTL 索引).給定近似因子α,圖G的ACCTL 索引預先對每個頂點v計算兩個標簽組集合L+(v)和L-(v),滿足:

(3)對于任意的從頂點s到頂點d的帶費用限制的最小時態路徑查詢Q,設Popt是Q的精確解,則在L+(s)內的某個標簽組中,存在標簽(下文中,對于標簽中暫不需關注的項采用符號?表示)的對應路徑P+,在L-(d)內的某個標簽組中,存在標簽的對應路徑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 節介紹查詢算法,然后在第5 節討論索引的構建方法,因為索引構建方法比查詢方法復雜.

4 查詢算法

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

4.1 查找標簽

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

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

算法2.EAPQuery.

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

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

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

4.2 路徑還原

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

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

5 ACCTL 索引的構建

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

5.1 計算基本路徑

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

算法3.BuildIndex.

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

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

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

(3)由于終點d和費用上限θ在構建索引時未知,所以在BuildIndex 中不利用d和θ進行剪枝.

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

對于每條標記為保留的路徑,第23 行、第24 行生成標簽l并加進相應的標簽組.最后,第26 行調用反向Dijk-CCMTP 算法計算到達vi的基本路徑,計算過程與第4 行～第25 行相似.

5.2 選擇路徑

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

算法4.MarkPrune.

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

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

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

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

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

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

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

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

(2.2)P不早于Popt出發且不晚于Popt到達.

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

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

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

5.3 點序o的計算

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

6 實 驗

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

Table 4 Characteristics of datasets表4 數據集特征

6.1 查詢時間

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

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

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

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

總體看來,基于ACCTL 索引的平均查詢時間比基于Dijkstra 的搜索快2 個～3 個數量級.這是因為ACTTL在預先計算的路徑集中查找路徑生成解,避免在原圖上盲目搜索.就各組數據的基于ACCTL 索引的查詢時間對比,查詢時間與索引大小和圖的度數有關.總體來說,索引越大,查詢時間就越長.圖3 的各組數據的第1 根柱子顯示了α=1 時的索引大小.留意到Madrid 的索引比LosAngeles 和Berlin 的都小,但查詢時間長.這是因為Madrid的平均頂點度數大.頂點v的度數越大,v到達圖中其他頂點(或從圖中其他頂點到達v)的可能性越大,即L+(s)和L-(d)有擁有相同端點的標簽組越多,所以需要匹配的標簽組越多,查詢時間越長.此外,最短耗時路徑查詢的速度比最早到達路徑查詢的稍慢,甚至在個別數據中最短耗時路徑的查詢比最早到達路徑的更快(例如Berlin 的Dijk-CCEAP 與Dijk-CCSDP、SaltLakeCity 的ACCTL-CCEAP 與ACCTL-CCSDP),這是因為最短耗時路徑查詢受到到達時刻t′的約束,可以幫助剪枝掉部分搜索;而最早到達路徑的到達時刻沒有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 時,各個圖的索引大小(MB)

6.2 索引的大小

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

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

圖3 的每組數據的后兩根柱子表示B 組數據集取α=1.1 和α=1.2 的索引大小,分別標記為(B)1.1 和(B)1.2.留意到B 組的索引明顯比A 組要大.因為B 組的圖中邊的費用取值多樣,導致兩點間路徑的費用取值也多樣,因此基本路徑數也比A 組要多.在B 組數據集中,從α=1.1 遞增到α=1.2 時,索引大小有40%～50%的降幅.這是因為路徑費用值取值多樣,使得α變大后,有更多的路徑因為α-支配被去掉.

綜合上述比較,索引大小與α取值和圖的費用值浮動的大小有關:α越大,索引越小,但隨著α的增大,索引大小降幅變慢.另一方面,當圖的路徑的費用值浮動越大時,α的影響也越大.

6.3 建立索引的時間

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

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 時,各個圖建立索引的時間

7 結束語

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