反向時間依賴路網(wǎng)上移動對象的啟發(fā)式k近鄰查詢算法

宋力翔，秦小麟

(南京航空航天大學 計算機技術(shù)與科學學院，南京 210016)

1 引 言

如今，隨著移動設(shè)備的發(fā)展，在我們的日常生活中越來越普及.由于現(xiàn)有的移動設(shè)備通常都裝有全球定位系統(tǒng)芯片，用戶可以很容易地獲得自己的位置.隨著各行各業(yè)對基于位置的服務(wù)(Location Based Services，LBS)需求不斷擴大，對于基于位置的服務(wù)研究也不斷深入.在我們的日常生活中，道路網(wǎng)上已有很多LBS應(yīng)用.例如，導航系統(tǒng)、旅游應(yīng)用程序.

在不同類型的路網(wǎng)中進行k近鄰查詢需要不同的算法.因此對于每一種路網(wǎng)模型，都會有一些合適的算法來進行k近鄰查詢.如果路網(wǎng)模型中的邊權(quán)值是靜態(tài)的且確定性的，那么這個路網(wǎng)模型就是非時間依賴路網(wǎng)，也稱為靜態(tài)路網(wǎng).靜態(tài)路網(wǎng)下k近鄰查詢的相關(guān)研究已十分成熟，文獻[1-4]為靜態(tài)網(wǎng)絡(luò)提出了許多有效的算法.這些算法均為標準的k近鄰查詢算法.

而隨著城市道路網(wǎng)絡(luò)上私家車的數(shù)量不斷增加，越來越多的路網(wǎng)卡口開始發(fā)生交通擁堵.這就會導致許多社會問題的產(chǎn)生，例如城市交通污染和居民出行時間的變化.為了能夠幫助人們能夠更有效地應(yīng)對外界情況的改變，例如交通狀況，天氣因素，突發(fā)事件就需要時間依賴路網(wǎng)模型.其中，道路邊權(quán)值跟隨時間而產(chǎn)生變化.如圖1所示，一位到南京來旅游的游客，他/她對于離他/她最近的旅游景點非常感興趣，例如最負盛名的幾個景點，紫金山、紫峰大廈等.他/她提出一個查詢，詢問此時此刻哪條路線通往該景點最快；答案取決于出發(fā)時間.例如，10：00時，去紫金山需要40分鐘(見圖1(a)).這是最近的景點.盡管如此，如果他/她在22：00查詢相同的問題，在相同的空間點，最近的景點是紫峰大廈(見圖1(b)).在靜態(tài)路網(wǎng)中，無論何時進行k近鄰查詢，返回的結(jié)果都是相同的.而時間依賴路網(wǎng)中的k近鄰查詢則不同，需要考慮外界因素對路網(wǎng)邊權(quán)值的影響，更符合實際情況.

圖1 k近鄰查詢樣例Fig.1 Example of kNN query

由于實際路段上的行駛時間由時間決定，也就是說，其取決于路段上當前時間的交通車流量，所以實際路網(wǎng)是時間依賴路網(wǎng)而非靜態(tài)路網(wǎng).而在時間依賴路網(wǎng)的k近鄰查詢，即TD-kNN問題，同時是查詢距離查詢點最短路徑行駛時間的k個POI.但目前TD-kNN的研究大多針對路網(wǎng)靜態(tài)對象[5]，未能有效處理多移動對象服務(wù).例如，乘客查詢能最快到達的快車，食客尋求能最快送到的外賣，病人尋求能最快趕到的救護車等.同時查詢算法存在許多局限和不足，主要依賴在線擴展，查詢時間代價大，僅使用樸素啟發(fā)函數(shù)，近鄰擴展還可以進行多次過濾，造成了過多冗余計算，使得算法查詢效率受到了一定影響.

基于上述問題，提出新的時間依賴路網(wǎng)上k近鄰查詢用以解決實際生活中查詢k個POI(如快車、救護車、外賣騎手)能在最短時間內(nèi)到達查詢點(如乘客、病人、食客)的問題，并對此構(gòu)建了一個基于標記點的最短路徑樹結(jié)構(gòu)，運用三角形不等式和啟發(fā)式函數(shù)，能夠有效處理時間依賴路網(wǎng)上移動對象的k近鄰查詢.本文主要貢獻如下：

1)針對以往研究假設(shè)時間依賴路網(wǎng)下移動對象查詢的不足，提出反向時間依賴路網(wǎng)圖上移動對象的k近鄰查詢，使得最終結(jié)果更加接近真實值.

2)提出一種基于標記點的時間依賴路網(wǎng)下最短路徑樹.并利用三角形不等式和啟發(fā)式函數(shù)，極大地提升了算法的查詢效率.

