安云哲,倪燦燦,李佳佳,張安珍,夏秀峰

（沈陽航空航天大學(xué)計算機學(xué)院,遼寧 沈陽 110136）

隨著配備GPS的智能設(shè)備的激增,類似于滴滴出行、Uber等平臺已經(jīng)成為用戶必不可少的出行工具,與傳統(tǒng)的系統(tǒng)相比,此類設(shè)備在減少出租車空車時間和乘客等待時間方面有了顯著的進步.同時,它們也促進了路網(wǎng)中大量基于位置查詢的研究,其中,k近鄰（k-Nearest Neighbor,kNN）查詢作為一種技術(shù)支持,在此類設(shè)備中發(fā)揮了重要的作用.kNN查詢問題目前在靜態(tài)路網(wǎng)和時間依賴路網(wǎng)中都有著廣泛的研究,但是由于與本文的問題定義不同等原因,無法直接用于本文中提出的問題.

首先,靜態(tài)路網(wǎng)中針對kNN查詢的研究已經(jīng)非常成熟,例如INE[1]（增量網(wǎng)絡(luò)擴展）、IER[1]（增量歐幾里得約束）、ROAD[2]、和G-tree[3]等,在靜態(tài)路網(wǎng)中,邊的權(quán)值是固定不變的,只能通過兩點之間路網(wǎng)距離的遠(yuǎn)近來表示代價的大小.然而,在實際生活中,路網(wǎng)的權(quán)值是隨著時間的變化而變化的,影響權(quán)值的因素有交通堵塞、天氣變化等,在同一天中,同一條邊的權(quán)值會發(fā)生多次改變,所以,路網(wǎng)中邊的權(quán)值應(yīng)該是一條隨著時間變化的分段線性函數(shù),僅通過距離的遠(yuǎn)近并不能反映路網(wǎng)中的真實代價.所以針對這一問題,本文提出了時間依賴路網(wǎng)中的k近鄰查詢,不再用距離的遠(yuǎn)近來衡量查詢對象到達查詢點的代價,而是使用在時間依賴路網(wǎng)中的實際通行時間來表示該代價.

其次,傳統(tǒng)的kNN查詢的方向是從查詢點到移動對象,以查詢點為中心逐步向外擴展,直到獲得k個時間代價最小的移動對象,如Dijkstra算法[4].而本文關(guān)注的是查詢點保持不動,從移動對象到查詢點的查詢,與傳統(tǒng)查詢方向相反.在靜態(tài)路網(wǎng)中,邊的權(quán)值是不變的,所以解決查詢方向相反的問題,可以將路網(wǎng)進行反轉(zhuǎn),即將路網(wǎng)中所有有向邊的權(quán)值設(shè)為其對應(yīng)反向邊的權(quán)值.通過在反向圖中進行擴展,就可以得到從移動對象到查詢點的代價,進而選擇代價更小的移動對象作為返回結(jié)果.但是在時間依賴路網(wǎng)中,點和點之間的代價是一個與時間相關(guān)的線性函數(shù),邊的時間代價與出發(fā)時間有關(guān),并且對于同一條邊,在同樣的查詢時間,兩個方向的時間代價也不同,所以無法通過簡單的反轉(zhuǎn)來進行從移動對象到查詢點方向的kNN查詢.針對這一問題,本文提出了一種基于網(wǎng)格索引的查詢框架,將當(dāng)前訪問的網(wǎng)格邊緣到達查詢點的最小時間代價作為上界值,與當(dāng)前找到的第k大的時間代價作比較,當(dāng)?shù)趉大的時間代價大于上界值時,終止算法.通過該方法,將查詢范圍大大縮小,避免了對路網(wǎng)的全局訪問,極大地提高了kNN查詢的效率.

