時(shí)間依賴路網(wǎng)中限制到達(dá)時(shí)間的k近鄰查詢

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

2 問題定義

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

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

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

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

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

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

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

3 查詢算法

3.1 TIGR算法

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

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

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

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

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

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

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

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

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

算法1:TIGR算法輸入:路網(wǎng)G=（V,E,F,T）、查詢點(diǎn)q、網(wǎng)格索引L、查詢時(shí)間t、時(shí)間間隔[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算法中,部分移動(dòng)對(duì)象在任意查詢時(shí)間下的時(shí)間代價(jià)均大于時(shí)間上限.還存在時(shí)間代價(jià)過大的被占用對(duì)象和空車時(shí)間過大的未被占用對(duì)象,為了避免對(duì)此類移動(dòng)對(duì)象的訪問,本節(jié)提出了三種剪枝策略以及TIGR_P算法,對(duì)TIGR算法的查詢效率進(jìn)行改進(jìn).在介紹算法之前,先給出一些相關(guān)定義,然后詳細(xì)介紹三種剪枝策略.

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

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

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

策略1.下界圖剪枝.根據(jù)定義5可以得到,如果利用下界圖得到某一個(gè)移動(dòng)對(duì)象oa到達(dá)查詢點(diǎn)q的時(shí)間代價(jià)下界LBC（oa,q）大于移動(dòng)對(duì)象ob到達(dá)查詢點(diǎn)的真實(shí)時(shí)間代價(jià),那么在任意查詢時(shí)間,oa到達(dá)q的真實(shí)時(shí)間代價(jià)都會(huì)大于ob到達(dá)查詢點(diǎn)的真實(shí)時(shí)間代價(jià).

證明1：給定兩個(gè)移動(dòng)對(duì)象oa和ob,查詢時(shí)間t和查詢點(diǎn)q,如果LBC（oa,q）＞TFTC（ob,q,t）,那么對(duì)于任意的t∈[0,T],有

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

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

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

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

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

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

證明3：由公式3可知,對(duì)于未被占用對(duì)象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個(gè)移動(dòng)對(duì)象到達(dá)查詢點(diǎn)的空車時(shí)間Tk是否小于時(shí)間下限T1,如果滿足條件,則停止對(duì)未被占用對(duì)象的訪問.在算法1的第14-16行,需要計(jì)算網(wǎng)格中每個(gè)移動(dòng)對(duì)象到查詢點(diǎn)的具體時(shí)間代價(jià)和空車時(shí)間之前,使用剪枝策略1和2,先計(jì)算每一個(gè)移動(dòng)對(duì)象到達(dá)查詢點(diǎn)的時(shí)間代價(jià)下界,如果時(shí)間代價(jià)下界大于時(shí)間上限T2,則該移動(dòng)對(duì)象被剪枝.同時(shí)對(duì)于每一個(gè)被占用對(duì)象,判斷td是否大于時(shí)間上限T2,如果滿足條件,則該被占用對(duì)象被剪枝.

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

4.1 實(shí)驗(yàn)條件

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

4.2 實(shí)驗(yàn)數(shù)據(jù)

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

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

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

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

表2 實(shí)驗(yàn)數(shù)據(jù)集Tab.2 Datasets

4.3 結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

5 小結(jié)

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