3)采用德國奧登堡路網(wǎng)數(shù)據(jù)集與現(xiàn)有算法進行了對比實驗，進一步驗證了算法的有效性，實驗結(jié)果表明，TDSPT-kNN算法相較于現(xiàn)有算法更為高效.

本文其余部分結(jié)構(gòu)如下：在第2節(jié)中，我們對相關(guān)工作進行了簡要的討論.接下來我們正式定義了反向時間依賴路網(wǎng)上移動對象的k近鄰查詢.第4節(jié)基于上述概念提出了時間依賴路網(wǎng)下的基于標記點的最短路徑樹構(gòu)建及更新，并基于此提出了反向時間依賴路網(wǎng)上移動對象的k近鄰查詢算法TDSPT-kNN.在第5節(jié)，我們給出了實驗評估和結(jié)果.最后對本文工作進行了總結(jié)并對下一步工作提出了思考.

2 相關(guān)工作

k近鄰查詢作為基于位置服務(wù)中重要支持性技術(shù)之一，已經(jīng)有眾多學者對其深入研究.Knuth提出了著名的郵局問題，NN查詢就來源于此.k近鄰查詢則是NN查詢的一般形式化.

傳統(tǒng)路網(wǎng)上關(guān)于k近鄰查詢的研究已經(jīng)相當成熟[6，7].Papadias[6]等提出的INE算法基于傳統(tǒng)路網(wǎng)上的Dijkstra算法，從查詢位置開始擴展近鄰節(jié)點，直到找到k個近鄰結(jié)果.IER[6]算法利用空間剪枝技術(shù)(例如，以歐幾里德距離為邊界剪支)來改進INE算法，剪枝無用擴展.IER和INE都是“盲目”算法，因為它們既不能捕獲從對象到查詢位置的全局距離，也不能有效地修剪不必要的對象.Lee[7]提出的ROAD算法采用層次結(jié)構(gòu)擴展了Dijkstra算法.算法以遞歸形式將路網(wǎng)網(wǎng)劃分為子網(wǎng)絡(luò)，預(yù)先計算子網(wǎng)絡(luò)中虛擬邊的最短路徑距離，并以分層方式組織它們.通過使用類似Dijkstra的網(wǎng)絡(luò)擴展，道路可以跳過不包含對象的子網(wǎng)絡(luò).但是它不能剪除對象廣泛分散的子網(wǎng)絡(luò).例如，如果對象分布廣泛(例如加油站)，道路將退化為Dijkstra算法，并且必須穿越整個網(wǎng)絡(luò).因此，在大型路網(wǎng)上性能很差.

Cooke和Halsey[8]認為靜態(tài)路網(wǎng)下的SP問題缺乏現(xiàn)實意義，率先提出節(jié)點間通行時間可變的路網(wǎng).George和Shekhar[9]提出了時間聚合圖概念，將每條邊上在一時刻的旅行時間聚合成一個時間序列.上述研究均假設(shè)邊權(quán)函數(shù)定義在有限離散時間序列t∈t0，t1，…，tn上，但是離散時間算法有許多缺點.首先，由于對于每個指定時間步長中都要復(fù)制整個網(wǎng)絡(luò)，因此對于復(fù)雜網(wǎng)絡(luò)來說，使用離散時間定義的時間依賴路網(wǎng)需要大量的存儲空間.其次，使用離散時間定義方法只能提供近似結(jié)果，而非精確結(jié)果，因為計算是在離散時間進行的，而不是在連續(xù)時間進行的.Dreyfus[10]提出了在時間依賴路網(wǎng)下Dijkstra算法的變體，Halpren[11]研究發(fā)現(xiàn)時間依賴路網(wǎng)的時間間隔會導致路網(wǎng)的不一致性.Ding[12]等人針對TDSP問題提出了基于Dijkstra的算法，該算法通過掃描時間步長來分離路徑選擇和時間細化從而優(yōu)化時間復(fù)雜度，時間步長大小取決于到達時間函數(shù)值.Kanoulas[13]等人引入了allFP算法，該算法不按標量值對優(yōu)先級隊列進行排序，而是維護所有要擴展的路徑的優(yōu)先級隊列.但該算法枚舉從源節(jié)點到目標節(jié)點中的所有路徑，所以在最壞的情況下，該算法會產(chǎn)生指數(shù)運行時間.Demiryurek[14]等估計通行時間的上下屆運用A*算法來擴展路網(wǎng)節(jié)點，但這會使得結(jié)果是依據(jù)估計值，和實際值有一定偏差.