再次,現(xiàn)有的針對靜態(tài)對象的kNN查詢,可以先對靜態(tài)對象建立索引,在每次查詢來到時,都訪問這個固定不變的索引來提高查詢效率.TOAIN算法[5]可以從預(yù)先計算的最近下坡對象中獲取kNN查詢結(jié)果,TEN*算法[6]對每一個節(jié)點預(yù)計算其子樹節(jié)點的kNN結(jié)果,查詢時只需要訪問從查詢點到根節(jié)點預(yù)存的kNN結(jié)果,就能獲得查詢點的kNN結(jié)果.但是對于在每次查詢開始之前位置都會發(fā)生改變的移動對象,索引會隨著位置的更新而失效.另外對于時間依賴路網(wǎng)來說,不同的查詢時間會使每一個頂點對應(yīng)著不同的kNN結(jié)果,索引也會隨著查詢時間的不同而失效.上述兩種問題會導(dǎo)致巨大的索引更新代價,尤其是在索引建立代價更大的時間依賴路網(wǎng)中,所以此方法不適用于時間依賴路網(wǎng)下面向移動對象的近鄰查詢.針對這一問題,同樣可以使用本文提出的查詢框架,利用網(wǎng)格索引對移動對象的位置進行定位,在每次查詢開始之前,可以快速地確定每個移動對象所屬的網(wǎng)格,并且在網(wǎng)格擴展的過程中,對當(dāng)前網(wǎng)格中的移動對象進行訪問.

最后,時間依賴路網(wǎng)中的kNN查詢往往是從用戶的角度出發(fā),找到k個能夠最快到達用戶所在位置的移動對象,但是如果從移動對象的角度考慮,會存在由于調(diào)度不合理而造成的時間浪費的情況.例如,一些當(dāng)前被占用的移動對象,雖然需要先將當(dāng)前用戶送到目的地,再從目的地到達查詢點,如果該目的地距離查詢點位置很近,其到達查詢點的時間代價甚至?xí)纫恍]有被占用的移動對象要小,但是由于處于被占用狀態(tài),所以無法參與調(diào)度.另一方面,對于用戶來說,希望車輛在一個指定的時間范圍內(nèi)到達,這種情況下如果還是一味的追求時間代價最小,會導(dǎo)致一些距離查詢點較近的移動對象提前到達,空車時間較長.所以本文同時考慮了被占用和未被占用的移動對象,并且提出了限制到達時間的k近鄰查詢,目的是在滿足用戶的時間要求的前提下,將移動對象的空車時間作為查詢結(jié)果的選取標(biāo)準(zhǔn),最終得到k個既滿足用戶要求,空車時間又最短的移動對象.

1 相關(guān)工作

1.1 靜態(tài)路網(wǎng)中的kNN查詢算法

解決靜態(tài)路網(wǎng)中的kNN查詢問題,最經(jīng)典的方法是基于Dijkstra[4]的增量擴展方法INE算法[1],該算法無需索引結(jié)構(gòu).G-tree[3]設(shè)計了一個層次結(jié)構(gòu),將路網(wǎng)劃分為由若干子圖構(gòu)建成的樹結(jié)構(gòu),保存子圖中邊界點和非邊界點之間的距離矩陣,采用自頂向下的方式來回答kNN查詢.TEN*算法[6]同樣使用將路網(wǎng)分解為樹結(jié)構(gòu)的方法,保存樹中每個節(jié)點的部分kNN,在查詢時,只需要訪問從查詢點到根節(jié)點中所有頂點的部分kNN結(jié)果,并且返回其中距離查詢點最近的k個點.但是對于每次查詢之前位置都要發(fā)生改變的移動對象來說,預(yù)存部分kNN結(jié)果的方法會導(dǎo)致索引更新的代價非常大.

1.2 時間依賴路網(wǎng)中的kNN查詢算法

Cooke等[7]第一次提出并解決了時間依賴路網(wǎng)的最短路徑查詢問題.文獻[8-9]借鑒INE的增量網(wǎng)絡(luò)擴展的思路,從查詢點開始向外擴展,直到找到k個查詢點能夠最快到達的移動對象,但無法解決查詢方向從移動對象到查詢點的問題.為提高在線查詢的效率,一些索引結(jié)構(gòu)被提出,文獻[10]計算并預(yù)存了查詢時間范圍內(nèi)幾個子區(qū)間的最小時間代價,在查詢時,利用類似A*算法的擴展方式,將最小時間代價作為啟發(fā)值來使用,直到找到kNN查詢結(jié)果.這種索引結(jié)構(gòu)由于預(yù)估的時間代價和實際代價偏差較大,無法應(yīng)用于大型路網(wǎng).文獻[11]提出了兩種互補的索引結(jié)構(gòu)緊密網(wǎng)絡(luò)索引TNI和松散網(wǎng)絡(luò)索引LNI,每個查詢對象的TNI和LNI都是根據(jù)行駛時間的上限和下限預(yù)先計算的.如果查詢點位于某一個對象的TNI單元中,那么該對象一定是查詢點的最近鄰結(jié)果,如果查詢點不在任何對象的TNI單元中,而是在某一對象的LNI單元中,那么將該對象作為潛在的候選對象.該索引結(jié)構(gòu)僅適用于靜態(tài)的查詢對象,當(dāng)對象位置發(fā)生改變時,TNI和LNI的單元需要重新計算,更新代價大,因此無法用于解決針對移動對象的查詢.

