基于動態(tài)選擇啟發(fā)值的改進(jìn)TD-FTT算法

李佳佳，劉曉靜，劉向宇，夏秀峰，朱 睿

(沈陽航空航天大學(xué) 計算機(jī)學(xué)院，沈陽 110136)(*通信作者電子郵箱lijiajia@sau.edu.cn)

0 引言

目前，關(guān)于靜態(tài)路網(wǎng)K近鄰查詢研究已經(jīng)相當(dāng)成熟[1-3]，代表性算法有基于Voronoi圖的VN3(Voronoi-based Network Nearest Neighbor)算法[4]；利用歐氏距離與路網(wǎng)距離結(jié)合的IER(Incremental Euclidean Restriction)、INE(Incremental Network Expansion)[5]算法；通過范圍擴(kuò)展的“島”算法[6]等，但靜態(tài)路網(wǎng)以行駛距離作為邊的權(quán)值，在時間依賴路網(wǎng)中，邊的權(quán)值為行駛時間。如圖1所示，汽車1尋找最快到達(dá)的加油站，在圖1(a)發(fā)起查詢時刻為早上8:00，加油站1為返回結(jié)果，如果在早上6:00發(fā)起查詢?nèi)鐖D1(b)所示，加油站2則是離汽車1最近的加油站。由于發(fā)起查詢時刻不同，返回的結(jié)果集不同，因此靜態(tài)路網(wǎng)中求解K近鄰查詢的算法并不適用于時間依賴路網(wǎng)中，需要探索新的方法。

關(guān)于時間依賴路網(wǎng)K近鄰查詢存在一定研究[7-9]但相關(guān)研究還很不完善。Demiryurek等[10]提出TE(Time-Expanded)和TD-NE(Time-DependentKnearest neighbor with Network Expansion)算法，Cruz等[11]通過啟發(fā)函數(shù)和剪枝技術(shù)提出TD-NE-A*(Time Dependent Network Expansion with A*search)算法。TE算法將邊的權(quán)值離散化，無法保證權(quán)值在所有時刻取得實(shí)際值，因此造成誤差并不斷積累，最終可能導(dǎo)致結(jié)果集的錯誤；TD-NE算法查詢中盲目擴(kuò)展所有節(jié)點(diǎn)的鄰接點(diǎn)，計算代價大；TD-NE-A*算法剪枝策略的設(shè)定，會漏掉查找的興趣點(diǎn)，或者使到達(dá)興趣點(diǎn)的代價增大，并且由于時間依賴路網(wǎng)中權(quán)值在高峰期和低峰期相差較大，TD-NE-A*在高峰期用全天最小值作啟發(fā)值與實(shí)際值相差較大，啟發(fā)效果差，因此Komai等[12]提出TD-FTT(Time Dependent Fast Travel Time)算法，該算法將總體時間分為n個時段。預(yù)處理階段，取每個時段邊的最小值構(gòu)成靜態(tài)路網(wǎng)Gmin，在Gmin中計算所有節(jié)點(diǎn)的C近鄰。查詢發(fā)起時，確定查詢發(fā)起時刻位于的時段，利用該時段節(jié)點(diǎn)到達(dá)C近鄰的最小值作啟發(fā)值，因此啟發(fā)值更接近實(shí)際值，啟發(fā)更高效，有效解決了TD-NE算法[10]盲目擴(kuò)展帶來的計算量大和TD-NE-A*算法[11]啟發(fā)效果差的問題。

TD-FTT算法[12]在查詢階段，由于用查詢時刻所在時段的Gmin中節(jié)點(diǎn)到達(dá)最近鄰的時間作啟發(fā)值，因此必須保證查詢擴(kuò)展過程中節(jié)點(diǎn)到達(dá)下一節(jié)點(diǎn)的時間和到達(dá)K近鄰的時間與查詢發(fā)起時刻在同一時段，使實(shí)際應(yīng)用受限。例如，圖2中將T=60以20為間隔平均劃分為三個時段，v1在ts=15時發(fā)起查詢求最近鄰。當(dāng)擴(kuò)展第一個節(jié)點(diǎn)v2時，到達(dá)v2的時間為25，已經(jīng)跨過當(dāng)前時段[0,20]。在預(yù)處理階段，求解靜態(tài)路網(wǎng)Gmin中的C近鄰時C值和時段個數(shù)不易確定，且需計算每個時段Gmin中所有節(jié)點(diǎn)的C近鄰，計算量大，但在查詢K近鄰過程中，僅利用節(jié)點(diǎn)最近鄰的預(yù)處理信息，即C>1時，C近鄰的計算沒有意義，預(yù)處理信息利用率低。

圖1 時間依賴路網(wǎng)1近鄰查詢