綜上所述，目前傳統(tǒng)靜態(tài)路網(wǎng)的近鄰查詢算法已經(jīng)有相當多的研究，而時間依賴路網(wǎng)下的近鄰查詢算法仍存在不足.已有的時間依賴路網(wǎng)下的k近鄰查詢技術(shù)大都是依據(jù)出行時間的估計值，和實際時間仍有較大偏差，同時搜索時擴展節(jié)點慢效率不高.為解決上述問題，提出反向時間依賴路網(wǎng)上移動對象的k近鄰查詢問題，并構(gòu)建了一個基于標記點的最短路徑樹結(jié)構(gòu)，運用到三角形不等式和啟發(fā)式函數(shù)，提出了一種高效的時間依賴路網(wǎng)下的移動對象k近鄰查詢算法TDSPT-kNN.

3 基礎(chǔ)定義

下面給出對于時間依賴路網(wǎng)模型定義和性質(zhì)及新的k近鄰查詢問題.

定義1.(時間依賴有向圖[15])將時間依賴路網(wǎng)建模為有向圖GT=(V，E，W)，其中每個vi∈V是路網(wǎng)中頂點集，evivj∈E是vi到vj的有向邊，wvivj∈W是與邊evivj相關(guān)聯(lián)的時間依賴路網(wǎng)邊權(quán)值函數(shù)，wvivj(t)：[0，T]→R+，T是W中函數(shù)的域，表示邊evivj在t時刻的通行時間為wvivj(t).

與現(xiàn)有的時間依賴路網(wǎng)算法類似，我們假設(shè)時間依賴有向圖滿足FIFO性質(zhì)，即用戶正好在時間t出發(fā)且在通過路徑時不允許等待，如果不滿足則查詢問題將演變成NP-hard問題[16].

定義2.(分段線性權(quán)值函數(shù)[15])對于給定的一條有向邊e，在特定的時間段內(nèi)與一組權(quán)重(行程時間)相關(guān)聯(lián)，如S={(t1，w1)，…，(tk，wk)}其中，t1=ts&tk=te，的插值點集記為SI.有向邊e的分段線性權(quán)值函數(shù)記為w，權(quán)值函數(shù)w是點集SI中的線性插值.在時刻t出發(fā)，由vi移動到vj所需要花費的時間，即wvivj(t)在時刻t得出的權(quán)值.

本文設(shè)定的時間依賴路網(wǎng)圖中邊不都是雙向?qū)Φ鹊?即邊evivj的存在并不意味著邊evjvi的存在.此外，存在相反邊evivj和evjvi，使得wvivj(t)≠wvjvi(t)，否則研究的問題將變成傳統(tǒng)意義上的TD-k近鄰問題.如圖2所示，這是一個時間依賴局部路網(wǎng)圖.對邊ev0v1和ev1v0以及ev0v2和ev2v0具有相同的成本.然而，ev0v3和ev3v0雖然相反，但有不同的成本.

圖2 時間依賴局部路網(wǎng)Fig.2 Time-dependent local road network

圖2局部路網(wǎng)中的時間依賴邊權(quán)如表1所示.每個邊都與一組(時間，權(quán)重)對相關(guān)聯(lián).

表1 邊權(quán)值Table 1 Edge weights

定義3.(到達時間[17])對于時間依賴路網(wǎng)圖GT=(V，E，W)，t時刻從vi點出發(fā)，經(jīng)過邊evivj到達vj點的時間記為ATvivj(t)=t+wvjvi(t)modT.

定義4.(路徑行駛時間)時間依賴路網(wǎng)圖GT=(V，E，W)經(jīng)過的路徑記為序列ρvsve.從節(jié)點vs出發(fā)到達ve的所有路徑集記為δvsve.設(shè)一路徑ρv1vi，ρv1vi-1為ρv1vi去除終節(jié)點vi后的子路徑，在t時刻發(fā)起查詢通過路徑ρv1vi所需時間定義為：

TT(ρv1vi，t)=TT(ρv1vi-1，t)+wvi-1vi(t+TT(ρv1vi-1，t))

(1)

其中TT(ρv1v1，t)=0.如圖2所示，路徑p={(v0，v2，v3)} 在t=15 時的路徑行駛時間TT(ρv0v3，t)=20+20=40.

定義5.(最短路徑時間函數(shù)[15])在時刻t從節(jié)點vs出發(fā)到達ve的最短路徑時間函數(shù)記為τvsve(t)，是所有可能路徑集δvsve的最小時間.

τvsve(t)=minρvsve{TT(ρvsve，t)|ρvsve∈δvsve}

(2)

定義6.(興趣點(POI))設(shè)P={p1，…，pn}為興趣點(POI)pi=(pid，loc，mf)，1≤i≤n.其中，pid是POI的標識，loc是p在地理空間(即緯度，經(jīng)度)中的位置，mf：RxR→V是給定的映射函數(shù)，它將p的地理位置與一個頂點v∈V相聯(lián).

