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

(沈陽(yáng)航空航天大學(xué) 計(jì)算機(jī)學(xué)院，沈陽(yáng) 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]算法；通過(guò)范圍擴(kuò)展的“島”算法[6]等，但靜態(tài)路網(wǎng)以行駛距離作為邊的權(quán)值，在時(shí)間依賴(lài)路網(wǎng)中，邊的權(quán)值為行駛時(shí)間。如圖1所示，汽車(chē)1尋找最快到達(dá)的加油站，在圖1(a)發(fā)起查詢時(shí)刻為早上8:00，加油站1為返回結(jié)果，如果在早上6:00發(fā)起查詢?nèi)鐖D1(b)所示，加油站2則是離汽車(chē)1最近的加油站。由于發(fā)起查詢時(shí)刻不同，返回的結(jié)果集不同，因此靜態(tài)路網(wǎng)中求解K近鄰查詢的算法并不適用于時(shí)間依賴(lài)路網(wǎng)中，需要探索新的方法。

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

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

圖1 時(shí)間依賴(lài)路網(wǎng)1近鄰查詢

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

1 時(shí)間依賴(lài)路網(wǎng)模型

定義1 時(shí)間依賴(lài)路網(wǎng)。時(shí)間依賴(lài)路網(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中兩個(gè)不同頂點(diǎn)(頂點(diǎn)對(duì))的邊的有限集合，C={c(vi,vj)(t)|(vi,vj)∈E}，c(vi,vj)(t):[0,T]→R+，表示在t時(shí)刻從vi到vj所耗時(shí)間，其中t∈[0,T]，T為時(shí)間周期。如圖2(a)為一個(gè)時(shí)間依賴(lài)路網(wǎng)，圖2(b)～圖2(f)為各邊的權(quán)值函數(shù)。

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

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

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

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

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

2 TD-FTT算法

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

2.1 TD-FTT算法描述

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

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

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

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

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

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

圖3 時(shí)間依賴(lài)路網(wǎng)GT

Tab. 1 Time function of each edge

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

3 ITD-FTT算法

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

3.1 預(yù)處理階段

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

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

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

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

2)在時(shí)段內(nèi)，將所有興趣點(diǎn)作為NVD的中心點(diǎn)，構(gòu)建NVD單元，得到每個(gè)節(jié)點(diǎn)在時(shí)段內(nèi)的最近鄰及到達(dá)最近鄰的代價(jià)[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計(jì)算節(jié)點(diǎn)最近鄰如算法1所示。

算法1 NVD并行計(jì)算最近鄰算法。

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

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

1)

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

2)

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

3)

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

4)

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

5)

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

6)

end for

7)

VP-label=?

8)

whileVT-label≠? do

9)

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

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

10)

將vmin從優(yōu)先隊(duì)列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)先隊(duì)列VT-label中

16)

end if

17)

ifdgene(vk)>D對(duì)vk更新 do

18)

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

19)

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

20)

end if

21)

ifdgene(vk)=D對(duì)vk更新do

22)

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

23)

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

24)

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

25)

end if

26)

end for

27)

end while

3.2 查詢階段

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

算法2 ITD-FTT查詢算法。

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

輸出：含有K個(gè)最近鄰的結(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)所在時(shí)段，根據(jù)所在時(shí)段對(duì)應(yīng)的Gmin中預(yù)計(jì)算得到的vk最近鄰及到達(dá)最近鄰所需的時(shí)間：MinTime=Match(AT(vk))

4)

計(jì)算L=TT(vk)+MinTime

5)

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

6)

end for

7)

while 結(jié)果集列表NN長(zhǎng)度小于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)所在時(shí)段，根據(jù)所在時(shí)段，根據(jù)所在時(shí)段對(duì)應(yīng)的Gmin中預(yù)計(jì)算得到vi最近鄰及到達(dá)最近鄰所需的時(shí)間MinTime=Match(AT(vi))

12)

計(jì)算啟發(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í)例說(shuō)明

如圖3，當(dāng)t=8時(shí)，TD-FTT算法無(wú)法求解，下面利用ITD-FTT算法給出求解過(guò)程。令查詢點(diǎn)q=a，查詢時(shí)間t=8，K=2。遍歷查詢點(diǎn)a的鄰接點(diǎn){b,p2,c}并將a加入到隊(duì)列VP-label。分別計(jì)算各節(jié)點(diǎn)的AT、TT、L值，并將節(jié)點(diǎn)加入到優(yōu)先隊(duì)列VT-label中。例如對(duì)于節(jié)點(diǎn)b，通過(guò)a到b的權(quán)值函數(shù)得TTb=c(a,b,8)=4.4，ATb=t+TTb=12.4，根據(jù)節(jié)點(diǎn)的到達(dá)時(shí)間判斷節(jié)點(diǎn)所選擇的預(yù)處理信息。因?yàn)锳Tb∈(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中對(duì)節(jié)點(diǎn)c進(jìn)行出隊(duì)列操作同時(shí)在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ái)遍歷L值最小的節(jié)點(diǎn)p2，因?yàn)閜2為興趣點(diǎn)且TT=L，該興趣點(diǎn)為查找的目標(biāo)節(jié)點(diǎn)。p2鄰接點(diǎn)為p3，此時(shí)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，因?yàn)閜3為興趣點(diǎn)且TT=L，則該興趣點(diǎn)為查找的目標(biāo)節(jié)點(diǎn)，得到結(jié)果集NN={p3,p2}。在以上查詢過(guò)程中啟發(fā)值不受限于查詢時(shí)刻所在的時(shí)段。

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

4.1 實(shí)驗(yàn)參數(shù)

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

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

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

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

4.2.2 查詢階段實(shí)驗(yàn)

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

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

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

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

圖4 K值對(duì)查詢的影響

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

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

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

圖5 POI密度對(duì)查詢的影響

5 結(jié)語(yǔ)

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

References)

[1] 廖巍,吳曉平,胡衛(wèi),等.基于最短路徑的道路網(wǎng)絡(luò)K近鄰查詢處理[J].計(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ì)算機(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)中的移動(dòng)對(duì)象連續(xù)K近鄰查詢[J].計(jì)算機(jī)學(xué)報(bào),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] 譚國(guó)真,高文.時(shí)間依賴(lài)的網(wǎng)絡(luò)中最小時(shí)間路徑算法[J].計(jì)算機(jī)學(xué)報(bào),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.