1.3 時間依賴路網(wǎng)中帶有時間限制的最短路徑查詢算法

考慮時間限制的kNN查詢算法較少,但有一部分工作研究了時間限制下的最優(yōu)路徑查詢問題.楊雅君等[12]針對時間限制下的最優(yōu)路徑查詢問題,基于“到達某個頂點的最早時刻可以通過到達其鄰居的最早時刻計算得出”這一重要性質(zhì),提出了一種兩階段搜索算法.Omer等[13]則假定移動對象可以通過推遲出發(fā)時間或者在特定的地點停下來以避免在高峰時間的時間浪費,但是該研究只考慮如何避免浪費移動對象的時間,沒有考慮到達時間限制.盡管kNN問題可通過執(zhí)行多個最優(yōu)路徑查詢來解決,但首先要搜索得到潛在的移動對象,計算出所有候選對象到查詢點的最優(yōu)路徑,查詢效率低.此外,上述方法由于時間依賴路網(wǎng)不能像靜態(tài)路網(wǎng)一樣進行反轉(zhuǎn),所以此類方法無法直接用來解決TD-LkNN查詢.

2 問題定義

定義1.時間依賴有向路網(wǎng)：定義時間依賴有向路網(wǎng)G=（V,E,F,T）,其中vi∈V代表路網(wǎng)中的節(jié)點集合,（vi,vj）∈E代表路網(wǎng)中邊的集合,f（vi,vj）∈F代表邊（vi,vj）的時間依賴函數(shù),T代表時間周期（例如一天中T=1 440 min）.

移動對象集合M為V的子集,為了方便理解,本文假設(shè)移動對象的位置在路網(wǎng)節(jié)點上[5].在實際應(yīng)用中,不在節(jié)點上的對象可以表示為具有偏移量的對象,與節(jié)點之間的距離可以使用文獻[5]中的公式進行計算.本文的移動對象具有被占用和未被占用兩種狀態(tài),被占用對象的當(dāng)前位置和目的地位置不同,td代表從移動對象當(dāng)前位置到達目的地的時間代價,對于未被占用對象,當(dāng)前位置和目的地相同,td=0.

定義2.時間依賴路網(wǎng)中的時間代價：在路網(wǎng)G中定義一條路徑p={v1,v2,…,vn},該路徑的時間代價表示為

式（1）中：t1=t,ti=ti-1+f（vi-1,vi）（ti-1）,i=2,...,n-1.

給定起點s,終點d和查詢時間t,P為路網(wǎng)G中從s到d所有路徑的集合,定義s到d的最小時間代價為P中所有路徑的時間代價的最小值

定義3.空車時間：指定期待到達時間范圍[T1,T2],時間上限為T2,定義空車時間Te（oi,q,t）如下

定義4.時間依賴路網(wǎng)中的LkNN查詢：給定一個查詢點q,一個時間段[T1,T2],一個移動對象集合M,查詢時間t,一個值k,其中k≤|M|,和時間依賴有向路網(wǎng)G=（V,E,F,T）,TD-LkNN查詢返回一個具有k個移動對象的集合R∈M,對于任意的oi∈R,滿足條件：1）TFTC（oi,q,t）≤T2;2）Te（oj,q,t）≥Te（oi,q,t）,其中oj∈MR.

3 查詢算法

3.1 TIGR算法