為了將所提出的反向時間依賴路網(wǎng)上移動對象k近鄰查詢問題形式化，下面對查詢點及查詢問題進行定義.

定義7.(查詢點)查詢點qp∈V是圖TDG中的頂點.該查詢點qp由用戶任意選定.

定義8.(時間依賴路網(wǎng)查詢問題)一個查詢問題的實例：元組.其中，GT=(V，E，W)即為時間依賴路網(wǎng)圖，P是興趣點集，qp是一個查詢點，qp∈V，非負整數(shù)qt∈[0，T]指代查詢時間，非負整數(shù)mtt∈[0，T]指代最大等待時間.給定一個TDRNQ例子，問題是找到滿足以下條件的p∈P：

(i)tt(p，qp)≤wt；

(ii)?π∈V|tt(p，qp)≤tt(pi，qp)&p≠pi

條件1約束行程時間應(yīng)小于等待時間wt，條件2約束從p到qp的行程時間必須最小，且必須考慮到所有POI.

4 算法描述

本文研究的k近鄰查詢，致力于解決用戶對路網(wǎng)上移動服務(wù)的查詢需求，是查詢能以最短行駛時間到達查詢點的k個POI.對此設(shè)計了時間依賴路網(wǎng)上基于標記點的最短路徑樹TD-LSPT，在4.1節(jié)給出了相關(guān)概述.4.2節(jié)依據(jù)三角形不等式和啟發(fā)式函數(shù)，進一步提出了TDSPT-kNN算法來解決反向時間依賴路網(wǎng)上移動對象的k近鄰查詢問題.

4.1 時間依賴路網(wǎng)上的最短路徑樹及其更新

如圖3所示，是邊(C，G)權(quán)值由21增加到31的情況.粗線箭頭就是以A為根節(jié)點生成的最短路徑樹.當邊(C，G)權(quán)值增加時，節(jié)點A、B、C、D、E、G、H、K原最短路徑仍是合法的.但對于根節(jié)點A到虛線區(qū)域內(nèi)節(jié)點的最短路徑，必須進行更新.這些節(jié)點都是原有SPT中節(jié)點F(包含F(xiàn))的子孫節(jié)點.如圖4所示，是更新后的新SPT.如果到節(jié)點F、I、J、L、M的最短路徑不變，則這些節(jié)點的最短距離僅增加10.如果存在其他路徑可使其距離增值小于10，則進行更新.這些節(jié)點都有多條入邊.每條入邊都可能會定義新最短距離.例如，邊(C，F(xiàn))和(B，F(xiàn))都可以到達節(jié)點F，經(jīng)過邊(C，F(xiàn))到節(jié)點F的路徑最短距離將增加10.而通過邊(B，F(xiàn))則最短距離增加2.這意味著邊(B，F(xiàn))更優(yōu).如表2所示，列出了虛線區(qū)域內(nèi)節(jié)點所需要掃描的邊.

圖3 邊(C，F(xiàn))權(quán)值由21增加至31Fig.3 Edge(C，F(xiàn))weight increased from 21 to 31

表2首先列出需要更新的節(jié)點，其次列出節(jié)點的入邊.在第3行中，如果新最短路徑包含第2行的入邊，則給出距離增值.最后給出入邊是否有助于構(gòu)建新SPT的判斷.在給出節(jié)點的所有入邊中，第2行的邊對其節(jié)點的增量最小.當從邊集Q_SPT中提取一條邊時，該邊就是一條關(guān)鍵邊.在圖4中，關(guān)鍵邊就是(G，J)和(B，F(xiàn))，即在表2更新的邊.

表2 與需要更新的節(jié)點相連邊會影響新SPT的構(gòu)建Table 2 Connection edge with the node to be updated will affect the construction of the new SPT

圖4 邊(C，F(xiàn))權(quán)值由21增加至31所建立的新SPTFig.4 A new SPT based on the weight of edge(C，F(xiàn))increased from 21 to 31

給定節(jié)點集V′，定義源邊集S_Edge{N}和終邊集T_Edge{N}.其中V′ ?V，S_Edge{N}?E，T_Edge{N}?E.S_Edge{N}={e|S(e)∈N，T(e)?N}；T_Edge{N}={e|T(e)∈N，S(e)?N}.例如圖4所示，節(jié)點集V′={F，I，J，L，M}，S_Edge{N}={(F，D)，(F，E)，(F，G)，(I，H)}，T_Edge{N}={(B，F(xiàn))，(C，F(xiàn))，(E，I)，(G，J)，(H，L)，(K，M)}.即源邊集是SPT中與虛線范圍相交的且源節(jié)點在虛線范圍內(nèi)終節(jié)點在虛線范圍外的有向邊，終邊集是SPT中與虛線范圍相交的且源節(jié)點在虛線范圍外終節(jié)點在虛線范圍內(nèi)的有向邊.

