馬 慧，湯 庸，傅 瑜，易 鋒

(1. 電子科技大學(xué)中山學(xué)院 廣東 中山 528402；2. 華南師范大學(xué)計(jì)算機(jī)學(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)用中，用戶希望在道路上所花的費(fèi)用越少越好。例如物流公司的貨車在道路上行駛時間越長，耗油量就越大，需要找到一條耗油量最少的路徑[13-14]。

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

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

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

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

1 相關(guān)工作

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

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

2 問題描述

本文沿用文獻(xiàn)[13]的時間依賴圖模型和最小費(fèi)用路徑查詢問題的定義。

定義 1 時間依賴圖。時間依賴圖是一個有向圖，記作GT=(V, E, W, F)。V={vi}是頂點(diǎn)的集合，E?V×V 是邊的集合。?vi,vj?∈E 表示一條從頂點(diǎn)vi到頂點(diǎn)vj的有向邊。每條邊?vi,vj?附有一個權(quán)值wi→j∈W，表示通過?vi,vj?的耗時；另有函數(shù)fi→j(t)∈F表示在t 時刻通過?vi,vj?的費(fèi)用。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

同文獻(xiàn)[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時刻從頂點(diǎn)v1出發(fā)，在t1+w1→2時刻到達(dá)v2，然后在t2時刻從v2出發(fā)，···，到達(dá)vk后在tk時刻出發(fā)，最后到達(dá)vk+1。路徑上允許到達(dá)頂點(diǎn)vi后，等待一段時間再出發(fā)，以期待P 的費(fèi)用更小。P 上的時間約束滿足ti+wi→i+1≤ti+1。P 的費(fèi)用記為：

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

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

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

3 逆向搜索

表1 文中常用符號的含義

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 增量式計(jì)算gs(t)

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

算法1 Reverse Search

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

輸出：最小費(fèi)用。

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

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

3) 將元組(0, vd, edtd, ldtd)加進(jìn)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ū)間右端點(diǎn)是tai;

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

13) Tj= taj;

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

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

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

17) return +∞;

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

算法維護(hù)一個最小堆H，H 中的每個元素是一個四元組(cj, vj, tdj, taj)，表示頂點(diǎn)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ū)間上的取值已被正確計(jì)算出來，為cj，這一點(diǎn)將在定理1 中證明。當(dāng)vs首次彈出時，最小費(fèi)用路徑已找到(第6 行)。

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

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

計(jì)算過程如圖3 所示。求v0到v3的最小費(fèi)用路徑，td=0, ta=10。計(jì)算各頂點(diǎn)的最早出發(fā)時刻和最晚出發(fā)時刻，得到頂點(diǎn)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 中彈出。擴(kuò)展?v1,v3?，得到的g1(t)如圖3a 所示，細(xì)實(shí)線表示將g1(t)變成單調(diào)遞增函數(shù)，下同。此時g1(t)的最小值是5，所以將元組(5,v1,3,8)加進(jìn)H。同理，擴(kuò)展?v2,v3?，得到g2(t)如圖3b 所示，將(3,v2,3,7)加進(jìn)H。

圖3 v0 到v3 的最小費(fèi)用路徑的計(jì)算過程

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

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

3.4 算法Reverse Search 的改進(jìn)與正確性證明

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

證明方法如下。

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

證明：以示區(qū)分，用gj(t)表示正確的出發(fā)時間?最小費(fèi)用函數(shù)；用gj*(t)表示元組(cj, vj, tdj, taj)彈出時，當(dāng)前計(jì)算出的值。證明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)表示正確的最小費(fèi)用，所以有g(shù)j*(tj) >gj(tj)。

設(shè)在tj時刻從vj出發(fā)的最小費(fèi)用路徑Pj=vj@tj→···vu@tu→vw@tw→···→vd。 由 于 ： gj*(t)≠gj(tj)且gd*(t)=gd(t)=0，所以在Pj上，存在兩個相鄰的頂點(diǎn)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èi)用都是非負(fù)數(shù)，所以cost(Pu)≤cost (Pj)。又 因 為：cost (Pu)=fu→w(tu)+cost (Pw)且Pj是最小費(fèi)用路徑，即cost(Pj)=gj(tj)，所以：

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

vw的包含tw的時間區(qū)間的元組從H 彈出時，曾用fu→w(t)計(jì)算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 雙向搜索

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

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

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

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

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

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

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

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

實(shí)驗(yàn)采用Visual Studio 2017Community C++編寫，Windows 10 平臺運(yùn)行，機(jī)器配置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 個頂點(diǎn)和7 035 條邊；CA 描述了加利福尼亞州的路網(wǎng)，包括20 147 個頂點(diǎn)和21 692 條邊。同文獻(xiàn)[13-14]的測試方法，本文在路網(wǎng)的基礎(chǔ)上生成時間依賴圖。圖中每條邊?vi,vj?的時間代價wi→j取路網(wǎng)的邊的權(quán)值。費(fèi)用函數(shù)fi→j(t)的定義域設(shè)為[0, 20 000]。將fi→j(t)的定義域隨機(jī)分成k 段，每一段上隨機(jī)生成一個[20,100]范圍內(nèi)的整數(shù)。k 分別取10 和20。

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

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

5.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

圖7 平均查詢時間對比

6 結(jié) 束 語

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