針對本文中移動對象到查詢點的查詢,最直觀的方法是計算路網(wǎng)中所有移動對象到達查詢點的時間代價和空車時間,從中選出最合適的k個作為查詢結(jié)果,但是這樣會導(dǎo)致查詢范圍過大,查詢效率較低.為了避免對路網(wǎng)中移動對象的全局訪問,本文使用了一種基于網(wǎng)格索引的查詢框架,來找到查詢點附近潛在的移動對象,只需要對這些移動對象進行訪問即可,極大地縮小了查詢范圍.

為了計算候選集中移動對象到查詢點的時間代價和空車時間,本文使用了TD-G-tree算法.TD-G-tree是一種計算時間依賴路網(wǎng)中的最快路徑查詢算法,該算法使用圖分割將路網(wǎng)劃分為若干個大小相似的子圖,將每一個子圖作為樹中的一個節(jié)點構(gòu)造出一棵平衡樹.通過在樹結(jié)構(gòu)中保存大量的中間結(jié)果來加速查詢的效率,算法具體細(xì)節(jié)可以參考文獻[14].

TIGR算法的查詢過程如圖1所示,算法首先找到k個到達查詢點的時間代價小于時間上限的移動對象,將這k個移動對象放入候選集中,并將其中第k大的空閑時間作為當(dāng)前的上界Tk.取Tk和時間上限T2之間的最小值,用來劃定一個歐式空間下的查詢范圍,如圖1-a所示.當(dāng)查詢的網(wǎng)格范圍大于圖1-a中在Tk內(nèi)部的范圍時,說明當(dāng)前網(wǎng)格邊緣到達查詢點的最小時間代價已經(jīng)不滿足查詢要求,即外層網(wǎng)格中所有移動對象到達查詢點的空車時間都大于Tk,不需要再對外層網(wǎng)格中的移動對象進行訪問,算法達到終止條件.反之,如果查詢的網(wǎng)格范圍小于劃定的查詢范圍,那么可以繼續(xù)對下一層網(wǎng)格中的移動對象進行訪問,如果訪問到的移動對象ok’能夠提供更小的上界值Tk’,則將當(dāng)前的上界值更新為更小的值,可以進一步縮小查詢范圍,如圖1-b所示.

圖1 TIGR算法思想Fig.1 The idea of TIGR algorithm

在查詢之前,先將路網(wǎng)劃分為若干個大小相等的網(wǎng)格,利用網(wǎng)格索引定位每個移動對象目的地的所屬網(wǎng)格.以圖2為例,{o1,o2,o3,o4,o5,o6}代表6個移動對象目的地的位置,括號中的內(nèi)容代表從移動對象的當(dāng)前位置到達目的地的時間代價.假設(shè)每個網(wǎng)格的寬度為10 km,路網(wǎng)中移動對象的最大行駛速度為1 km/min,那么可以得到,穿過每一個網(wǎng)格的最小時間代價為10 min.

圖2 TIGR算法詳例Fig.2 Example of TIGR algorithm

在圖中進行一個k=2的TD-LkNN查詢,用戶期望移動對象到達的時間段為[10,20]min.首先從查詢點q所在網(wǎng)格開始,在擴展完第一層網(wǎng)格后,得到兩個移動對象o1,o2,這兩個移動對象到達q的時間代價分別為{10,15},小于時間上限20,空車時間分別為{5,15},將這兩個移動對象放入候選集C中.此時候選集中移動對象數(shù)量達到了k個,Tk的值為15,此時路網(wǎng)中的空車時間上限UB的值也是15.接下來計算第二層網(wǎng)格邊緣到查詢點所在網(wǎng)格的最小時間代價,得到LB=10,小于當(dāng)前的UB,說明外層網(wǎng)格中可能存在空車時間更小的移動對象,可以對第二層網(wǎng)格進行擴展,并且對其中的移動對象進行訪問.第二層網(wǎng)格中的三個移動對象o3,o4,o5到達查詢點的時間代價分別為{25,15,21},其中o3,o5不滿足時間限制,不符合查詢點要求,不再對其進行后續(xù)訪問.計算得到對象o4到達查詢點的空車時間為10,小于15,那么將對象o4放入候選集中,并且將Tk的值和UB更新為10.當(dāng)對下一層網(wǎng)格進行擴展時,事先計算出第三層網(wǎng)格LB的值為20,說明外層網(wǎng)格中所有移動對象的目的地到查詢點的時間代價大于UB,則空車時間也大于UB,不需要再向外擴展,最終返回候選集中空車時間最小的兩個移動對象o1,o4作為LkNN查詢結(jié)果.