本文針對TD-FTT算法在預(yù)處理階段存在的計算量大、信息利用率低和查詢階段不能跨時段查詢的問題，提出改進(jìn)的TD-FTT(Improved TD-FTT, ITD-FTT)算法。具體改進(jìn)策略如下：在預(yù)處理階段采用網(wǎng)絡(luò)泰森圖(Network Voronoi Diagram, NVD)在靜態(tài)路網(wǎng)Gmin中并行計算所有節(jié)點(diǎn)的最近鄰及到達(dá)最近鄰的時間，以減少計算量；在查詢階段根據(jù)查詢過程節(jié)點(diǎn)的到達(dá)時間動態(tài)選擇啟發(fā)值，不受用查詢時刻所在時段的最小值作啟發(fā)值所帶來的時段限制問題，使查詢不受限。

1 時間依賴路網(wǎng)模型

定義1 時間依賴路網(wǎng)。時間依賴路網(wǎng)GT由集合V，E和C組成，記為GT=(V,E,C)，其中V={v1,v2,…,vn}是頂點(diǎn)的有限集合，E={(vi,vj)|vi,vj∈V,i≠j}是連接V中兩個不同頂點(diǎn)(頂點(diǎn)對)的邊的有限集合，C={c(vi,vj)(t)|(vi,vj)∈E}，c(vi,vj)(t):[0,T]→R+，表示在t時刻從vi到vj所耗時間，其中t∈[0,T]，T為時間周期。如圖2(a)為一個時間依賴路網(wǎng)，圖2(b)～圖2(f)為各邊的權(quán)值函數(shù)。

圖2 時間依賴路網(wǎng)GT及某1 h內(nèi)各邊權(quán)值函數(shù)

時間依賴路網(wǎng)模型分為先進(jìn)先出(First-In First-Out, FIFO)模型和非先進(jìn)先出模型，即對于邊，如果邊權(quán)值函數(shù)c(vi,vj)(t)連續(xù)且處處可微，對任意t滿足c(vi,vj)(t)≤t1+c(vi,vj)(t+t1)；或者當(dāng)邊的時間函數(shù)c(vi,vj)(t)為離散值時，對任意s，t滿足下列不等式s+c(vi,vj)(s)≤t+c(vi,vj)(t)；具有該性質(zhì)的邊為FIFO邊。若路網(wǎng)中所有邊都為FIFO邊，則這樣的路網(wǎng)稱為FIFO路網(wǎng)模型，不具有這樣性質(zhì)的邊為非FIFO邊，若路網(wǎng)中存在一條非FIFO邊，則路網(wǎng)稱為非FIFO路網(wǎng)模型。時間依賴網(wǎng)絡(luò)中，需要滿足FIFO性質(zhì)；否則產(chǎn)生NP(Non-deterministic Polynomial)難問題[13]。目前所有關(guān)于時間依賴路網(wǎng)的研究都以滿足FIFO性質(zhì)為前提。本文所研究時間依賴路網(wǎng)同樣滿足FIFO性質(zhì)。

定義2 到達(dá)時間。對于時間依賴路網(wǎng)GT=(V,E,C)，在t時刻從vi通過邊(vi,vj)到達(dá)vj的到達(dá)時間定義為AT(vi,vj,t)=t+c(vi,vj)(t) modT。

定義4 時間依賴最快路徑。對于時間依賴路網(wǎng)GT=(V,E,C),存在u,v∈V，P(u,v)表示在t時刻出發(fā)，從u到v的所有路徑的集合，如果p∈P(u,v)且對于其他所有p′∈P(u,v)滿足TT(p,t)≤TT(p′,t)，則p為時間依賴最快路徑，定義為p=TDFP(u,v,t)。例如，在圖2，在t=5時發(fā)起查詢，v1到v5的時間依賴最短路徑TDFT(v1,v5,5)={v1,v2,v3,v5}；當(dāng)t=10時，v1到v5的時間依賴最短路徑TDFT(v1,v5,10)={v1,v2,v4,v5}。同一查詢，查詢時間不同，返回的最短路徑不同。

定義5 時間依賴的K近鄰查詢。對于時間依賴路網(wǎng)GT=(V,E,C)和興趣點(diǎn)集合POI?V，存在查詢點(diǎn)q，查詢發(fā)起時間t和目標(biāo)興趣點(diǎn)個數(shù)k(k>0)，時間依賴路網(wǎng)K近鄰查詢返回的結(jié)果集R={vr1,vr2,…,vrk}?POI且對任意v屬于集合POIR滿足，TDFP(q,vri,t)≤TDFP(q,v,t)。

2 TD-FTT算法

TD-FTT算法是為解決時間依賴路網(wǎng)中利用A*查詢K近鄰時啟發(fā)函數(shù)與實(shí)際值相差較大問題而提出的算法。

2.1 TD-FTT算法描述