在 TD-LSPT算法中，預(yù)處理包括兩個步驟：標記點選擇和原始SPT生成.標記點的選擇是啟發(fā)式的，所以我們只選擇靜態(tài)標記點，即使后續(xù)時間依賴路網(wǎng)變化標記點也不會更改.原始SPT可以通過靜態(tài)路網(wǎng)中的Dijkstra算法(處理無負權(quán)邊的圖)或Bellman-Ford算法[17](處理無負權(quán)環(huán)的圖)得到.在更新過程中，通過維護邊集Q_SPT和節(jié)點集合M，重新配置節(jié)點的父子關(guān)系.集Q_SPT中的每個元素都以{e，min_d}的形式存儲，其中min_d表示假設(shè)新的最短路徑通過e，節(jié)點T(e)的最短距離的增加值.M表征當邊權(quán)增加時受影響的節(jié)點的集合，可簡化更新SPT的計算.受影響待更新的節(jié)點都會被加入到點集M中.設(shè)節(jié)點v∈M，節(jié)點v帶有增值M.v.inc.M.v.inc是其入邊中最小的增值.同時點集M能確保邊集Q_SPT中沒有具有相同min_d的記錄.當節(jié)點S(e1)成為連續(xù)變化的臨時SPT中節(jié)點T(e1)的父節(jié)點時，用公式表示為P(T(e1))=S(e1)，節(jié)點T(e1)則為節(jié)點S(e1)的子節(jié)點.

更新SPT會根據(jù)邊權(quán)變化進行兩種操作.一種處理邊權(quán)增加，另一種處理邊權(quán)減小.邊權(quán)值增加時調(diào)用算法1，通過維護集合M能簡化添加/刪除元素及在邊集Q_SPT搜索最小min_d的計算.邊權(quán)減小時與增加操作類似，但需要注意無法判斷更新節(jié)點的確切范圍，會出現(xiàn)更短的最短距離對des(j)中的所有節(jié)點更新的情況.des(j)中節(jié)點最短距離的減小也會使其相鄰節(jié)點更新更短的最短距離.即邊權(quán)減小的影響可能會傳播.當處理完邊權(quán)變化后會等待下一個拓撲變化.

算法1.UPDATE-Increased算法

輸入：原SPT，邊e變化前后權(quán)值w(e)和w′(e)

輸出：更新后的SPT

1.d=w′(e)-w(e)；

2.M←j；M.j.inc=d；

3.Q_SPT.Enqueue(e，d) //?v∈des(j)更新

4.IfT(e)∈des(j)&S(e)?des(j)then

5.min_d=MIN{D(S(e))+w(e)-D(S(e))}

6.Ifmin_d

7.Q_SPT.Enqueue(e，min_d)；

8.m.v.inc=min_d；

9.IfP(k)=vthen

10.M←k；M.k.inc=M.v.inc；

11.ForQ_SPT≠?do

12.Q_SPT.Extract(e’，min_d)；

13.P(T(e)) =S(e)； //原SPT已改變

14. ?v∈des(E(e′))，D(v)=D(v)+min_d；//更新子節(jié)點

15.Ife∈S_Edge{des(T(e′))}&e∈T_Edge{M}then

16.min_d=D(S(e))+w(e)D(T(e))；

17.Ifmin_d

18.M.T(e).inc=min_d；//更新Q_SPT

19.Q_SPT.Enqueue(e，min_d)；

20. ReturnQ_SPT

當標記點原有SPT中邊權(quán)增加時算法1對其進行更新.引入點集M來表示路網(wǎng)圖GT中更新的節(jié)點.初始化階段(第1-2行)，M包含所有要更新的節(jié)點.將節(jié)點j和增值d一起加入到節(jié)點集M中.然后根據(jù)標記點原有SPT中根節(jié)點j的DFS序列搜索j的所有子孫節(jié)點(第4-5行).v的第一個節(jié)點j初始值為M.j.inc.用D(S(e))+w(e)-D(T(e))的增值來比對除去des(j)中具有初始節(jié)點后剩余每個節(jié)點v∈des(j)的入邊.選擇增值最小的邊e′，將其最小值min_d與M.v.inc進行比較(第6-8行).如果min_d較小，則將邊e′添加到邊集Q_SPT中，并更新M.v.inc.隨后，將臨時SPT節(jié)點v的子節(jié)點k加入到節(jié)點集M中，并附上M中節(jié)點v的增值(第9-10行).初始化過程確保Q_SPT中每條邊的增值都比其所有祖先小.初始化結(jié)束后，集合Q_SPT內(nèi)包含所有關(guān)鍵邊.

