時間依賴圖下的最小費用路徑搜索

馬 慧，湯 庸，傅 瑜，易 鋒

(1. 電子科技大學(xué)中山學(xué)院 廣東 中山 528402；2. 華南師范大學(xué)計算機學(xué)院 廣州 510631)

最優(yōu)路徑查詢有著廣泛的應(yīng)用。近年來，學(xué)者們提出了多種最優(yōu)路徑查詢算法。針對不同的應(yīng)用場景，“最優(yōu)路徑”的查詢目標(biāo)也不一樣。例如用戶希望找到“距離最短”[1-3]、“最快到達(dá)”[4-9]或最優(yōu)k 條路徑[10-12]等。在一些應(yīng)用中，用戶希望在道路上所花的費用越少越好。例如物流公司的貨車在道路上行駛時間越長，耗油量就越大，需要找到一條耗油量最少的路徑[13-14]。

上述應(yīng)用可以用一個時間依賴圖來刻畫路網(wǎng)，圖模型上的每條邊附帶一個函數(shù)fi→j(t)，表示通過邊?vi,vj?的費用隨出發(fā)時刻t 而變化。給定起點vs和終點vd，查詢返回路徑P，使得P 的費用最小。允許在路徑的頂點上停留，以待在合適的時間繼續(xù)前行[13-20]。本問題的難點在于所研究的路徑的費用具有時間依賴性。即從起點vs到頂點vi的最小費用不是一個常數(shù)，而是一個以時間為自變量的函數(shù)，表示最小費用依賴于時間變化。

在路網(wǎng)中，每一個頂點都只能通過它的入邊鄰居到達(dá)。若能計算出到達(dá)vj的所有入邊鄰居vi的最小費用，便可計算出到達(dá)vj的最小費用。這個求值過程與最短路徑的經(jīng)典算法Dijkstra算法[1]類似?；诖?，文獻[13-14]采用了類Dijkstra 算法求解：從起點開始向四周擴散，按路徑費用升序擴展新路徑。該方法與Dijkstra 算法的區(qū)別在于：在傳統(tǒng)的靜態(tài)圖下，每個頂點vi在Dijkstra 搜索中僅被擴展一次，因為起點vs到vi的最短路距離只有一個值，本問題中每個頂點vi會多次被拿出來擴展，因為對于同一頂點的到達(dá)時間不同，費用也不同。設(shè)c⊥表示滿足查詢條件的最小費用，所有滿足條件gi(t)

如果把搜索過程中訪問過的頂點在表示路網(wǎng)的圖上作標(biāo)記的話，搜索空間大致分布在以vs為圓心、c⊥為半徑的圓內(nèi)。假設(shè)平均每個頂點被擴展k 次，搜索量大致用k 倍的以c⊥為半徑的圓的面積來衡量。為了減少搜索量，可分別從vs和終點vd出發(fā)啟動正向搜索和逆向搜索，兩個搜索交替進行，直到“相遇”為止?！跋嘤觥敝刚业揭粋€中間點vi，使得正向搜索已求出從vs到達(dá)vi的最小費用路徑，逆向搜索也求出從vi到vd的最小費用路徑，便可以從已搜索的路徑中生成從vs到vd的最小費用路徑。需說明的是，最小費用路徑不一定路過vi，細(xì)節(jié)將在第4 節(jié)中討論。直觀上，雙向搜索的搜索空間大致位于分別以vs、vd為圓心，半徑為c⊥/2 的兩個圓上。假設(shè)平均每個頂點被擴展了k 次，搜索空間大致等于兩個半徑為c⊥/2 的圓的面積之和的k 倍，較單向搜索的搜索量大大減少。

本文優(yōu)化了文獻[13-14]的算法，并在其基礎(chǔ)上提出了雙向搜索算法。雖然雙向搜索是一種常見的優(yōu)化算法，但路徑費用與時間相關(guān)，雙向搜索算法的難點在于：路徑的費用的時變依賴性給雙向搜索的處理細(xì)節(jié)和終止條件增加了復(fù)雜性。