算法的偽代碼如算法1所示,給定時間依賴路網(wǎng)G,查詢點q,網(wǎng)格索引L,查詢時間t,和期望到達時間范圍[T1,T2].算法以查詢點所在網(wǎng)格為中心向外逐層擴展,直到得到k個滿足條件的結(jié)果為止.算法前4行定義一些初始值,算法使用集合C來存儲移動對象的候選集,集合H表示當(dāng)前訪問的網(wǎng)格,初始化為查詢點所在網(wǎng)格,集合NH表示當(dāng)前訪問網(wǎng)格的外層網(wǎng)格集合.UB表示訪問完NH中所有移動對象之后,當(dāng)前候選集中第k個移動對象到達q的空車時間,初始化為時間上限T2.在擴展過程中,本算法維護一個從當(dāng)前訪問網(wǎng)格到查詢點時間代價的下界值LB,用網(wǎng)格邊緣與查詢點所在網(wǎng)格之間的歐氏距離除以移動對象在路網(wǎng)中的最大移動速度得到.

算法第5行是對算法終止條件的判斷.在第8-16行中,如果候選集中移動對象數(shù)量沒有達到k個,則逐個訪問網(wǎng)格中的移動對象,并將滿足時間限制的放入候選集中,達到k個之后,需要將每一個滿足時間限制的移動對象的空閑時間與候選集中第k個移動對象的空閑時間Tk進行比較,保留其中更小的值,并更新Tk的值.每訪問完一層網(wǎng)格之后,算法17-19行將為下一層網(wǎng)格的擴展做準(zhǔn)備.達到算法終止條件之后,20行返回候選集中的前k個移動對象作為LkNN的查詢結(jié)果.

算法1:TIGR算法輸入:路網(wǎng)G=（V,E,F,T）、查詢點q、網(wǎng)格索引L、查詢時間t、時間間隔[T1,T2]輸出:q的TD-LkNN查詢結(jié)果1 Let h be the grid containing q,2 Let C be the candidate set;3 Let UB be the upper bound of Te and initially set to T2;4 Let LB←0;5 While UB＞LB do 6 Let L（NH）be the set of objects in NH;7 for each o∈L（NH）do 8 ifC.size（）＜kthen 9 if TFTC(o,q,t)≤T2 then 10 compute Te(o,q,t);11 C←0;12 else 13 Tk=Min{k-th largest Te of objects in C,T2};14 ifTFTC（o,q,t）T2 then 15 if Te（o,q,t）＜Tkthen 16 C←o,Update Tk;17 H←HUNH,UB←Tk;18 Let NH be the set of grids that are neighbors of H but excluding the grids in H 19 Let DL be the minimum Euclidean distance from q to the edge of NH,LB←DL/Speedmax;20 Return top-k objects in C;images/BZ_68_1006_660_1212_686.png

3.2 TIGR_P查詢算法

在TIGR算法中,部分移動對象在任意查詢時間下的時間代價均大于時間上限.還存在時間代價過大的被占用對象和空車時間過大的未被占用對象,為了避免對此類移動對象的訪問,本節(jié)提出了三種剪枝策略以及TIGR_P算法,對TIGR算法的查詢效率進行改進.在介紹算法之前,先給出一些相關(guān)定義,然后詳細(xì)介紹三種剪枝策略.

定義5.下界圖：給定時間依賴路網(wǎng)G=（V,E,F,T）,定義下界圖Gl=（Vl,El）為一個靜態(tài)的有向圖,其中Vl=V,El=E,所有邊（vi,vj）E的權(quán)值都是時間依賴函數(shù)f（vi,vj）的最小值.

定義6.時間代價下界：在下界圖Gl中給定一條路徑pl={v1,v2,...,vn},路徑pl的代價CGl（pl）定義為路徑pl中所有邊的權(quán)值之和.對于Gl中的查詢起點s和終點d,pl代表從s到d所有的路徑,定義時間代價下界LBC（s,d）=minp∈PlCGl（p）.