當邊集Q_SPT為空時，策略一的循環(huán)終止(第11行).此時已經(jīng)構(gòu)建好新SPT，TD-LSPT-UPDATE算法等待下一次邊權(quán)更改.如果非空，從Q_SPT中提取帶有最小增值的邊e′(第12行).一旦邊e′被取出，其初始節(jié)點S(e1)將成為維護SPT中的結(jié)束節(jié)點T(e′)的父節(jié)點(第13行).所有子孫節(jié)點des(T(e′))都可以通過增加min_d得到其新的最短距離(第14行).Q_SPT中的所有與des(T(e1))中終節(jié)點相連的邊都將被移除(第15行).更新的節(jié)點也從M中移除(第16行).此外，由于M中的一些節(jié)點會得到更小的最短距離增量，會對以des(T(e1))為源節(jié)點和M中節(jié)點為終節(jié)點的邊進行篩查(第17-19行).將這些邊添加到邊集Q_SPT中然后繼續(xù)執(zhí)行動態(tài)更新.

邊權(quán)值減小且對原SPT造成影響時也需要對標記點原有SPT進行.因為無法具體到更新哪些節(jié)點，所以不再使用節(jié)點集M.由于des(j)中所有節(jié)點的最短距離都減小了，所以會對des(j)中所有節(jié)點進行更新.如果該邊對原SPT造成影響則加入Q_SPT.終節(jié)點T(e)則選擇最小增值min_d的邊e′，如果min_d為負，則將邊e及其min_d加入到邊集Q_SPT中.創(chuàng)建的邊集Q_SPT包含所有關(guān)鍵邊.

4.2 反向時間依賴路網(wǎng)上移動對象的k近鄰查詢

k近鄰查詢算法分為預(yù)處理和查詢.預(yù)處理時建立相關(guān)路網(wǎng)和最短路徑樹；查詢時維護標記點的最短路徑及利用預(yù)處理信息和查詢算法返回滿足條件的k個對象.

圖5 反向時間依賴局部路網(wǎng)Fig.5 Reverse time-dependent local road network

預(yù)處理時首先使用路網(wǎng)圖GT的初值作為權(quán)值，并創(chuàng)建其反向時間依賴路網(wǎng).再通過4.1節(jié)算法選取標記點并生成相應(yīng)SPT，存儲標記點到達其后繼節(jié)點的最短路徑及其最短距離.

當時間依賴路網(wǎng)中有向邊的權(quán)值發(fā)生變化時，根據(jù)邊權(quán)變化執(zhí)行兩種更新操作.

擴展節(jié)點進行查詢時，越可能成為q最近鄰的路網(wǎng)POI優(yōu)先級越高，而優(yōu)先級高的會最早擴展.基于三角形不等式和標記節(jié)點的動態(tài)最短路徑樹，構(gòu)造如下啟發(fā)函數(shù)來引導搜索，使每個頂點路徑規(guī)劃始終趨向于最近POI：

f(n)=maxl∈L{d(l，t)-d(l，n)，d(n，l)-d(t，l)}

(3)

式(3)中：f(n)表示從節(jié)點n到達終點t的預(yù)估距離，對于每個標記節(jié)點l∈L，根據(jù)三角不等式兩邊之差小于第三邊可知d(n，t)≥d(l，t)-d(l，n)且d(n，t)≥d(n，l)-d(t，l)，遍歷所有標記節(jié)點后將f(n)取值為最大值.

TDSPT-kNN算法如算法2所示.依據(jù)輸入的查詢點q的具體路網(wǎng)位置點開始，同時將查詢時間點及最大行程時間作為參數(shù)，構(gòu)建優(yōu)先隊列Q_NN來擴展搜索近鄰POI，同時用隊列R來保存結(jié)果集.算法2開始擴展并在1-3行初始化相關(guān)值，開始先將查詢點q插入到優(yōu)先級隊列Q_NN中(第4行).存放尚未展開擴展節(jié)點的隊列Q_NN是以四元組(v，TTv，ATv，hv)的形式存儲，v是節(jié)點，TTv=TT(q，v，t)代表從q到v的行駛時間，ATv=AT(q，v，t)代表到達v的到達時間，hv是啟發(fā)式函數(shù)值加TTv，對于查詢點q直接位于標記點，POI位于標記點，查詢點q和POI處于同一標記點最短路徑樹中可直接得出.若是以上3種情況外，則可通過啟發(fā)式函數(shù)hv=TTv+f(v)/vmax引導擴展，f(v)/vmax是從v點到達最近POI的行駛時間的估計.hv小的節(jié)點優(yōu)先從隊列Q_NN中出隊來進行搜索(第6行)，當頂點u出隊后，會將其標記為已訪問(第7行)，如果出隊頂點u是POI且hu小于R集合中第k個POI，則將u插入到結(jié)果集R中(第10行).由于u是POI，因此hu表示從u到q的通行時間.如果hu已經(jīng)大于或等于R中第k個POI，則搜索結(jié)束，R中前k個POI作為近鄰結(jié)果集返回(第13行).檢查近鄰點v的訪問標識，為真則跳過(第15行).接著計算當前TT，超過最大行程時間則直接跳過(第16-17行).隨著節(jié)點的擴展，計算到達時間(第18行).