1 相關(guān)工作

最優(yōu)路徑查詢的一個經(jīng)典問題是靜態(tài)圖上的最短路徑查詢?，F(xiàn)有的方法在大規(guī)模路網(wǎng)下，一個查詢平均只需數(shù)毫秒的時間便可完成[2]。但實際應(yīng)用中路網(wǎng)具有動態(tài)性，邊的權(quán)值依賴于時間變化。一類時間依賴圖基于離散模型，即每一條邊的權(quán)值依賴于某些離散的出發(fā)時間點[4-6]。另一類時間依賴圖基于連續(xù)模型，即每一條邊的權(quán)值是一個隨時間變化的連續(xù)函數(shù)[7-8]。由于公共交通網(wǎng)絡(luò)與路網(wǎng)有著天然的相似性，也有很多工作研究公共交通網(wǎng)絡(luò)下的最優(yōu)路徑規(guī)劃問題[9]。上述時間依賴圖下的最優(yōu)路徑查詢研究的共同點是計算“總耗時最少的路徑”，即用到達(dá)時刻減去出發(fā)時刻衡量路徑的耗時?？偤臅r最少的路徑不一定是路徑上途經(jīng)邊的費用之和最小的, 因此這些方法不能解決本文研究的問題。

本文的研究基于文獻[13]提出的模型：圖中每條邊?vi,vj?附有一個值wi→j，表示通過?vi,vj?的耗時；另有一個費用函數(shù)fi→j(t)，表示通過?vi,vj?的費用依賴于頂點vi的出發(fā)時刻t，路徑允許在頂點上等待，以實現(xiàn)費用最小。在此模型的基礎(chǔ)上，文獻[14]提出了一種兩階段搜索方法Two-Step，將文獻[13]中的每條邊的wi→j擴展成時間依賴函數(shù)，并對文獻[13]的方法做了改進，包括wi→j是時間依賴函數(shù)的場景。文獻[15]提出的問題模型與文獻[13-14]相 似，每 條 邊?vi,vj?只 有 一 個 函 數(shù)fi→j(t)，fi→j(t)表示在t 時刻通過?vi,vj?的耗時，目標(biāo)求解路上耗時(on-road travel time)最小的路徑，允許路徑在頂點上等待。文獻[16]在文獻[15]的基礎(chǔ)上采用車輛的歷史軌跡數(shù)據(jù)來構(gòu)造時間依賴圖，并提出了一種求近似解的算法，加快了查詢速度。另有工作研究基于離散時間模型的允許在頂點上等待的最小費用路徑查詢[18,20]。

2 問題描述

本文沿用文獻[13]的時間依賴圖模型和最小費用路徑查詢問題的定義。

定義 1 時間依賴圖。時間依賴圖是一個有向圖，記作GT=(V, E, W, F)。V={vi}是頂點的集合，E?V×V 是邊的集合。?vi,vj?∈E 表示一條從頂點vi到頂點vj的有向邊。每條邊?vi,vj?附有一個權(quán)值wi→j∈W，表示通過?vi,vj?的耗時；另有函數(shù)fi→j(t)∈F表示在t 時刻通過?vi,vj?的費用。fi→j(t)用分段常量函數(shù)表示：

為了表述清晰，假設(shè)通過?vi,vj?的時間wi→j是一個非負(fù)常數(shù)。需說明的是，本文的算法也適用于當(dāng)wi→j是一個關(guān)于t 的函數(shù)的情形，只要wi→j(t)滿足FIFO 性質(zhì)：t1

同文獻[13-14]一樣，本文假設(shè)?f∈F 的所有分段區(qū)間均為左閉右開區(qū)間。當(dāng)任意一端改成開區(qū)間或閉區(qū)間時，本文討論的算法依然有效。