TD-FTT算法分為預(yù)處理和查詢兩個階段。算法將整體時間tb根據(jù)需要分割成不同時段[0,t1]，(t1,t2]，…，(tb-1,tb]。在預(yù)處理階段，對每個時段(ti,ti+1]進(jìn)行如下操作：1)所有邊權(quán)值取當(dāng)前時段權(quán)值函數(shù)最小值minc(vi,vj)，構(gòu)成靜態(tài)路網(wǎng)Gmin；2)在靜態(tài)路網(wǎng)Gmin用INE算法[5]，查詢所有節(jié)點(diǎn)的C近鄰(C常值)和到達(dá)C近鄰的代價TT(ti-1,ti]，保存結(jié)果集，構(gòu)建索引。在查詢階段，查詢點(diǎn)q在時刻t發(fā)起查詢，首先判斷t所屬的時段(ti+1,ti]，計算q到鄰接點(diǎn)vi的通行時間c(q,vi,t)，利用預(yù)處理構(gòu)建的索引查找在時間段(ti+1,ti]中vi的C近鄰，取代價TT(ti-1,ti]最小的近鄰，即TT(ti-1,ti]=min(TT(ti-1,ti])，令L=c(q,vi,t)+TT(ti-1,tt]作為評價函數(shù)，選取L最小的節(jié)點(diǎn)vi繼續(xù)擴(kuò)展，找到K近鄰為止。

2.2 TD-FTT算法實(shí)例

以圖3和表1為例，說明TD-FTT算法執(zhí)行過程及TD-FTT存在的預(yù)處理階段信息利用率低和查詢階段受時段限制的問題。在3.3節(jié)中仍使用該圖和表為例，說明ITD-FTT算法執(zhí)行過程及在執(zhí)行過程中如何解決以上問題。

圖3和表1為時間依賴路網(wǎng)GT及相應(yīng)邊的權(quán)值函數(shù)，將整體時間T=20平均分割為兩個時間段[0,10]，(10,20]并令C=2。由邊權(quán)值函數(shù)，得到每個時段內(nèi)邊的最小值，構(gòu)成靜態(tài)路網(wǎng)GMIN[0,10]和GMIN(10,20]，在靜態(tài)路網(wǎng)中得到所有節(jié)點(diǎn)(除興趣點(diǎn)外)的兩個近鄰poi1、poi2及到達(dá)近鄰所需時間time1、time2，結(jié)果如表2所示。令查詢點(diǎn)q=a，查詢時間t=1，K=2。首先，判斷查詢時刻所在的時段，因為t∈[0,10]，因此選擇GMIN[0,10]的預(yù)處理信息；然后，遍歷查詢點(diǎn)a的鄰接點(diǎn){b,p2,c}并將a加入到隊列VP-label，加入VP-label中的節(jié)點(diǎn)不再擴(kuò)展；最后，分別計算各節(jié)點(diǎn)的AT、TT、L值，并加入到優(yōu)先隊列VT-label中，例如對于節(jié)點(diǎn)b，通過a到b的權(quán)值函數(shù)得TTb=c(a,b,1)=2.3，ATb=t+TTb=3.3。由表2可知，b的最近鄰為p1且time1=1，所以評價值L=TTb+time1=3.3。p2和c各值的計算類似b，最終得到的VT-label集合如下：

VT-label={(TTb=2.3,ATb=3.3,Lb=3.3),(TTp2=3.8,ATp2=4.8,Lp2=3.8),(TTc=2.4,ATc=3.4,Lc=4.4)}。選擇評價值L最小的節(jié)點(diǎn)繼續(xù)擴(kuò)展，因此在VT-label中對節(jié)點(diǎn)b進(jìn)行出隊列操作同時將b加入到隊列VP-label中。與節(jié)點(diǎn)b相連的節(jié)點(diǎn)為p1，操作如上，得到VP-label={a,b}，VT-label如下：{(TTc=2.4,ATc=3.4,Lc=4.4),(TTp2=3.8,ATp2=4.8,Lp2=3.8),(TTp1=6.6,ATp1=7.6,Lp1=6.6)}，其中節(jié)點(diǎn)p2的L值最小，因此選擇p2進(jìn)行遍歷。當(dāng)選擇的節(jié)點(diǎn)為興趣點(diǎn)且TT=L，則該興趣點(diǎn)為查找的目標(biāo)節(jié)點(diǎn)，因此將p2加入到結(jié)果集NN中。重復(fù)以上操作，得到結(jié)果集NN={p1,p2}，且到達(dá)目標(biāo)節(jié)點(diǎn)的時間在時段[0,10]區(qū)間。

當(dāng)查詢時間t=8時，t∈[0,10]，選擇GMIN[0,10]的預(yù)處理信息，當(dāng)擴(kuò)展a的鄰接點(diǎn){b,c,p2}時，到達(dá)節(jié)點(diǎn)的時間超出時段[0,10]，則到達(dá)目標(biāo)節(jié)點(diǎn)的時間必然在該時段外。