算法2.TDSPT-kNN算法

輸入：查詢點q∈V，最大行程時間t∈[0，T]

輸出：依據(jù)最大行程時間t能以最快時間到達查詢點的k個近鄰結(jié)果集

1.TTmax= 0；

2.ATq=t+dt； //初始化q到達時間

3.kth_R=∞； //結(jié)果集R

4.Q_NN.Enqueue(q，TTmax，ATq，hq)； //查詢點q先進隊

5.WhileQ_NN≠ ?do

6. (u，TTmax，ATu，hq)=Q_NN.Dequeue； //隊頭u出隊

7.u.visited=true；

8.If(TTmax≤t)then

9.If(uis POI)&&(hu

11.If(R.size>k)then

12.kth_R=H′of thek-thobject inR；

1http：//www.cs.utah.edu/～lifeifei/SpatialDataset.htm

13.Elsereturntop-k objects inR；

14.Foreachadjacencyvofudo

15.If(v.visited)thencontinue；

16.TTc=u_TravelT+v_dist(u，v)；//計算通行時間

17.If(TTc>t)thencontinue；

18.ATc=u_ArrivalT-v_dist(u，v)；

19.Q_NN.Enqueue(v，ATc，TTc，Lv)；//v進隊

5 實驗及分析

為驗證TDSPT-kNN算法的性能及其有效性，我們設(shè)計了兩組實驗對TDSPT-kNN算法進行測試.我們提出的TDSPT-kNN算法著力于解決在時間依賴路網(wǎng)中離查詢點Q最近的k個興趣點的問題，所以我們將其與能解決相類似k近鄰查詢問題的NN-Reverse-TD算法[18]進行比較.NN-Reverse-TD算法利用增量式網(wǎng)絡(luò)擴展INE算法和啟發(fā)函數(shù)在時間依賴路網(wǎng)上將最近的移動對象及時返回給查詢點.

實驗環(huán)境為：Windows10操作系統(tǒng)，Intel Core i5-3470 CPU @ 3.20GHz 處理器，主頻3.20GHz，內(nèi)存4GB.上述算法均用C++語言實現(xiàn)，編譯器為GNU Compiler Collection.

5.1 數(shù)據(jù)集設(shè)置

采用Brinkhoff[19]提出的用于路網(wǎng)的移動對象的生成器來創(chuàng)建綜合數(shù)據(jù)集，選取示例中的奧爾登堡(德國)路網(wǎng)圖1進行仿真實驗.路網(wǎng)圖含7035個有向路段和6105個節(jié)點，每隔5min對邊賦權(quán)值.將提出的TDSPT-kNN算法，通過實驗對比已有算法NN-Reverse-TD，得出k值與查詢響應(yīng)時間和查詢遍歷節(jié)點個數(shù)的關(guān)系和興趣點密度與查詢響應(yīng)時間和查詢遍歷節(jié)點個數(shù)的關(guān)系.令k為集合 {1，5，10，15，20，25，30}，興趣點密度默認值為0.1.設(shè)興趣點密度為集合{0.05，0.1，0.15，0.2}中的值，k默認值為15.實驗參數(shù)如表3所示.每個實驗都采取控制變量法.為了盡量減少隨機性造成的差異，在相同環(huán)境下進行30次測試，同時以去掉最大最小值后剩余28次測試值的平均值作為算法性能的參考指標.

表3 實驗參數(shù)Table 3 Parameters values of experiments

5.2 近鄰個數(shù)k值變化對算法性能的影響

令k∈{1，5，10，15，20，25，30}，POI密度取默認值0.1.對不同k值，隨機進行30次查詢，取除去最大最小值后剩余28次測試值的平均值.如圖6所示，兩種算法隨近鄰個數(shù)k值從1到30的變化對查詢性能的影響.圖6(a)比較了TDSPT-kNN算法和NN-Reverse-TD算法在k值增加的情況下的查詢響應(yīng)時間.圖6(b)顯示隨k值增加查詢遍歷節(jié)點個數(shù)兩者變化的對比.圖6(c)顯示了TDSPT-kNN算法節(jié)點剪枝比例.隨著k值從1到30的變化過程中，所有算法的查詢響應(yīng)時間和遍歷節(jié)點個數(shù)與k值正相關(guān)，這是因為需要擴展更多的路網(wǎng)信息才能計算出最終結(jié)果，而擴展節(jié)點的同時會帶來響應(yīng)時間的增加.

圖6 近鄰個數(shù)k值數(shù)據(jù)量對算法性能的影響Fig.6 Performances with the number of nearest neighbours on algorithm

TDSPT-kNN算法遍歷節(jié)點個數(shù)隨k值增加而緩慢增加，且性能遠遠優(yōu)于NN-Reverse-TD算法.由于TDSPT-kNN算法為基于時間依賴路網(wǎng)中的地標及其相關(guān)動態(tài)最短路徑樹，能夠有效減少整體擴展節(jié)點，優(yōu)先朝能夠以更短時間到達查詢點的POI擴展，即查詢規(guī)劃始終趨向于目標終點.而NN-Reverse-TD算法在時間依賴路網(wǎng)下進行近鄰搜索擴展時僅將時間依賴路網(wǎng)節(jié)點的啟發(fā)值設(shè)為該節(jié)點到最近POI之間的距離，因此TDSPT-kNN算法遠比NN-Reverse-TD算法遍歷節(jié)點個數(shù)少，算法更高效.

在算法響應(yīng)時間方面TDSPT-kNN算法比NN-Reverse-TD算法平均減少64.9%.在計算結(jié)果時，隨著k值的增加，所需要遍歷的節(jié)點增加，算法所花費的代價就增大.而當k值為1時，算法的開銷差距受遍歷節(jié)點范圍影響，相差較小.

5.3 路網(wǎng)POI密度對算法性能的影響

將POI的密度設(shè)置為0.05，0.1，0.15，0.2，在不同密度下，令k取默認值15隨機進行30次查詢，取除去最大最小值后剩余28次測試值的平均值.如圖7所示，兩種算法隨路網(wǎng)POI密度的變化，查詢響應(yīng)時間和擴展節(jié)點數(shù)的變化趨勢.本文比較了TDSPT-kNN算法和NN-Reverse-TD算法，得出隨路網(wǎng)POI密度變化的查詢響應(yīng)時間的平均值對比曲線.由圖7(a)給出了POI密度增加對兩種算法的響應(yīng)時間的影響，TDSPT-kNN算法的查詢響應(yīng)時間一直小于NN-Reverse-TD算法.如圖7(b)所示，路網(wǎng)POI密度變化對兩種算法遍歷節(jié)點個數(shù)的影響.POI密度增加后，每個點作為興趣點的概率增加，因此只需要訪問更少的頂點就可以返回規(guī)定數(shù)量的對象結(jié)果，兩啟發(fā)式算法耗費的時間也會隨之減少.所以如圖7(c)所示，TDSPT-kNN算法節(jié)點剪枝比例隨著POI密度的增加，優(yōu)化質(zhì)量有所下降.

圖7 POI密度對算法性能的影響Fig.7 Performances with the POI density on algorithm

在路網(wǎng)POI密度對算法性能的影響中，TDSPT-kNN算法比NN-Reverse-TD算法的平均擴展頂點個數(shù)減少66.3%，響應(yīng)時間減少65.7%，這是因為TDSPT-kNN算法采用的啟發(fā)值更接近實際值，能優(yōu)先擴展更快到達POI的頂點，因此訪問了更少的頂點，降低了算法的響應(yīng)時間.算法的響應(yīng)時間和搜索過程中訪問到的頂點數(shù)目關(guān)系密切，因此也可以發(fā)現(xiàn)兩者的變化趨勢大致相同.

6 結(jié)束語

本文從時間依賴路網(wǎng)出發(fā)，針對路網(wǎng)上移動對象的k近鄰查詢問題進行深入研究，提出反向時間依賴路網(wǎng)上移動對象的k近鄰查詢解決方案.在分析現(xiàn)有查詢算法的不足基礎(chǔ)上，建立了反向時間依賴路網(wǎng)和基于標記點的最短路徑樹.在此基礎(chǔ)上，給出了反向時間依賴路網(wǎng)上移動對象的k近鄰查詢算法TDSPT-kNN.通過采用基于最短路徑樹的啟發(fā)式函數(shù)等剪枝策略，進一步提升查詢效率.最后，通過仿真實驗對TDSPT-kNN算法和已有算法在多種情況下的對比分析，結(jié)果表明該方法的高效性.我們未來的研究重點將放在解決弱影響集的相關(guān)問題，例如出租車司機更傾向于搭載能收益最大化的乘客.