定義 2 路徑 P=v1@t1→v2@t2→…→vk@tk→vk+1是圖GT的一條路徑，其中?vi,vi+1?∈E(1≤i≤k)。P 表示在t1時刻從頂點v1出發(fā)，在t1+w1→2時刻到達(dá)v2，然后在t2時刻從v2出發(fā)，···，到達(dá)vk后在tk時刻出發(fā)，最后到達(dá)vk+1。路徑上允許到達(dá)頂點vi后，等待一段時間再出發(fā)，以期待P 的費用更小。P 上的時間約束滿足ti+wi→i+1≤ti+1。P 的費用記為：

定義 3 時間依賴圖上的具有時間限制的最小費用路徑查詢。給定一個時間依賴圖GT，起點vs，終點vd，時間td、ta，GT上的具有時間限制的費用最小路徑查詢返回路徑P，使得：1)P 在td 或之后從vs出發(fā)，在ta 或之前到達(dá)vd；2)所有滿足條件1)的路徑中，P 的費用最小。

圖1a 顯示了一個時間依賴圖，邊上的數(shù)字表示wi→j。圖1b～圖1f 為各條邊的費用函數(shù)。若查詢從v0到v3的最小費用路徑，td=0，ta=10，則P=v0@2→v2@5→v3是其中一個解，cost(P)=5。

圖1 一個時間依賴圖及各條邊的費用函數(shù)

3 逆向搜索

表1 文中常用符號的含義

文中變量在表1 中給出具體定義。

3.1 出發(fā)時間?最小代價函數(shù)

因為路徑的費用與時間相關(guān)，所以定義頂點vi的出發(fā)時間?最小代價函數(shù)為gi(t)，表示若在t 時刻位于vi，則在ta 時刻或之前到達(dá)vd的最小費用。在t 時刻位于vi，指在t 時刻出發(fā)，或者在vi上等待至t 時刻后的某個時刻出發(fā)。

查詢的起始頂點是vs，故搜索的目標(biāo)是計算gs(t)的最小值。

3.2 更新出發(fā)時間?最小費用函數(shù)

本節(jié)討論在已知頂點vi的出邊鄰居的出發(fā)時間?最小費用函數(shù)的情況下，如何更新gi(t)。用Ni+表示vi的出邊鄰居的集合。設(shè)vj∈Ni+，gi→j(t)表示在t 時刻位于vi，途經(jīng)?vi,vj?再從vj到達(dá)vd的最小費用。由于從vi出發(fā)的路徑只能通過Ni+中的頂點到達(dá)vd，所以gi(t)的值取決于gi→j(t) (vj∈Ni+)：

gi(t)的求解過程可以分成兩步：1) 求gi→j(t)；2) 按式(1)更新gi(t)。第1)步的計算如下。

gi(t)的定義域為[edti，ldti]。各頂點的edti值可以在以wi→j為邊?vi,vj?的權(quán)值圖上，從vs出發(fā)調(diào)用一次Dijkstra 搜索求得；同理，各頂點的ldti值也可以從vd出發(fā)調(diào)用一次逆向Dijkstra 搜索求得。

若不考慮在vi上等待，有：

若考慮上在vi上等待，則gi→j(t)是一個單調(diào)遞增函數(shù)：若t1

可見gi→j(t)的計算分成兩步：首先通過式(2)計算gi→j(t)，然后將gi→j(t)變成單調(diào)函數(shù)。圖2 為求g1→3(t)的計算過程，已知g3(t)=0。

圖2 求g1→3(t)的過程

引理 1 若已知gj(t)，上述方法計算的gi→j(t)是在t 時刻位于vi，途經(jīng)邊?vi,vj?到達(dá)vd的最小費用函數(shù)。

3.3 增量式計算gs(t)