與靜態(tài)路網(wǎng)相比,時間依賴路網(wǎng)中任意兩點間最快路徑的計算代價明顯更大,所以對于在任意查詢時間下,時間代價均大于時間上限的移動對象,可以先對時間依賴路網(wǎng)的下界圖建立一個靜態(tài)索引,通過該靜態(tài)索引計算出移動對象到達查詢點的時間代價下限,根據(jù)該時間代價下限來避免在時間依賴路網(wǎng)中對這些移動對象進行計算.基于此,本文提出了剪枝策略1.

策略1.下界圖剪枝.根據(jù)定義5可以得到,如果利用下界圖得到某一個移動對象oa到達查詢點q的時間代價下界LBC（oa,q）大于移動對象ob到達查詢點的真實時間代價,那么在任意查詢時間,oa到達q的真實時間代價都會大于ob到達查詢點的真實時間代價.

證明1：給定兩個移動對象oa和ob,查詢時間t和查詢點q,如果LBC（oa,q）＞TFTC（ob,q,t）,那么對于任意的t∈[0,T],有

為了更好地使用這一策略,本文在下界圖上建立了一個靜態(tài)的H2H索引[15]來進行時間代價下界的計算.在給定時間范圍[T1,T2]的前提下,部分移動對象到達查詢點的最小時間代價會大于時間上限T2,從而無法成為查詢結(jié)果,導(dǎo)致本次最小時間代價的計算是無效的.針對這一情況,可以先利用下界圖計算每一個移動對象到達查詢點的LBC是否大于T2,如果LBC大于T2,那么可以對該移動對象進行剪枝,不需要再計算該移動對象到達查詢點的具體時間代價.

由于被占用的移動對象需要先從當(dāng)前位置到達其目的地,所以存在這一段路程的時間代價過大的情況,對于這樣的被占用對象,即使其目的地到達查詢的時間代價非常小,也會存在整體時間代價大于時間上限的情況,所以要避免對此類移動對象的訪問.基于此,本文提出了剪枝策略2.

策略2.被占用對象剪枝.根據(jù)定義1,被占用對象o擁有一個從當(dāng)前位置到達目的地的時間代價td,當(dāng)td大于T2時,可以對該移動對象進行剪枝.

證明2：對于被占用對象o,如果td＞T2,那么TFTC（o,q,t+td）+td＞T2.

對于未被占用的移動對象,由于從響應(yīng)查詢開始就處于空車狀態(tài),所以從當(dāng)前位置到達查詢點的整段路程,都是在產(chǎn)生空車時間的路程,由此可以得到,在給定時間范圍[T1,T2]后,未被占用對象的最小空車時間為T1.如果當(dāng)前路網(wǎng)中地空車時間最小值Tk＜T1,意味著當(dāng)前路網(wǎng)中所有未被占用對象的空車時間都會大于Tk,即所有的未被占用對象都不會成為查詢結(jié)果.所以在查詢過程中需要不斷判斷Tk的值是否已經(jīng)小于時間下限T1,如果滿足該條件,則可以終止對后續(xù)所有未被占用對象的訪問.基于此,本文提出了剪枝策略3.

策略3.未被占用對象剪枝.對于未被占用對象,如果從移動對象到達查詢點的最小時間代價小于T1,并且當(dāng)前Tk＜T1,那么該移動對象可以被剪枝.

證明3：由公式3可知,對于未被占用對象o,如果TFTC（o,q,t+td）+td＜T1,則Te（o,q,t+td）=T1.已知Tk＜T1,則Te（o,qt+td）＞Tk.

本算法的查詢框架與算法1相同,偽代碼也與算法1類似,只在剪枝策略的使用上有所不同.在算法1第13行,得到Tk后,使用剪枝策略3,判斷當(dāng)前候選集中第k個移動對象到達查詢點的空車時間Tk是否小于時間下限T1,如果滿足條件,則停止對未被占用對象的訪問.在算法1的第14-16行,需要計算網(wǎng)格中每個移動對象到查詢點的具體時間代價和空車時間之前,使用剪枝策略1和2,先計算每一個移動對象到達查詢點的時間代價下界,如果時間代價下界大于時間上限T2,則該移動對象被剪枝.同時對于每一個被占用對象,判斷td是否大于時間上限T2,如果滿足條件,則該被占用對象被剪枝.