TD-FTT算法查詢點(diǎn)q必須在查詢時刻t所屬的時段t∈(ti-1,ti]內(nèi)到達(dá)K近鄰，當(dāng)查詢時間t與時段上限ti接近時，不能保證q到達(dá)K近鄰的時間與查詢發(fā)起時刻在同一時段。另外，在預(yù)處理階段，計算每個時段(ti,ti+1]內(nèi)所有節(jié)點(diǎn)在靜態(tài)路網(wǎng)中的C近鄰和到達(dá)C近鄰的時間來構(gòu)建索引。如上例在查詢階段，僅利用節(jié)點(diǎn)到達(dá)最近所需的時間min(TT(ti,ti+1])，因此當(dāng)C>1時，C近鄰的計算沒有意義。本文針對以上問題，預(yù)處理階段改進(jìn)索引結(jié)構(gòu)，在查詢階段動態(tài)選擇啟發(fā)值解決不能跨時段查詢的問題。

圖3 時間依賴路網(wǎng)GT

Tab. 1 Time function of each edge

表2 兩個區(qū)間的預(yù)處理信息

3 ITD-FTT算法

ITD-FTT在預(yù)處理階段和查詢階段對TD-FTT算法進(jìn)行改進(jìn)。由于NVD[14]單元具有在其范圍內(nèi)的節(jié)點(diǎn)，都以該NVD單元的中心點(diǎn)為最近鄰的性質(zhì)。因此，在預(yù)處理階段，首先計算各時段的靜態(tài)路網(wǎng)Gmin，然后利用NVD單元上述性質(zhì)，并行計算每個Gmin中所有節(jié)點(diǎn)vi∈V(i=1,2,…,n)的最近鄰及達(dá)最近鄰所需的時間TT(ti-1,ti]。查詢階段，根據(jù)節(jié)點(diǎn)vi到達(dá)時間AT(vi,vi+1,tk)所在的時段，動態(tài)選擇相應(yīng)時段的Gmin中節(jié)點(diǎn)到達(dá)最近鄰所需的時間TT(ti-1,ti]作為啟發(fā)值，解決了以查詢時刻所在時段對應(yīng)的Gmin中節(jié)點(diǎn)到達(dá)最近鄰值作啟發(fā)值帶來的時段限制問題。

3.1 預(yù)處理階段

介紹預(yù)處理階段之前，對NVD及相關(guān)性質(zhì)進(jìn)行描述：

性質(zhì)1 NVD單元范圍內(nèi)的所有節(jié)點(diǎn)，以NVD的中心點(diǎn)為最近鄰[14]。

在預(yù)處理階段，將整個周期T根據(jù)實(shí)際路網(wǎng)權(quán)值變化規(guī)律，分割為n個互不相交的時段，對每個時段進(jìn)行如下操作：

1)邊權(quán)值取時段內(nèi)時間函數(shù)的最小值，構(gòu)成靜態(tài)路網(wǎng)稱為Gmin，邊權(quán)值滿足E={|(vi,vj)|=minc(vi,vj)(ti-1,ti]}。

2)在時段內(nèi)，將所有興趣點(diǎn)作為NVD的中心點(diǎn)，構(gòu)建NVD單元，得到每個節(jié)點(diǎn)在時段內(nèi)的最近鄰及到達(dá)最近鄰的代價[11]。用Vgene(vi)表示vi的最近發(fā)起點(diǎn)集合，Vpred(vi)表示vi的前驅(qū)集合，dgene(vi)表示vi到當(dāng)前最近發(fā)起點(diǎn)的最短路徑，Vadja(vmin)表示vmin的鄰接點(diǎn)集合，dS(vmin,vk)表示vmin到vk的距離，利用NVD計算節(jié)點(diǎn)最近鄰如算法1所示。

算法1 NVD并行計算最近鄰算法。

輸入：靜態(tài)路網(wǎng)Gmin，興趣點(diǎn)集合POI。

輸出：NVD，得到節(jié)點(diǎn)最近鄰及到達(dá)最近鄰的時間。

1)

對所有中心點(diǎn)及非中心點(diǎn)進(jìn)行初始化

2)

for 對每個中心點(diǎn)pi∈POI及每個節(jié)點(diǎn)vido

3)

Vgene(pi)={pi}，Vpred(pi)={p0}，dgene(vi)=0

4)

將pi插入優(yōu)先隊列VT-label中

5)

Vgene(vi)={v∞}，Vpred(vi)={v0}，dgene(vi)=∞

6)

end for

7)

VP-label=?

8)

whileVT-label≠? do

9)

【英國《國際核工程》網(wǎng)站2018年10月2日報道】 俄羅斯核燃料產(chǎn)供集團(tuán)(TVEL)主管科技工作的副總裁亞歷山大·烏格爾耶莫夫2018年9月27日宣布，產(chǎn)供集團(tuán)計劃與俄羅斯原子能工業(yè)公司(Rosenergoatom)達(dá)成協(xié)議，近期在VVER-1000反應(yīng)堆中對耐事故燃料元件進(jìn)行輻照試驗。但沒有指明具體將對哪種耐事故燃料進(jìn)行輻照試驗。