回顧查詢的目標(biāo)是求gs(t)的最小值，并非gs(t)在整個定義域上的值。已知gj(t)求gi→j(t)，對gj(t)的定義域按gj(t)的取值分成若干段，按定義域上的取值從小到大的順序求gi→j(t)在各分段的值。所以在搜索過程中，也可以先后用gj(t)的某個分段的值計算gi→j(t)，不需要在完整計算出gj(t)后才計算gi→j(t)。增量式計算的思想是：為了減少計算量，當(dāng)gj(t)的某個分段的值已被正確計算出來后，才用來計算gi→j(t)。計算過程如算法1 所示。

算法1 Reverse Search

輸入：GT，起點vs、終點vd、最早出發(fā)時刻td、最晚到達(dá)時刻ta。

輸出：最小費用。

1) 分別從vs和vd調(diào)用Dijkstra 搜索，用td、ta 求各頂點vi的edti和ldti值。

2) ?vi∈V?{vd}, gi(t)=+∞; gd(t)=0; Ti=edti;

3) 將元組(0, vd, edtd, ldtd)加進H

4) while (!H.empty()) do

5) 從H 彈出元組(cj, vj, tdj, taj)

6) if (vj==vs) then return cj

7) for each vi∈Nj?do

8) gi→j(t?wi→j) = fi→j(t?wi→j) + cj, tdj≤ t < taj

9) 將gi→j(t)變成單調(diào)遞增函數(shù)，更新gi;

10) ci= min{gi(t) | Ti≤t}

11) 設(shè)gi(t)取值ci的區(qū)間右端點是tai;

12) 將元組(ci, vi, Ti, tai)加進H

13) Tj= taj;

14) cj= min{gj(t) | t≥taj}

15) 設(shè)gj(t)取值cj的區(qū)間的右端點是taj;

16) 將元組(cj, vj, Tj, taj)加進H；

17) return +∞;

除vd以外，各頂點vi的gi(t)=+∞，表示gi(t)在定義域[edti, ldti]上的取值未確定，Ti的取值將在下文中解釋。算法迭代地選取某個頂點vj和相應(yīng)的時間區(qū)間擴展，更新vj的入邊鄰居的費用，直到找到從vs出發(fā)的最小費用路徑為止。

算法維護一個最小堆H，H 中的每個元素是一個四元組(cj, vj, tdj, taj)，表示頂點vj的函數(shù)gj(t)在區(qū)間[tdj,taj)的取值為cj。H 中的元組以cj為關(guān)鍵字排序。初始時H 僅包含一個元組(0, vd, edtd, ldtd)(第3 行)。當(dāng)(cj, vj, tdj, taj)彈出時，gj(t)在[tdj,taj)區(qū)間上的取值已被正確計算出來，為cj，這一點將在定理1 中證明。當(dāng)vs首次彈出時，最小費用路徑已找到(第6 行)。

若vj不是vs，用vj在[tdj, taj)區(qū)間上的取值cj計算gi→j(t)(第7～12 行，詳細(xì)的計算過程將在下一段討論)。每個頂點vj附帶一個值Tj，表示gj(t)的已確定值的時間區(qū)間的右端點。初始時，Tj=edtj。當(dāng)vj首次從H 彈出時，由定理1 可知，cj是gj(t)的最小值，taj是gj(t)=cj的時間區(qū)間的右端點，接下來用gj(t)在[edtj, taj)這一段的值計算gi→j(t)。由于gj(t)是單調(diào)遞增函數(shù)，所以gj(t)的下一個最小值的區(qū)間的左端點是taj，于是在第13 行令Tj= taj，表示下一步將用gj(t)在[Tj, ·)上的最小值更新gi→j(t)。因此，(cj, vj, tdj, taj)擴展完畢后，繼續(xù)找出gj(t)在區(qū)間在[Tj, ·)上的最小值cj，將vj、cj和cj取值對應(yīng)的時間區(qū)間加進H。