4 實驗驗證

4.1 實驗條件

本文算法均由C++語言編寫,使用GNN GCC進行編譯.實驗平臺為Linux（Ubuntu18.04）操作系統(tǒng),CPU型號為Intel（R）Xeon（R）W-2245,內(nèi)存256 GB.

4.2 實驗數(shù)據(jù)

本文使用紐約市真實路網(wǎng)進行實驗,根據(jù)文獻[14],本文同樣模擬每天的三個時間段,分別是早高峰之前,早高峰與晚高峰之間和晚高峰之后,使用四個拐點（x1,y1）,（x2,y2）,（x3,y3）,（x4,y4）擬合成一條分段線性函數(shù),作為邊的時間依賴函數(shù).在每天的1 440 min中,拐點橫坐標(biāo)x1=0,x4=1 440,x2∈[510,570）,x3∈[990,1 070）,x2,x3是在對應(yīng)時間范圍內(nèi)隨機選取的一個值.對于縱坐標(biāo),本文首先設(shè)置兩個速度指標(biāo),包括非高峰期的行駛速度sp1∈[500,900]m/min,和高峰期的行駛速度sp2∈[300,750]m/min,對于路網(wǎng)中長度為l（u,v）的邊（u,v）,縱坐標(biāo)的值

本文實驗參數(shù)設(shè)置如表1所列,加粗?jǐn)?shù)字代表實驗參數(shù)的默認(rèn)值,其中比例θ代表被占用對象占移動對象總數(shù)的比例,時間范圍γ代表在指定時間點T上下各浮動5 min.

表1 實驗參數(shù)設(shè)置Tab.1 Parameter settings

本文默認(rèn)數(shù)據(jù)集為紐約市路網(wǎng)NY,NY中移動對象數(shù)量默認(rèn)為10 000.本文從紐約路網(wǎng)中抽取三個子網(wǎng)NY1,NY2,NY3作為不同的數(shù)據(jù)集,子網(wǎng)點和邊的數(shù)量如表2所示.在不同數(shù)據(jù)集的實驗中,移動對象默認(rèn)數(shù)量不同,數(shù)據(jù)集NY1中,默認(rèn)為1 250個,NY2中,默認(rèn)為2 500,NY3中,默認(rèn)為5 000.

表2 實驗數(shù)據(jù)集Tab.2 Datasets

4.3 結(jié)果分析

本文分別對TIGR和TIGR_P查詢算法進行實驗,用來比較在使用不同的最快路徑查詢算法時,TIGR與TIGE_P算法的查詢效率.本文將最快路徑查詢算法TD-Dijkstra[16]與本文的查詢框架結(jié)合,作為本文的對比實驗.其中使用TD-G-tree的算法分別表示為TIGR（G）和TIGR_P（G）,使用TD-Dijkstra的算法分別表示為TIGR（D）和TIGR_P（D）.每組查詢在路網(wǎng)中隨機選取1 000個查詢點,并且在[0,1 440]內(nèi)隨機選取一個時間點作為查詢時間,將1 000次查詢的平均時間展示在實驗圖中.

（1）k值.由圖3可以看出,在使用TD-G-tree和TD-Dijkstra進行查詢時,TIGR_P算法的查詢效率均比TIGR提升一個數(shù)量級左右,甚至使用了剪枝策略的TIGR_P（D）的查詢時間要比沒有使用剪枝策略的TIGR（G）還要短,體現(xiàn)了本文所提剪枝策略的高效性.另外,兩種算法的查詢時間都隨著k值的增大而增加,這是由于k值越大,查詢范圍越大,需要訪問的移動對象數(shù)量也隨之增加.但由于時間上限的限制,當(dāng)k值較大時,位置在時間上限對應(yīng)的網(wǎng)格范圍之外的移動對象不需要被訪問,查詢時間增速相對變緩.

圖3 k值對查詢效率的影響Fig.3 Query efficiency vary k