得到VT-label中最小頂點(diǎn)vmin，將vmin加入到VP-label

10)

將vmin從優(yōu)先隊列VT-label中去掉

11)

forvk∈Vadja(vmin) do

12)

D=dgene(vmin)+dS(vmin,vk)

13)

ifdgene(vk)=∞ do

Vgene(vk)={vmin}，Vpred(vk)={vmin}，dgene(vk)=D

15)

將vk插入優(yōu)先隊列VT-label中

16)

end if

17)

ifdgene(vk)>D對vk更新 do

18)

Vgene(vk)={vmin}，Vpred(vk)={vmin}，dgene(vk)=D

19)

將vk插入優(yōu)先隊列VT-label中

20)

end if

21)

ifdgene(vk)=D對vk更新do

22)

Vgene(vk)=Vgene(vk)∪Vgene(vmin)

23)

Vpred(vk)=Vpred(vk)∪{vmin}，dgene(vk)=D

24)

將vk插入優(yōu)先隊列VT-label中

25)

end if

26)

end for

27)

end while

3.2 查詢階段

根據(jù)查詢過程中節(jié)點(diǎn)vi到達(dá)時間AT(vpi,vpi+1,ti)，動態(tài)選擇AT(vpi,vpi+1,ti)所在時段對應(yīng)的Gmin中節(jié)點(diǎn)vi的最近鄰和到達(dá)最近鄰的代價minc(vi,vj)作啟發(fā)值。當(dāng)查詢點(diǎn)q在t時刻發(fā)起查詢，假設(shè)t∈(ti,ti+1]。計算q到鄰接點(diǎn)vi的到達(dá)時間AT(q,vi,t)，確定AT(q,vi,t)所在的時段，假設(shè)AT(q,vi,t)∈(ti+1,ti+2]，利用時段(ti+1,ti+2]所構(gòu)建的Gmin在預(yù)處理階段得到vi的最近鄰及到達(dá)最近鄰的代價min(TT(ti+1,ti+2])，令L=c(q,vi,t)+min(TT(ti+1,tt+2])作為評價函數(shù)，選取L值最小的節(jié)點(diǎn)vj繼續(xù)擴(kuò)展vj的鄰接點(diǎn)，直到找到K近鄰，ITD-FTT查詢算法如算法2所示。

算法2 ITD-FTT查詢算法。

輸入：查找的近鄰個數(shù)K，發(fā)起查詢時間starttime，查詢點(diǎn)q。

輸出：含有K個最近鄰的結(jié)果集NN。

1)

for 查詢點(diǎn)q的鄰接點(diǎn)vkdo

2)

TT(vk)=c(q,vk,starttime)，

AT(vk)=TT(vk)+starttime

3)

匹配AT(vk)所在時段，根據(jù)所在時段對應(yīng)的Gmin中預(yù)計算得到的vk最近鄰及到達(dá)最近鄰所需的時間：MinTime=Match(AT(vk))

4)

計算L=TT(vk)+MinTime

5)

在優(yōu)先隊列TList中加入vk

6)

end for

7)

while 結(jié)果集列表NN長度小于Kdo

8)

從TList中得到L值最小的節(jié)點(diǎn)vmin

9)

forvmin的鄰接點(diǎn)vtdo

10)

TT(vi)=c(q,vi)，AT(vi)=TT(vi)+TT(vmin)

11)

匹配AT(vi)所在時段，根據(jù)所在時段，根據(jù)所在時段對應(yīng)的Gmin中預(yù)計算得到vi最近鄰及到達(dá)最近鄰所需的時間MinTime=Match(AT(vi))

12)

計算啟發(fā)值L=TT(vi)+MinTime

13)

如果vi在TList中，且L值小于原有L值，則更新vi，并將更新后的vi加入到TList

14)

IfTT(vi)=L且vi為興趣點(diǎn)

15)

將vi加入到結(jié)果集NN中

16)

end if

17)

end for

18)

end while

19)

returnNN

3.3 ITD-FTT算法實(shí)例說明