擴展vj的詳細(xì)過程如下。第8)行計算得到的gi→j(t)并非單調(diào)函數(shù)，需要把gi→j(t)變成單調(diào)遞增函數(shù)。按式(1)更新gi(t)，之后需要重新找出gi(t)在未確定取值的時間區(qū)間上的最小值ci(第10)行)。第12)行中，若H 中沒有包含頂點是vi的四元組，則將(ci, vi, Ti, tai)加進H；若H 中包含頂點是vi的四元組(ci', vi', tdi', tai')，而且費用大于ci，則用(ci, vi, Ti, tai)代替(ci', vi', tdi', tai')。

計算過程如圖3 所示。求v0到v3的最小費用路徑，td=0, ta=10。計算各頂點的最早出發(fā)時刻和最晚出發(fā)時刻，得到頂點vi的gi(t)函數(shù)的定義域分別是：v0[0,5], v1[3,8], v2[3,8], v3[5,10]。初始時，T0=0, T1=3, T2=3, T3=5。首先，g3(t)=0，H 包含四元組(0,v3,5,10)。

第一次迭代，(0,v3,5,10)從H 中彈出。擴展?v1,v3?，得到的g1(t)如圖3a 所示，細(xì)實線表示將g1(t)變成單調(diào)遞增函數(shù)，下同。此時g1(t)的最小值是5，所以將元組(5,v1,3,8)加進H。同理，擴展?v2,v3?，得到g2(t)如圖3b 所示，將(3,v2,3,7)加進H。

圖3 v0 到v3 的最小費用路徑的計算過程

第二次迭代，(3,v2,3,7)從H 中彈出。擴展?v0,v2?，得到g0(t)如圖3c 所示，將元組(5, v0, 0, 4)加進H。擴展?v1,v2?得到的g1(t)無更新。至此，(3,v2,3,7)擴展完畢，將T2改成7。g2(t)在t≥7 上的最小值是5，所以將(5,v2,7,8)加進H。

第三次迭代，(5,v0,6,8)從H 中彈出，至此已找到v0到v3的最小費用5。

3.4 算法Reverse Search 的改進與正確性證明

算法Reverse Search 與Two-Step 算法相比，在兩方面縮小了搜索空間：1) Reverse Search 將gi(t)的定義域縮小至[edti,ldti]，而Two-Step 把正向搜索的定義域僅限定在[edti,ta]。實際上[ldti,ta]區(qū)間上的計算是無意義的。尤其對于路徑上靠近起點的頂點vi，其ldti的值可能比ta 小很多，且在[ldti, ta]區(qū)間上的費用也比小(由于vi靠近起點)，這意味著搜索初期用了[ldti, ta]中的一些子區(qū)間擴展路徑，而這部分?jǐn)U展是不可能生成在ta 前到達(dá)終點的路徑的；2) 在第8)行，Reverse Search僅用[Tj, taj) 區(qū)間計算gi→j(t)，剩余區(qū)間[taj, ·)不用。這是因為此時gj(t)在[taj, ·)上的取值尚未確定，仍可能被vj的出邊鄰居更新，用未確定的值來計算gi→j(t)也是無意義的。

證明方法如下。

定 理 1 在Reverse Search 中，當(dāng)(cj, vj, tdj,taj)彈出時，gj(t)函數(shù)在[tdj, taj)上的取值已確定，即為cj。

證明：以示區(qū)分，用gj(t)表示正確的出發(fā)時間?最小費用函數(shù)；用gj*(t)表示元組(cj, vj, tdj, taj)彈出時，當(dāng)前計算出的值。證明gj*(t)=gj(t), tdj≤t

采用數(shù)學(xué)歸納法。首次迭代(0, vd, edti, ldtd)彈出時, gd*(t)=gd(t)=0。假設(shè)在前k 次迭代中命題成立，現(xiàn)證明第k+1 次迭代時命題仍然成立。不妨設(shè)存在tj∈[tdj, taj)，使得gj*(tj)≠gj(tj)。由于gj(tj)表示正確的最小費用，所以有g(shù)j*(tj) >gj(tj)。