（2）移動對象數(shù)量|M|.由圖4可以看出,隨著移動對象數(shù)量的增加,使用TD-G-tree的查詢算法的查詢時間逐漸變短.這是由于隨著移動對象數(shù)量的增多,其在路網(wǎng)中的密度也隨之增大,在k值不變情況下,查詢所需擴展的空間范圍越小,查詢時間越短.相反,使用TD-Dijkstra的兩種算法的查詢時間都隨著移動對象數(shù)量的增多而增加,這是由于TD-Dijkstra使用在線擴展的方式進行最快路徑查詢,計算代價較大,當(dāng)移動對象數(shù)量越多,進行的計算次數(shù)越多時,查詢時間就會越長.但總體來看,TIGR_P算法的查詢效率仍比TIGR算法提高了1~2個數(shù)量級.

圖4 |M|對查詢效率的影響Fig.4 Query efficiency vary|M|

（3）網(wǎng)格寬度L.由圖5可以看出,使用TD-G-tree和TD-Dijkstra進行查詢時,網(wǎng)格大小對兩種算法的查詢效率影響都較小,這是由于在網(wǎng)格較大時,需訪問的網(wǎng)格數(shù)量雖然較少,但每個網(wǎng)格中移動對象數(shù)量較多,而網(wǎng)格較小時則相反,因此總體查詢響應(yīng)時間變化不大.

圖5 L對查詢效率的影響Fig.5 Query efficiency vary L

（4）數(shù)據(jù)集Dataset.由圖6可以看出,兩種算法的查詢時間都隨著數(shù)據(jù)集的增大而增大.這是因為在移動對象密度不變的前提下,數(shù)據(jù)集的增大會導(dǎo)致查詢范圍的擴大.而對于TIGR_P,剪枝策略的使用會相對縮小查詢范圍,所以查詢時間的增加相對平緩.值得注意的是,使用TD-Dijkstra的查詢算法受數(shù)據(jù)集的影響更大,這是由于在數(shù)據(jù)集變大導(dǎo)致查詢范圍變大時,利用TD-Dijksrta作為查詢過程中的最快路徑查詢時,查詢效率會明顯變低.

圖6 Dataset對查詢效率的影響Fig.6 Query efficiency vary Dataset

（5）比例θ.由圖7可以看出,對于TIGR_P,隨著被占用對象比例的增加,使用TD-G-tree和TDDijkstra的查詢算法的都隨之增大.相反,TIGR的查詢時間是隨著被占用對象比例的增加而減小.這是由于,根據(jù)定義3,未被占用對象能夠提供的最小空車時間是T1,但由于被占用對象存在從當(dāng)前位置到目的地的時間代價,所以往往能夠提供小于T1的空車時間,從而更快的滿足算法終止條件,使查詢范圍減小,查詢效率提高.但是由于剪枝策略3的存在,減小了未被占用對象對查詢效率的影響,所以使用了剪枝策略的TIGR_P能夠讓查詢效率受查詢環(huán)境的影響更小,更穩(wěn)定.

圖7 θ對查詢效率的影響Fig.7 Query efficiency vary θ

（6）時間范圍γ.由圖8可以看出,使用TD-G-tree和TD-Dijkstra的查詢算法的查詢時間都隨著時間點的增大而增大.這是因為隨著時間點的提高,距離查詢點較近的移動對象提供的空車時間會更長,為了獲得空車時間更短的移動對象,查詢范圍會隨之?dāng)U大.

圖8 γ對查詢效率的影響Fig.8 Query efficiency vary γ

5 小結(jié)

與傳統(tǒng)的kNN查詢相比,帶有到達時間限制的k近鄰查詢更具有現(xiàn)實意義.本文提出了一種TIGR算法,首先利用基于網(wǎng)格索引的框架結(jié)構(gòu)確定移動對象的候選集,再計算候選集中移動對象到達查詢點的具體時間代價和空車時間,并提出了基于剪枝策略的TIGR_P查詢算法.實驗結(jié)果表明,所提的TIGR_P算法能夠高效的實現(xiàn)查詢,比TIGR算法執(zhí)行速度快一個數(shù)量級左右.下一步工作中,我們將考慮進一步縮小搜索范圍,增強剪枝效果,提高查詢效率.