如圖3，當(dāng)t=8時，TD-FTT算法無法求解，下面利用ITD-FTT算法給出求解過程。令查詢點(diǎn)q=a，查詢時間t=8，K=2。遍歷查詢點(diǎn)a的鄰接點(diǎn){b,p2,c}并將a加入到隊列VP-label。分別計算各節(jié)點(diǎn)的AT、TT、L值，并將節(jié)點(diǎn)加入到優(yōu)先隊列VT-label中。例如對于節(jié)點(diǎn)b，通過a到b的權(quán)值函數(shù)得TTb=c(a,b,8)=4.4，ATb=t+TTb=12.4，根據(jù)節(jié)點(diǎn)的到達(dá)時間判斷節(jié)點(diǎn)所選擇的預(yù)處理信息。因為ATb∈(10,20]，因此選擇GMIN(10,20]，即表2的信息。由表2可知b的最近鄰為p1且time1=6.5，所以啟發(fā)值L=TTb+time1=10.9。得到的VT-label集合如下：{(TTb=4.4,ATb=12.4,Lb=10.9),(TTp2=9.4,ATp2=17.4,Lp2=9.4),(TTc=5.2,ATc=13.2,Lc=9.4)}，選擇啟發(fā)值L最小的節(jié)點(diǎn)繼續(xù)擴(kuò)展，因此在VT-label中對節(jié)點(diǎn)c進(jìn)行出隊列操作同時在VP-label中加入c。與節(jié)點(diǎn)c相連的節(jié)點(diǎn)為p1,p3，操作如上，得到VP-label={a,c}，VT-label集合如下：{(TTp2=9.4,ATp2=17.4,Lp2=9.4),(TTp3=9.84,ATp3=17.84,Lp3=9.84),(TTb=4.4,ATb=12.4,Lb=10.9),(TTp1=12.8,ATp1=20.8,Lp1=12.8)}，接下來遍歷L值最小的節(jié)點(diǎn)p2，因為p2為興趣點(diǎn)且TT=L，該興趣點(diǎn)為查找的目標(biāo)節(jié)點(diǎn)。p2鄰接點(diǎn)為p3，此時TTp3=14.7>9.84，因此，不更新p3的值。得到VP-label={a,p2,c}，VT-label如下：{(TTp3=9.84,ATp3=17.84,Lp3=9.84),(TTb=4.4,ATb=12.4,Lb=10.9),(TTp1=12.8,ATp1=20.8,Lp1=12.8)}，遍歷節(jié)點(diǎn)p3，因為p3為興趣點(diǎn)且TT=L，則該興趣點(diǎn)為查找的目標(biāo)節(jié)點(diǎn)，得到結(jié)果集NN={p3,p2}。在以上查詢過程中啟發(fā)值不受限于查詢時刻所在的時段。

4 實(shí)驗

4.1 實(shí)驗參數(shù)

用德國奧爾登堡的路網(wǎng)圖進(jìn)行仿真實(shí)驗，地圖含節(jié)點(diǎn)6 105個，邊7 035條。電腦配置處理器Inter Core i5- 3470 CPU @3.20 GHz，內(nèi)存4 GB。根據(jù)實(shí)際路網(wǎng)變化規(guī)律。本文將全天分為5個時段，[22:00,7:00)，[7:00,9:00)，[9:00,17:00)，[17:00,19:00)，[19:00,22:00);每隔5 min對邊賦權(quán)值，得到邊的288個權(quán)值，根據(jù)邊的權(quán)值擬合為分段線性函數(shù)。本文首先對TD-FTT和ITD-FTT算法在預(yù)處理階段計算量進(jìn)行對比實(shí)驗。在查詢階段，將ITD-FTT算法同TD-INE(Time Dependent Incremental Network Expansion)算法[10]，和將全天最小值作為啟發(fā)值的TD-A(Time Dependent A star)算法進(jìn)行對比驗證其效率。

4.2 實(shí)驗結(jié)果

4.2.1 預(yù)處理階段實(shí)驗

由于改進(jìn)的算法只需求時段內(nèi)靜態(tài)路網(wǎng)中節(jié)點(diǎn)的最近鄰，為與TD-FTT算發(fā)預(yù)處理階段進(jìn)行比較，因此令C=1，即假設(shè)TD-FTT算法在預(yù)處理過程中僅求解節(jié)點(diǎn)的最近鄰。TD-FTT算法計算所有時段的平均預(yù)處理時間為3 052 ms，在ITD-FTT算法中利用NVD計算所有時段的最近鄰所需時間為912 ms，時間減少了70.12%。因為，利用NVD可以并行計算所有節(jié)點(diǎn)的最近鄰，因此，計算時間會大幅減少，并且，TD-FTT算法在計算過程中C>1，計算時間比C=1時增加，因此預(yù)處理階段的改進(jìn)使計算量大幅減少，改進(jìn)效果明顯。

4.2.2 查詢階段實(shí)驗

對于查詢處理階段，實(shí)驗對比不同算法的K值和興趣點(diǎn)密度(Point Of Interest, POI)密度對查詢響應(yīng)時間和查詢遍歷節(jié)點(diǎn)的影響。令K的默認(rèn)值為20，POI密度默認(rèn)值設(shè)為0.1。