設(shè)在tj時刻從vj出發(fā)的最小費用路徑Pj=vj@tj→···vu@tu→vw@tw→···→vd。 由 于 ： gj*(t)≠gj(tj)且gd*(t)=gd(t)=0，所以在Pj上，存在兩個相鄰的頂點vu和vw，vu在時刻tu出發(fā)，vw在時刻tw出發(fā)，使得在前k 次迭代中，vw的包含tw的時間區(qū)間的元組曾經(jīng)從H 中彈出，vu的包含tu的時間區(qū)間的元組尚未從H 中彈出。分別記Pu(Pw)為Pj上在tu時刻從vu出發(fā)(在tw時刻從vw出發(fā))的子路徑。

每條邊上的費用都是非負(fù)數(shù)，所以cost(Pu)≤cost (Pj)。又 因 為：cost (Pu)=fu→w(tu)+cost (Pw)且Pj是最小費用路徑，即cost(Pj)=gj(tj)，所以：

gw(tw)是在時刻tw位于vw、到達(dá)vd的最小費用，所以gw(tw)≤cost(Pw)。結(jié)合式(3)，有:

vw的包含tw的時間區(qū)間的元組從H 彈出時，曾用fu→w(t)計算gu→w(t)，接著用gu→w(t)更新gu*(t)，因 此 gu*(tu)≤fu→w(tu)+gw*(tw)。 按 歸 納 ， vw的包含tw的時間區(qū)間的元組從H 彈出時，gw*(tw)=gw(tw)。因此：

結(jié)合式(4)和式(5)，可得gu*(tu)≤gj(tj)

4 雙向搜索

正向搜索計算頂點vi的到達(dá)時間?費用函數(shù)：gi(t)表示在td 時刻或之后從vs出發(fā)，若在t 時刻位于vi時的最小費用。搜索過程參考第3 節(jié)的討論。

雙向搜索的思路是：分別從vs和vd啟動正向搜索和逆向搜索，兩個搜索交替進行，直到兩個搜索相遇為止。具體地，用c⊥表示當(dāng)前找到的路徑的最小費用，初始時，c⊥=+∞。用gi→(t)表示頂點vi的到達(dá)時間?最小費用函數(shù)，gi←(t)表示vi的出發(fā)時間?最小費用函數(shù)。分別用H→和H←表示正向搜索和逆向搜索的最小堆。假設(shè)當(dāng)前四元組(cj, vj, tdj,taj)從H←彈出，vi是vj的一個入邊鄰居。利用算法1 更新gi←(t)后，利用gi→(t)更新c⊥:

雙向搜索的終止條件與重構(gòu)最小費用路徑：在搜索過程中，c⊥的值不斷地更新。當(dāng)正向(或逆向)搜索彈出頂點vmid，使得vmid的正向搜索的已確定值的時間區(qū)間中存在時間點tf，且vmid的逆向搜索的已確定值的時間區(qū)間中存在時間點tb，滿足tf≤tb，搜索終止，c⊥即為所求的最小費用。最小費用路徑并不一定途經(jīng)vmid，而是途經(jīng)令c⊥取得最小值的頂點vi。

設(shè)當(dāng)前從最小堆中彈出頂點v，如何判斷v 存在時間點tf與tb， tf?tb， 且 g→i(tf) 和 g←i(tb)的值均已確定回顧在逆向搜索中，每個頂點vi附帶一個值Ti(在雙向搜索中，記為Ti←)，表示已確定值的時間區(qū)間的右端點；對稱地，在正向搜索中，每個頂點vi附帶一個值Ti→，表示已確定值的時間區(qū)間的左端點。在搜索過程中，Ti←從初值edti開始遞增；Ti→從ldti開始遞減。當(dāng)Ti→≤Ti←時，表明存在tf和tb如上述描述。

定理 2 當(dāng)雙向搜索算法終止時，所得的c⊥即為最小費用。

證明：首先，當(dāng)四元組(cj, vj, tdj, taj)從正向搜索的最小堆H→彈出時，gj→(t)在[tdj, taj)區(qū)間上的取值已確定，即為cj。此證明過程與定理1 同理。