令K∈{1,5,10,15,20,25,30}，對不同K值，隨機(jī)進(jìn)行30次查詢。圖4(a)比較了3種算法隨K值增加查詢響應(yīng)時間的平均值對比曲線。圖4(b)顯示隨K值增加查詢遍歷節(jié)點(diǎn)數(shù)的平均值對比曲線?？梢钥闯?，響應(yīng)時間和遍歷節(jié)點(diǎn)數(shù)隨著K值的增加而增加，這是由于查詢目標(biāo)節(jié)點(diǎn)增加，需要擴(kuò)展更多節(jié)點(diǎn)得到目標(biāo)節(jié)點(diǎn)，而擴(kuò)展節(jié)點(diǎn)的增加同時帶來響應(yīng)時間的增加。

ITD-FTT和TD-A算法比TD-INE算法平均遍歷節(jié)點(diǎn)個數(shù)分別減少46.52%、35.73%，因為ITD-FTT和TD-A算法為啟發(fā)式搜索算法，因此遍歷節(jié)點(diǎn)個數(shù)比盲目擴(kuò)展的TD-INE算法少。ITD-FTT比TD-A算法遍歷節(jié)點(diǎn)個數(shù)減少了約16.63%，因為在同為啟發(fā)搜索算法的前提下，ITD-FTT的啟發(fā)值比TD-A更接近實(shí)際值，因此遍歷節(jié)點(diǎn)個數(shù)更少，算法更高效。

ITD-FTT和TD-A算法的平均響應(yīng)時間比TD-INE分別減少47.46%和35.73%，ITD-FTT比TD-A的響應(yīng)時間減少約18.24%。因為響應(yīng)時間的不同主要由遍歷節(jié)點(diǎn)個數(shù)不同引起，因此響應(yīng)時間隨K值的變化趨勢與遍歷節(jié)點(diǎn)隨K值的變化趨勢相同。當(dāng)K=1時，遍歷的節(jié)點(diǎn)太少，所有算法的響應(yīng)時間差距較小。

圖4 K值對查詢的影響

將POI的密度設(shè)置為5%、10%、15%、20%，在不同密度下，令K=20隨機(jī)進(jìn)行30次查詢。圖5(a)表示隨POI密度的增加，查詢響應(yīng)時間的變化趨勢。由圖5(a)可知，隨著密度的增加，3種算法的響應(yīng)時間均在減少，但I(xiàn)TD-FTT算法的響應(yīng)時間最少。圖5(b)表示，隨POI密度增加，查詢遍歷節(jié)點(diǎn)的變化規(guī)律。在圖5(b)中，遍歷節(jié)點(diǎn)的個數(shù)也隨著密度的增大而減少，并且ITD-FTT算法所需遍歷的節(jié)點(diǎn)數(shù)最少。

當(dāng)查詢目標(biāo)節(jié)點(diǎn)個數(shù)K一定時，POI的密度增大，節(jié)點(diǎn)作為目標(biāo)節(jié)點(diǎn)的概率增大，因此，隨POI密度增大，遍歷節(jié)點(diǎn)個數(shù)減少。又因為ITD-FTT和TD-A算法為啟發(fā)式搜索算法，因此比盲目擴(kuò)展的TD-INE算法遍歷節(jié)點(diǎn)個數(shù)少，ITD-FTT、TD-A算法在同為啟發(fā)搜索算法的前提下，ITD-FTT的啟發(fā)值比TD-A更接近實(shí)際值，因此遍歷節(jié)點(diǎn)個數(shù)減少，算法更高效。在3種算法中，ITD-FTT算法遍歷的節(jié)點(diǎn)個數(shù)最少。由于響應(yīng)時間由遍歷節(jié)點(diǎn)個數(shù)決定且成同樣趨勢，因此，由遍歷節(jié)點(diǎn)個數(shù)變化規(guī)律可知，響應(yīng)時間也同樣隨POI密度增加而減少。

由以上分析結(jié)果可知，本文所提的ITD-FTT算法在響應(yīng)時間和遍歷節(jié)點(diǎn)個數(shù)上相比其他兩種算法均有優(yōu)勢，并且在密度相同的情況下，響應(yīng)時間和遍歷節(jié)點(diǎn)個數(shù)的值均為最小。

圖5 POI密度對查詢的影響

5 結(jié)語

與靜態(tài)路網(wǎng)相比，時間依賴路網(wǎng)在位置廣告、智能導(dǎo)航、緊急救援更具有現(xiàn)實(shí)意義。本文在不改變TD-FTT算法效率的前提下，在預(yù)處理階段利用NVD并行計算節(jié)點(diǎn)的最近鄰，減少預(yù)計算的計算量；在查詢階段根據(jù)節(jié)點(diǎn)到達(dá)時間所在的時段，動態(tài)選擇啟發(fā)值，避免利用查詢時刻所在時段的最小值作啟發(fā)值帶來的不能跨時段查詢的問題。通過仿真實(shí)驗表明，ITD-FTT算法在預(yù)處理階段計算量大幅度減少且查詢階段在響應(yīng)時間和遍歷節(jié)點(diǎn)個數(shù)上優(yōu)于TD-INE算法和TD-A算法。將該方法利用在時間依賴路網(wǎng)的連續(xù)K近鄰查詢算法中，可作為進(jìn)一步研究工作。

References)

[1] 廖巍,吳曉平,胡衛(wèi),等.基于最短路徑的道路網(wǎng)絡(luò)K近鄰查詢處理[J].計算機(jī)科學(xué),2010,37(11):180-183.(LIAO W, WU X P, HU W, et al. Processing ofKnearest neighbor queries based on shortest path in road networks [J]. Computer Science, 2010, 37(11): 180-183.)

[2] 劉德高,李曉宇.基于路網(wǎng)的連續(xù)K近鄰查詢算法[J].計算機(jī)應(yīng)用,2013,33(7):1964-1968.(LIU D G, LI X Y. ContinuousKnearest neighbor query algorithm based on road network [J]. Journal of Computer Applications, 2013, 33(7): 1964-1968.)

[3] 趙亮,陳犖,景寧,等.道路網(wǎng)中的移動對象連續(xù)K近鄰查詢[J].計算機(jī)學(xué)報,2010,33(8):1396-1404.(ZHAO L, CHEN L, JING N, et al. ContinuousKneighbor queriers of moving objects in road networks [J]. Chinese Journal of Computers, 2010, 33(8): 1396-1404.)

[4] KOLAHDOUZAN M, SHAHABI C. Voronoi-basedknearest neighbor search for spatial network databases [C]// VLDB 2004: Proceedings of the Thirtieth International Conference on Very Large Data Bases. San Francisco, CA: Morgan Kaufmann, 2004: 840-851.

[5] PAPADIAS D, ZHANG J, MAMOULIS N, et al. Query processing in spatial network databases [C]// VLDB 2003: Proceedings of the 29th International Conference on Very Large Data Bases. San Francisco, CA: Morgan Kaufmann, 2003: 802-813.

[6] HUANG X, JENSEN CS,ALTENIS S. The islands approach to nearest neighbor querying in spatial networks [C]// SSTD 2005: Proceedings of the 2005 International Symposium on Spatial and Temporal Databases. Berlin: Springer, 2005: 73-90

[7] ZHANG D, CHOW C-Y, LI Q, et al. SMashQ: spatial mashup framework fork-NN queries in time-dependent road networks [J]. Distributed and Parallel Databases, 2013, 31(2): 259-287.

[8] COSTA C F, NASCIMENTO M A, DEMACDO J A F, et al. A*-based solutions forkNN queries with operating time constraints in time-dependent road networks [C]// MDM 2014: Proceedings of the 2014 IEEE 15th International Conference on Mobile Data Management. Piscataway, NJ: IEEE, 2014: 23-32.

[9] ABEYWICKRAMA T, CHEEMA M A. Efficient landmark-based candidate generation forkNN queries on road networks [C]// DASFAA 2017: Proceedings of the 22nd Internation Conference on Database Systems for Advanced Applications. Berlin: Springer, 2017: 425-440.

[10] DEMIRYUREK U, BANAEI-KASHANI F, SHAHABI C. Efficientk-nearest neighbor search in time-dependent spatial networks [C]// DEXA 2010: Proceedings of the 2010 International Conference on Database and Expert Systems Applications. Berlin: Springer, 2010: 432-449.

[11] CRUZ L A, NASCIMENTO M A, MACEDO J A F.k-nearest neighbors queries in time-dependent road networks [J]. Journal of Information & Data Management, 2012, 3(3): 211-216.

[12] KOMAI Y, NGUYEN D H, HARA T, et al.kNN search utilizing index of the minimum road travel time in time-dependent road networks [J]. Information Sciences, 2014, 255(1): 135-154.

[13] 譚國真,高文.時間依賴的網(wǎng)絡(luò)中最小時間路徑算法[J].計算機(jī)學(xué)報,2002,25(2):165-172.(TAN G Z, GAO W. Shortest path algorithm in time-dependent networks [J]. Chinese Journal of Computers, 2002, 25(2): 165-172.)

[14] OKABE A, SATOH T, FURUTA T, et al. Generalized network Voronoi diagrams: concepts, computational methods, and applications [J]. International Journal of Geographical Information Science, 2008, 22(9): 965-994.

This work is partially supported by National Natural Science Foundation of China (61502317).

LIJiajia, born in 1987, Ph. D., lecturer. Her research interests include temporal data management, intelligent transportation.

LIUXiaojing, born in 1991, M. S. candidate. Her research interests include temporal data management.

LIUXiangyu, born in 1981, Ph. D., lecturer. His research interests include social network, privacy preserving.

XIAXiufeng, born in 1964, Ph. D., professor. His research interests include data warehouse, NoSQL database.

ZHURui, born in 1982, Ph. D., lecturer. His research interests include data stream management, spatiotemporal crowdsourcing.