設(shè)正向(或逆向)搜索從最小堆中彈出頂點vmid，使得vmid在正向和逆向搜索的已確定值的時間區(qū)間存在時間點tf和tb，滿足tf≤tb，搜索終止。假設(shè)正確的最小費用是c，分兩種情況：1) c=gmid→(tf)+gmid←(tb)；2) c

1) 若c=gmid→(tf)+gmid←(tb)，說明vmid在一條最小費用路徑P 上，在tf時刻到達(dá)vmid，在tb時刻離開vmid。設(shè)P 上vmid的前驅(qū)頂點是vx，vmid的后繼頂點是vy。若vx在正向搜索中先出堆，vy在逆向搜索中后出堆，則在vx出堆時，由引理1 可知，能通過擴展邊?vx, vmid?正確計算出gmid→(tf)的值；之后在vy出堆時，能通過擴展邊?vmidvy?正確計算出gmid←(tb)。再通過式(6)計算出c⊥=gmid→(tf)+gmid←(tb)。對稱地，若vy在逆向搜索中先出堆，vx在正向搜索中后出堆，也能正確計算出c⊥。

2) c

設(shè)Px→在時刻tax到達(dá)vx，由gx→(t)的定義得：

由于cost(P)=cost(Py→)+cost(Py←)，結(jié)合本節(jié)的假設(shè)cost(P)

結(jié)合式(7)和式(9)，cost(Py←)

5 實 驗

實驗采用Visual Studio 2017Community C++編寫，Windows 10 平臺運行，機器配置Intel(R) Core(TM) i78700K CPU 和64 GB 內(nèi)存。

5.1 數(shù)據(jù)集

本文采用兩組路網(wǎng)數(shù)據(jù)集測試(http://www.cs.utah.edu/～lifeifei/SpatialDataset.htm)。OL 描述了奧爾登堡的路網(wǎng)，包括6 105 個頂點和7 035 條邊；CA 描述了加利福尼亞州的路網(wǎng)，包括20 147 個頂點和21 692 條邊。同文獻[13-14]的測試方法，本文在路網(wǎng)的基礎(chǔ)上生成時間依賴圖。圖中每條邊?vi,vj?的時間代價wi→j取路網(wǎng)的邊的權(quán)值。費用函數(shù)fi→j(t)的定義域設(shè)為[0, 20 000]。將fi→j(t)的定義域隨機分成k 段，每一段上隨機生成一個[20,100]范圍內(nèi)的整數(shù)。k 分別取10 和20。

分別在OL 和CA 上隨機生成查詢集。查詢集共包含10 000 個查詢，隨機生成每個查詢的起點和終點。首先計算出每個查詢的從起點到終點的最快到達(dá)時間，近似地用來衡量起點到終點的遠(yuǎn)近。將這10 000 個查詢按最快到達(dá)時間升序排序，每1 000 個查詢分成一組，分別將這10 組查詢記為Q1,Q2, ···, Q10。于是，Q1 組內(nèi)的查詢的起點和終點相距較近，Q10 組內(nèi)的相距較遠(yuǎn)。為了保證大部分查詢有解，每個查詢的td 限定在[0, 10 000]范圍，ta 在[10 000, 20 000]范圍內(nèi)隨機生成。

實驗分別在以下4 方面測試算法：1) Reverse Search 算法與文獻[13-14]的Two-Step 算法的效率對比；2)～4)從起點和終點之間的遠(yuǎn)近、圖的規(guī)模和費用函數(shù)上分段數(shù)量k 這3 方面對比單向(正向)搜索和雙向搜索的性能。以示公平，單、雙向搜索均使用了第3 節(jié)提出的增量式搜索方法。算法考察的性能指標(biāo)為平均每個查詢的耗時，以ms 為單位。

5.2 實驗結(jié)果

1) Reverse Search 與Two-Step 算法效率對比。圖4 顯示了OL 數(shù)據(jù)集k=10 的時間依賴圖下，Reverse Search 和Two-Step 對10 組查詢集的平均耗時。起止點相距越遠(yuǎn)的查詢效率差別越大。這是因為Reverse Search 與Two-Step 相比，縮小了每個頂點的有效時間區(qū)間，而且等某個頂點在某時間段出發(fā)的最小費用正確計算出來以后，才用來計算擴展路徑的費用。這兩個優(yōu)化能減少部分無用的計算。

圖4 k=10 下的平均查詢時間

2) 起點和終點之間的遠(yuǎn)近對單向搜索和雙向搜索的效率影響。圖5 顯示了OL 和CA 在k=10的時間依賴圖下，查詢集Q1,Q2,···,Q10 每個查詢的平均花費時間，y 軸用對數(shù)的比例顯示。圖例標(biāo)記的前兩個字母表示路網(wǎng)名稱，S 表示單向搜索，B 表示雙向搜索。隨著起點與終點的距離增加，兩者的效率差尤為明顯。例如在OL 數(shù)據(jù)集下的R1 查詢集中，單向、雙向搜索平均每個查詢花費1.25 ms 和0.98 ms；在R10 查詢集中，單向、雙向搜索平均每個查詢花費15.87 ms 和4.18 ms，雙向搜索耗時僅是單向搜索的26.3%。造成較大的效率差是因為雙向搜索能減少搜索過程中訪問的頂點數(shù)，而由于搜索過程中一個頂點可能多次被多次訪問，每次訪問對應(yīng)不同的時間區(qū)間。因此，雙向搜索通過減少訪問的頂點數(shù)提高了查詢效率。留意到實驗中的單向搜索已經(jīng)使用了第3 節(jié)提出的增量式搜索優(yōu)化。與Two-Step 相比，對于查詢相距較遠(yuǎn)的頂點，雙向搜索的平均每個查詢耗時約是Two-Step 的10%。

圖5 OL 和CA 的k=10 下的平均查詢時間

3) 圖的規(guī)模對算法效率的影響。從圖5 顯示的數(shù)據(jù)看出，CA 的頂點數(shù)和邊數(shù)約是OL 的4 倍，但平均查詢時間CA 約是OL 的10 倍。而且隨著查詢起止點的距離增大，兩個圖上的查詢的效率差尤為明顯。這是因為圖規(guī)模變大后，兩點之間的可選的路徑數(shù)暴漲，所以查詢也更耗時。

4) 函數(shù)上的分段數(shù)量k 的影響。圖6 以CA 為例顯示了k=10 和k=20 時的平均查詢時間?？傮w來說，不管用單向搜索還是雙向搜索，k 越大，平均每個查詢時間越長。這是因為在搜索過程中每個頂點會反復(fù)從最小堆中彈出，每次彈出的頂點附帶不同的時間區(qū)間，分段越多頂點上的時間區(qū)間也越多，因此頂點反復(fù)彈出次數(shù)越多。圖7 從另一個角度展示了當(dāng)路網(wǎng)與查詢集固定的情況下，k=10 和k=20 下的兩種搜索的查詢時間對比。有趣的是，不管使用哪種搜索，k 變大時引起的平均查詢時間增加的比率相對穩(wěn)定。

圖6 k=10, 20 下兩種搜索的平均查詢時間

圖7 平均查詢時間對比

6 結(jié) 束 語

本文提出了一種時間依賴圖下的最小費用路徑查詢的高效算法。首先通過縮小頂點的有效時間區(qū)間與延遲計算路徑費用的方法減少部分無意義的計算；然后提出雙向搜索的方法削減了搜索空間，提高了算法的效率。理論上證明了方法的正確性，實踐上用真實路網(wǎng)驗證了方法的有效性。下一步工作擬進一步將大規(guī)模圖查詢的索引方法引入本問題中，研究在時間依賴圖下的最小費用路徑索引算法。