基于時(shí)間感知的動(dòng)態(tài)組旅行查詢

李艷紅，歐昱宏，毛德權(quán)，龐栩

（1 中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢 430074；2 重慶市公安局 渝北區(qū)分局，重慶 401120）

1 問題的引入

隨著智能移動(dòng)終端的應(yīng)用，以及地理位置與文本數(shù)據(jù)的融合，大量的空間文本對(duì)象應(yīng)運(yùn)而生，但僅考慮空間文本相似度的空間關(guān)鍵詞查詢有時(shí)無(wú)法滿足成員的特殊需求.例如一組成員在晚上10點(diǎn)想要查詢一家能同時(shí)供應(yīng)中餐和西餐的餐廳，但大部分餐廳此時(shí)已經(jīng)暫停營(yíng)業(yè)，若仍用傳統(tǒng)的查詢算法，返回的結(jié)果很可能不是成員所需要的.

如今，為分散在各地的人們規(guī)劃出最佳行程，不僅包括成員所需訪問的不同類型興趣點(diǎn)的查詢，也要基于滿足約束的興趣點(diǎn)規(guī)劃出最優(yōu)路徑.例如，圖1顯示了一個(gè)Euclidean空間中的TDGTP（Time Dynamic Group Travel Planning）查詢，其中 3 個(gè)成員u1、u2和u3的起始位置和目標(biāo)位置分別為（s1，d1）、（s2，d2）、（s3，d3）.成員 u2和u3需要找到一家能同時(shí)滿足牛排和漢堡這兩個(gè)關(guān)鍵詞的餐館，然后成員u1與他們?cè)谝魳窂d碰面去聽音樂（藍(lán)線所示），聽完音樂后成員u3直接回到家中（綠線所示），其余成員則去書店買書，最后回到各自的家中.通常會(huì)遇到滿足關(guān)鍵詞要求的興趣點(diǎn)鄰近小組中的某位成員，但距離組內(nèi)其他成員較遠(yuǎn)的情況，此時(shí)該行程規(guī)劃可能不是最佳路徑.為此，希望找到滿足該組成員要求且總行程距離最小的最佳路徑，其中總行程距離是組中所有成員的行程距離之和，每個(gè)成員的行程從起始位置開始，然后訪問滿足要求的興趣點(diǎn)，最終到達(dá)目標(biāo)位置，結(jié)束行程.

圖1 一個(gè)TDGTP場(chǎng)景Fig.1 A TDGTP scene

當(dāng)前研究人員并未考慮行程規(guī)劃中新成員加入或已有成員離開的問題，也沒有在行程規(guī)劃中考慮興趣點(diǎn)與查詢需求的時(shí)間匹配問題.因此，本文提出了一個(gè)新問題——時(shí)間感知的動(dòng)態(tài)組旅行規(guī)劃查詢（TDGTP）問題.上述示例中有待解決的問題有：

（1）在興趣點(diǎn)數(shù)量龐大的空間中，如何修剪掉不滿足要求的興趣點(diǎn)，快速找出符合所有成員要求的興趣點(diǎn)區(qū)域？

（2）對(duì)于一組成員的旅行規(guī)劃，怎樣才能找出符合所有成員要求的興趣點(diǎn)？

（3）如何使該行程的總距離達(dá)到最小，返回一個(gè)最佳路徑序列？

為應(yīng)對(duì)上述難題，本文提出以下解決方案：首先將R-Tree 與倒排文本列表和時(shí)間文本列表結(jié)合，構(gòu)建了TIR-Tree 索引結(jié)構(gòu)及相關(guān)算法KMA（Keyword Matching Algorithm）對(duì)興趣點(diǎn)進(jìn)行索引；然后，依據(jù)“橢圓上的點(diǎn)到兩焦點(diǎn)的距離之和小于橢圓外的點(diǎn)到兩焦點(diǎn)的距離之和”的性質(zhì)，設(shè)計(jì)了ESRA（Elliptic Search Refinement Algorithm）算法將空間數(shù)據(jù)集的搜索區(qū)域剪枝細(xì)化；最后，提出BestTD（Best Time Dynamic）算 法來(lái)解決 TDGTP問題.

綜上所述，本文主要貢獻(xiàn)如下：

（1）正式定義并研究了時(shí)間感知的動(dòng)態(tài)組旅行規(guī)劃查詢（TDGTP）問題；

（2）設(shè)計(jì)了一種有效的綜合索引結(jié)構(gòu)，稱為TIR-Tree，提出了基于時(shí)間和關(guān)鍵詞的剪枝來(lái)高效、快速地查找相應(yīng)的興趣點(diǎn)；

（3）對(duì)于大規(guī)模的興趣點(diǎn)集，開發(fā)了一種基于橢圓區(qū)域的剪枝，利用橢圓性質(zhì)，設(shè)計(jì)了ESRA（Elliptic Search Refinement Algorithm）算法來(lái)對(duì)空間數(shù)據(jù)集剪枝，從而減少檢索數(shù)據(jù)集的數(shù)量.

2 相關(guān)工作

文獻(xiàn)［1］討論了空間數(shù)據(jù)庫(kù)中的一種新型行程規(guī)劃查詢（TPQ），研究了度量空間中TPQ 的快速近似算法.文獻(xiàn)［2］首次引入團(tuán)體旅行計(jì)劃（GTP）查詢的概念并針對(duì)Euclidean 空間做了介紹，將kGTP 定義為：如果一個(gè)組查詢一個(gè)GTP 的k組數(shù)據(jù)點(diǎn)，則該查詢稱為k 組旅行計(jì)劃（kGTP）查詢.文獻(xiàn)［3］將POI搜索區(qū)域細(xì)化為橢圓區(qū)域，計(jì)算組中每個(gè)成員形成的橢圓區(qū)域，其中每個(gè)橢圓的焦點(diǎn)位于相應(yīng)成員的源位置和目標(biāo)位置上.文獻(xiàn)［4］研究了道路網(wǎng)絡(luò)中的組最優(yōu)排序路線（GOSR）查詢問題，指出在Euclidean 空間中提出的GTP 算法會(huì)產(chǎn)生非常高的查詢處理開銷，且不能擴(kuò)展到道路網(wǎng)中.

文獻(xiàn)［5］為克服固定團(tuán)隊(duì)規(guī)模的限制，提出了NaiveDGTP算法和FastDGTP算法來(lái)處理DGTPQ，但這兩種方法在道路網(wǎng)上并不適用.文獻(xiàn)［6］提出了DGTP 算法和M-DGTP 算法來(lái)解決道路網(wǎng)上的小組規(guī)劃問題，相比之下，M-DGTP 算法處理的時(shí)間較快，內(nèi)存開銷較小，但該算法需要依次訪問道路網(wǎng)上的興趣點(diǎn)，處理的數(shù)據(jù)對(duì)象多且時(shí)間長(zhǎng).文獻(xiàn)［7-8］研究了空間數(shù)據(jù)庫(kù)中的序列團(tuán)體旅行計(jì)劃查詢（SGTPQ）問題，對(duì)于不同的團(tuán)體規(guī)模和查詢區(qū)域，所提出的PGNE算法響應(yīng)時(shí)間較短，內(nèi)存開銷較少.

文獻(xiàn)［9］提出了基于方向感知的空間關(guān)鍵詞搜索，它以空間點(diǎn)、方向和一組關(guān)鍵詞為參數(shù)，找到查詢的k 個(gè)最近鄰居，每個(gè)鄰居都位于搜索方向上且包含所有查詢關(guān)鍵詞.文獻(xiàn)［10］提出了時(shí)間感知布爾空間關(guān)鍵詞查詢（TABSKQ），設(shè)計(jì)了一種高效的混合索引結(jié)構(gòu)TA-tree 及相關(guān)算法來(lái)處理TABSKQ.文獻(xiàn)［11］提出了道路網(wǎng)絡(luò)上的時(shí)間感知空間關(guān)鍵詞查詢（TSK）問題，設(shè)計(jì)了一種高效索引結(jié)構(gòu)TG 及基于TG 索引的有效算法.文獻(xiàn)［12］提出了時(shí)間感知空間關(guān)鍵詞覆蓋查詢（TSKCQ），設(shè)計(jì)了PQA 算法去評(píng)估成員在時(shí)間和空間上的滿意度，并返回具有最佳成本函數(shù)的對(duì)象值.

文獻(xiàn)［13］首次探討了在查詢位置與空間對(duì)象之間的距離最短路徑道路網(wǎng)絡(luò)上處理top-k 空間關(guān)鍵詞查詢問題.文獻(xiàn)［14］研究了最接近關(guān)鍵詞搜索的最佳覆蓋，提出的keyword-NNE 算法能減少生成的候選關(guān)鍵詞覆蓋數(shù)量.文獻(xiàn)［15］引入了一種新穎的空間關(guān)鍵詞覆蓋（SK-COVER）問題，建立了一個(gè)O（log m）近似算法，設(shè)計(jì)了有效的訪問策略和修剪規(guī)則，以提高整體效率和可擴(kuò)展性.

3 問題描述

3.1 興趣點(diǎn)

假設(shè)在數(shù)據(jù)空間有一組時(shí)空文本對(duì)象o∈O，每個(gè)對(duì)象 o 定義為（id，doc，t），其中 o.id 是對(duì)象 o 的唯一標(biāo)識(shí)，o.doc是一組用來(lái)描述對(duì)象o的關(guān)鍵詞集合，其形式為 o.doc=｛（o.key1），（o.key2），…，（o.keyi）｝，o.t表示對(duì)象o的有效時(shí)間，形式為（st，et）其中st和et分別為對(duì)象o的起始時(shí)間和結(jié)束時(shí)間.其中，將o.t進(jìn)行整數(shù)化，以一個(gè)小時(shí)為單位.例如，購(gòu)物中心的有效時(shí)間是（09：00-12：00），（09：00-12：00）中的任何時(shí)間戳都可以轉(zhuǎn)化為單位時(shí)間（9，12）.表1 列出的是本文中出現(xiàn)的符號(hào)及其定義.表2是對(duì)象信息.

表1 符號(hào)與定義Tab.1 Symbols and definitions

表2 對(duì)象信息Tab.2 Object information

3.2 時(shí)間感知的動(dòng)態(tài)組旅行規(guī)劃查詢

已知數(shù)據(jù)集O和一個(gè)時(shí)間感知的動(dòng)態(tài)組旅行規(guī)劃（TDGTP）查詢q=（U，S，D，P，T），其中U=｛u1，u2，…，un｝表示小組成員集合，S=｛s1，s2，…，sn｝是每個(gè)成員ui的起始位置集合，D=｛d1，d2，…，dn｝是目標(biāo)位置集合.P 是一組關(guān)鍵詞集合，表示成員查詢目的.T 是成員指定的任意查詢時(shí)間區(qū)間如（9，12）.查詢q 返回一條各個(gè)成員從S 出發(fā)、到D 結(jié)束且符合q.P 和q.T約束條件的最佳路徑.

接下來(lái)是搜索區(qū)域邊界的計(jì)算.橢圓焦點(diǎn)的公式如下：

其中 si是成員 ui的起點(diǎn)，di是成員 ui的終點(diǎn)，n 為組成員數(shù)量.

橢圓主軸范圍為：

其中n 是小組成員數(shù)量，總行程距離是所有成員的行程距離之和.

4 索引結(jié)構(gòu)TIR-Tree

R-tree 是目前最流行的空間索引結(jié)構(gòu)之一，它運(yùn)用了空間分割理念，用作空間數(shù)據(jù)存儲(chǔ)的樹狀數(shù)據(jù)結(jié)構(gòu).倒排索引是實(shí)現(xiàn)“單詞-文檔矩陣”的一種具體存儲(chǔ)形式，是常用的文本索引結(jié)構(gòu)之一，通過倒排索引，可以根據(jù)單詞快速獲取包含這個(gè)單詞的文檔列表.傳統(tǒng)的空間查詢和關(guān)鍵詞搜索使用不同的索引技術(shù)和查詢算法耗時(shí)又費(fèi)力，為有效地處理TDGTP 問題，本文將R-tree 上的每個(gè)非葉子結(jié)點(diǎn)關(guān)聯(lián)上兩個(gè)倒排文件，在查詢包含空間文本信息的文件時(shí)擁有較高的效率，這種混合數(shù)據(jù)結(jié)構(gòu)被稱為TIR-Tree索引.

在二維空間中，對(duì)于不規(guī)則幾何圖形通常采用最小邊界矩形MBR 來(lái)構(gòu)建索引.本文采用MBR 的方法，從葉子結(jié)點(diǎn)開始用MBR 將空間框起來(lái)，結(jié)點(diǎn)越往上，框住的空間就越大，從而實(shí)現(xiàn)對(duì)空間的分割，如圖2所示：首先假設(shè)所有數(shù)據(jù)對(duì)象的位置都是二維空間下的點(diǎn)，圖中標(biāo)識(shí)了R6區(qū)域中的數(shù)據(jù)，將它看作是多個(gè)數(shù)據(jù)圍成的一個(gè)區(qū)域，為了實(shí)現(xiàn)R樹，用一個(gè)MBR 框住形成區(qū)域R6.采用同樣的方法，一共得到了4 個(gè)最基本的MBR，這些MBR 被存儲(chǔ)在非葉子結(jié)點(diǎn)中.下一步是進(jìn)行高一層的處理，此時(shí)的R3和R4這兩個(gè)矩形距離最為靠近，因此可用一個(gè)更大的矩形R1恰好框住這兩個(gè)矩形，同樣，R5和R6恰好被R2框住.所有最基本的MBR被框入更大的矩形中后，再次迭代，用更大的框框住這些矩形.

圖2 TIR-Tree的劃分Fig.2 Division of TIR-Tree

TIR-Tree 整體結(jié)構(gòu)如圖 3 所示 .TIR-Tree 以 R 樹的形式構(gòu)建，從空樹開始，不斷插入劃分的MBR，直到生成一棵完整的R 樹.每個(gè)非葉子結(jié)點(diǎn)用四元組（ra，rectangle，ra.di，ra.ti）表示，其中 ra 存儲(chǔ)的是子節(jié)點(diǎn)地址，rectangle 是覆蓋所有子結(jié)點(diǎn)的MBR 的最小矩形，ra.di 是關(guān)鍵詞描述標(biāo)識(shí)符，連接關(guān)鍵詞倒排文件列表，其中第一列為關(guān)鍵詞信息，第二列為包含對(duì)應(yīng)關(guān)鍵詞信息的子結(jié)點(diǎn)的MBR.ra.ti 是有效時(shí)間信息的標(biāo)識(shí)符，連接有效時(shí)間的倒排文件，其中第一列為有效時(shí)間信息，第二列為包含對(duì)應(yīng)時(shí)間信息的MBR.每個(gè)葉子結(jié)點(diǎn)包含許多形式為（o，o.rec，o.di，o.ti）的條目，其中o是數(shù)據(jù)空間的對(duì)象，o.rec是對(duì)象o 的邊界矩形，o.di 是對(duì)象o 的關(guān)鍵詞標(biāo)識(shí)符，o.ti是對(duì)象o有效時(shí)間的標(biāo)識(shí)符.

圖3 TIR-Tree綜合索引結(jié)構(gòu)Fig.3 TIR-Tree comprehensive index structure

5 查詢處理算法

這里首先提出基于TIR-Tree 的剪枝策略，然后介紹ESRA細(xì)化搜索空間算法和解決TDGTP查詢處理的BestTD算法.

5.1 基于TIR-Tree的剪枝策略

5.1.1 基于TIR-Tree的剪枝

引理1 已知一個(gè)TDGTP 查詢q=（U，S，D，P，T）和一個(gè)區(qū)域Ei，如果q.P ∩ Ei.P=?，則區(qū)域Ei可以被安全地削減.

證明 已知查詢的關(guān)鍵詞集合為q.P，區(qū)域Ei內(nèi)所有對(duì)象關(guān)鍵詞的并集為Ei.P.若q.P 與Ei的交集不為空，表示區(qū)域Ei內(nèi)有滿足查詢關(guān)鍵詞要求的對(duì)象；反之，區(qū)域Ei內(nèi)的對(duì)象都不滿足要求，可以被剪枝.

引理2 已知一個(gè)TDGTP 查詢q =（U，S，D，P，T）和一個(gè)區(qū)域Ei，如果q.T ∩ Ei.T= ?，則區(qū)域Ei可以被安全地削減.

證明 已知查詢q 的時(shí)間信息為q.T，區(qū)域Ei內(nèi)所有對(duì)象營(yíng)業(yè)時(shí)間的最大區(qū)間為Ei.T.若q.T 與Ei.T的交集不為空，表示區(qū)域Ei內(nèi)有滿足查詢時(shí)間要求的對(duì)象；反之，區(qū)域Ei內(nèi)的對(duì)象的營(yíng)業(yè)時(shí)間都在查詢給定的時(shí)間之外，可以被剪枝.

5.1.2 基于TIR-Tree的剪枝算法KMA

基于TIR-Tree 的剪枝算法KMA 具體流程見算法 1，初始化隊(duì)列 Qinit、集合 Ponec和指針 TNode，其中Qinit用來(lái)存放候選結(jié)點(diǎn)，Ponec用來(lái)保存所有符合約束的興趣點(diǎn)集合（第1行）.將TIR-tree的根結(jié)點(diǎn)放入隊(duì)列Qinit（第2 行）.當(dāng)隊(duì)列Qinit不為空，則從根結(jié)點(diǎn)自上而下地進(jìn)行處理，遍歷根結(jié)點(diǎn)的子結(jié)點(diǎn).首先TNode指向隊(duì)列Qinit的頭元素，判斷TNode是否滿足查詢關(guān)鍵詞和時(shí)間約束；若滿足，繼續(xù)判斷TNode是否為非葉子結(jié)點(diǎn)，若是，則將該結(jié)點(diǎn)的子結(jié)點(diǎn)存入隊(duì)列Qinit，否則將該結(jié)點(diǎn)存入集合Ponec（第2-9 行）.遍歷完成后，返回集合Ponec（第10行）.

images/BZ_114_1284_1524_2243_1581.png輸入：一個(gè)TDGTP查詢q=（U，S，D，P，T），關(guān)于數(shù)據(jù)集O的TIR-Tree輸出：滿足空間關(guān)鍵詞要求的興趣點(diǎn)集Ponec 1 Ponec=?；Qinit=?；TNode=? 2 將TIR-Tree樹的根結(jié)點(diǎn)R0放入隊(duì)列Qinit 3 while Qini≠t? do 4 TNode=Qinit.pop（）5 if TNode的關(guān)鍵詞∩q.P and TNode的時(shí)間∩q.T then 6 if TNode是非葉子結(jié)點(diǎn)then 7 Qinit.Push（TNode.children）8 else 9 Ponec ←TNode 10 Return Ponec

5.2 基于搜索區(qū)域的剪枝

5.2.1 搜索空間的剪枝

已知一個(gè)TDGTP 查詢q=（U，S，D，P，T）和一個(gè)數(shù)據(jù)集搜索空間，將搜索空間從整個(gè)搜索區(qū)域減小到TDGTP 查詢區(qū)域.為了計(jì)算搜索區(qū)域的邊界，需計(jì)算一組橢圓區(qū)域集.首先根據(jù)公式（1）、（2）計(jì)算初始成員（此時(shí)尚未加入的成員）的起始位置和目標(biāo)位置的質(zhì)心，即橢圓焦點(diǎn)，主軸為Tdist，形成E1橢圓；然后分別計(jì)算在某個(gè)興趣點(diǎn)新加入成員的起始位置和目標(biāo)位置的質(zhì)心，形成Ei橢圓；最后區(qū)域?yàn)樗袡E圓的交集，見圖4.

圖4 搜索區(qū)域的細(xì)化Fig.4 The refinement of search area

圖 4 中，U =｛u1，u2，u3，u4，u5｝，小組成員的起始位置為 S=｛s1，s2，s3，s4，s5｝，目標(biāo)位置為 D=｛d1，d2，d3，d4，d5｝.u1和 u3是初始成員，u4和 u5是在第 1 個(gè)興趣點(diǎn)加入的成員，u2是在第2 個(gè)興趣點(diǎn)加入的成員.第11 個(gè)橢圓區(qū)域E1；然后計(jì)算第2 個(gè)橢圓焦點(diǎn)Cs2=計(jì)算第3 個(gè)橢圓焦點(diǎn)，因?yàn)榈? 輪加入的成員只有u2，所以第3個(gè)橢圓的焦點(diǎn)就是s2和d2，形成第3個(gè)橢圓區(qū)域E3.R是3個(gè)橢圓E1，E2，E3的交集區(qū)域.

5.2.2 搜索區(qū)域ESRA算法

橢圓剪枝算法見算法2.兩個(gè)隊(duì)列Scand，Dcand以及3個(gè)集合cvs，cvd，Cur初始化為空，集合Ptwoc初始為O.其中，Scand用來(lái)存放成員起點(diǎn)，Dcand用來(lái)存放成員目標(biāo)點(diǎn)，Ptwoc用來(lái)存放橢圓交集內(nèi)的興趣點(diǎn)，cvs 和cvd分別保存計(jì)算的橢圓焦點(diǎn)（第1 行）.將每輪加入行程的成員起點(diǎn)和終點(diǎn)存入Scand，Dcand（第2行）.當(dāng)兩個(gè)隊(duì)列不為空時(shí)，根據(jù)公式（1）、（2）計(jì)算每一輪次的幾何質(zhì)點(diǎn)，分別存放在cvs 和cvd 中，然后使用FindElliptic 函數(shù)形成橢圓區(qū)域，并將該區(qū)域內(nèi)的興趣點(diǎn)存入Cur，Ptwoc存放所有橢圓交集區(qū)域的興趣點(diǎn)（第3-9行）；最后返回集合Ponec（第10行）.

images/BZ_115_242_2303_1201_2360.png輸入：S=｛s1，s2，…，si｝，D=｛d1，d2，…，di｝，O=｛o1，o2，…，oi｝輸出：輸出細(xì)化區(qū)域范圍的興趣點(diǎn)集Ptwoc 1 Ptwoc =O ；cvs=? ；cvd=? ；Scand=? ；Dcand=? ；Cur=? 2 將S、D按照加入行程的順序排列分別存入Scand，Dcand 3 while Scand ≠? and Dcand ≠? do 4 Cens=Scand.pop（）5 Cend=Dcand.pop（）6 cvs←按照公式（1）計(jì)算Cs 7 cvd←按照公式（2）計(jì)算Cd 8 Cur ←將 FindElliptic（cvs，cvd，Tdist）內(nèi)的興趣點(diǎn)9 Ptwoc=Ptwoc ∩Cur 10 Return Ptwoc

5.3 基于時(shí)間感知的動(dòng)態(tài)組旅行規(guī)劃BestTD算法

前兩小節(jié)討論的基本算法分別返回滿足約束條件的興趣點(diǎn)集，在此基礎(chǔ)上，將興趣點(diǎn)按照關(guān)鍵詞排序，得到所有的候選路徑，然后對(duì)候選路徑序列進(jìn)行遍歷，根據(jù)公式（4）、（5）計(jì)算候選路徑的距離，從而獲得總行程距離最小的最優(yōu)路徑.

查詢算法見算法3.首先初始化3 個(gè)集合PT，LTcand和 LT 及一個(gè)隊(duì)列 PTcand，Lmin被初始化為∞，（PT用來(lái)存放算法1 和算法2 剪枝后的興趣點(diǎn)，PTcand用來(lái)存放排列后的候選路徑，LTcand用來(lái)保存隊(duì)列PTcand出隊(duì)元素，LT 存放篩選后的最優(yōu)路徑）（第1行）.調(diào)用KMA 算法和ESRA 算法，將返回的集合交集存放在PT，并將PT 中的興趣點(diǎn)按照關(guān)鍵詞排列的候選路徑存入 PTcand（第 2-3 行）.當(dāng) PTcand不為空時(shí)，遍歷每條候選路徑，根據(jù)公式（4）和（5）計(jì)算出每條候選路徑的總行程距離TD，將TD 與Lmin比較，若TD 小于Lmin，此時(shí)的候選路徑存入LT，最小總距離行程的值賦值給Lmin（第4-12 行）.最后返回路徑LT（第13行）.

images/BZ_115_1284_1478_2243_1535.png輸入：一個(gè)TDGTP查詢q=（U，S，D，P，T），關(guān)于數(shù)據(jù)集O的TIRTree，O=｛o1，o2，…，oi｝輸出：最優(yōu)路徑LT 1 PT = ?；PTcand = ?；LT= ?；Lmin= ∞；LTcand= ? 2 PT←KMA（q，O）∩ ESRA（S，D，O）3 將PT中的興趣點(diǎn)o按照q.P的順序排列并插入PTcand 4 while PTcand ≠? do 5 LTcand =PTcand.pop（）6 n←|U|7 按照公式（4）計(jì)算PD 8 按照公式（5）計(jì)算TD 9 if TD ＜Lmin then 10 LT=LTcand 11 Lmin=TD 12 end if 13 查詢結(jié)束，返回LT

算法復(fù)雜度分析：根據(jù)算法1，在整個(gè)搜索空間內(nèi)，假設(shè)關(guān)鍵詞的總和為Nk，查詢關(guān)鍵詞數(shù)量為|q.P|，每個(gè)興趣點(diǎn)平均分配Ki個(gè)關(guān)鍵詞，此時(shí)獲得滿足2 是返回橢圓交集區(qū)域內(nèi)的興趣點(diǎn)，此時(shí)滿足關(guān)鍵算法2 的基礎(chǔ)上，算法3 檢索到在橢圓交集區(qū)域內(nèi)滿足關(guān)鍵詞和時(shí)間約束條件的興趣點(diǎn)，綜上所述，令空間對(duì)象總數(shù)為|O|，則滿足條件的對(duì)象總數(shù)為

算法3 中，若不采用剪枝策略，此時(shí)執(zhí)行次數(shù)m為|O|，則算法3 的最壞時(shí)間復(fù)雜度為O（|O|）；當(dāng)剪枝|O|，while 內(nèi)的語(yǔ)句會(huì)隨著問題規(guī)模m 的增加呈線性

6 實(shí)驗(yàn)案例

6.1 實(shí)驗(yàn)設(shè)置

本文以路網(wǎng)數(shù)據(jù)集的結(jié)點(diǎn)位置作為興趣點(diǎn)對(duì)象位置，使用2 個(gè)真實(shí)的路網(wǎng)數(shù)據(jù)集——美國(guó)California和德國(guó)Oldenburg真實(shí)路網(wǎng)數(shù)據(jù)在Euclidean空間評(píng)估算法，如表3所示.CA 路網(wǎng)有21048個(gè)結(jié)點(diǎn)和21693 條邊.使用Zipfian 分布為每個(gè)對(duì)象分配2-3 個(gè)關(guān)鍵詞，每個(gè)關(guān)鍵詞中的平均、最大和最小對(duì)象數(shù)分別為 319、3024 和 123.OL 路網(wǎng)包含 6105 個(gè)結(jié)點(diǎn)和7305條邊，使用Zipfian 分布為每個(gè)對(duì)象分配2-3 個(gè)關(guān)鍵詞，每個(gè)關(guān)鍵詞中的平均、最大和最小對(duì)象數(shù)分別為103、887 和33.

表3 實(shí)驗(yàn)數(shù)據(jù)集Tab.3 Experiment datasets

本實(shí)驗(yàn)將其數(shù)據(jù)空間歸化成一個(gè)1000×1000平方單位面積，使用TIR-Tree結(jié)構(gòu)來(lái)索引數(shù)據(jù)對(duì)象.對(duì)3 個(gè)參數(shù)（如表4 所示）進(jìn)行設(shè)置：成員數(shù)量n、查詢關(guān)鍵詞個(gè)數(shù)m 以及橢圓長(zhǎng)軸的大小Tdist.本次實(shí)驗(yàn)設(shè)備為Intel Core i5-5200U，2.20 GHz CPU，8.00 GB RAM Windows 10 的計(jì)算機(jī)，所有算法在Java 1.8.0_191的運(yùn)行環(huán)境下完成.

表4 參數(shù)設(shè)置Tab.4 Parameters setting

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

本節(jié)將展示 BestTD 算法與 TABASSUM 等人［5］提出的NaiveDGTP 算法處理TDGTP 查詢的性能比較分析.

（1）數(shù)據(jù)集的影響.圖5（a）和5（b）分別顯示了兩種算法在CA 和OL 數(shù)據(jù)集下處理時(shí)間和內(nèi)存開銷.實(shí)驗(yàn)結(jié)果表明：不管是查詢時(shí)間還是內(nèi)存開銷，BestTD 算法都要優(yōu)于NaiveDGTP 算法.這是因?yàn)镹aiveDGTP 基于動(dòng)態(tài)規(guī)劃，隨著數(shù)據(jù)結(jié)點(diǎn)的增加，最短路徑和部分行程的計(jì)算量也在增加.

圖5 兩種算法在不同數(shù)據(jù)集下的性能Fig.5 Performance of the two algorithms in different datasets

（2）查詢關(guān)鍵詞m的影響.實(shí)驗(yàn)結(jié)果表明（圖6），兩種算法的查詢處理時(shí)間均隨查詢關(guān)鍵詞數(shù)量的增加而增加，但BestTD 算法的查詢處理時(shí)間遠(yuǎn)小于NaiveDGTP 算法.這是因?yàn)殡S著查詢關(guān)鍵詞個(gè)數(shù)的增加，查詢的搜索范圍變大，查詢處理對(duì)象的數(shù)量增加.但BestTD 算法相較于NaiveDGTP 算法效率要高，它能夠根據(jù)查詢關(guān)鍵詞更快地查詢到滿足條件的對(duì)象.因此，從圖6 可以看出，在查詢關(guān)鍵詞數(shù)量的影響下，BestTD 算法查詢性能優(yōu)于NaiveDGTP算法.

圖6 查詢關(guān)鍵詞的影響Fig.6 Impact of query keywords

（3）組大小n 的影響.圖7 顯示了組大小對(duì)兩種方法的影響，正如預(yù)想的那樣，BestTD和NavieDGTP兩種算法的查詢時(shí)間都隨著組大小的增加而增加.因?yàn)榻M大小的增加將導(dǎo)致更大量的路徑計(jì)算，從而導(dǎo)致處理時(shí)間變長(zhǎng).從結(jié)果中觀察到，BestTD 所需要的處理時(shí)間要比NavieDGTP少得多.

圖7 組大小的影響Fig.7 Impact of group size

（4）橢圓主軸大小Tdist的影響.圖8顯示了隨著橢圓主軸大小的增大，兩種方法的處理時(shí)間都有所增加.這是因?yàn)闄E圓主軸越大，搜索區(qū)域越大，查詢的數(shù)據(jù)集越多，從而處理的時(shí)間越長(zhǎng).實(shí)驗(yàn)中觀察到 ，BestTD 算 法 要 優(yōu) 于 NaiveDGTP 算 法 . 對(duì) 于NaiveDGTP 算法來(lái)說，它沒有任何修剪策略來(lái)減小搜索空間，而是使用整個(gè)數(shù)據(jù)空間來(lái)計(jì)算最佳團(tuán)體旅行，導(dǎo)致處理時(shí)間長(zhǎng)；而BestTD 算法采用了橢圓屬性細(xì)化搜索空間，所以其查詢處理時(shí)間要遠(yuǎn)遠(yuǎn)低于NaiveDGTP算法.

圖8 橢圓主軸大小的影響Fig.8 Impact of ellipse major axis

7 結(jié)語(yǔ)

本文研究了基于時(shí)間感知的動(dòng)態(tài)組旅行規(guī)劃查詢問題（TDGTP）.為快速定位到組成員需求的興趣點(diǎn)，構(gòu)建了一個(gè)綜合索引結(jié)構(gòu)TIR-Tree 并提出相關(guān)的關(guān)鍵詞查詢KMA 算法.此外，提出了一種基于橢圓剪枝方法（ESRA），細(xì)化搜索空間為橢圓交集區(qū)域.提出一種基于KMA 和ESRA 的查詢處理算法BestTD 來(lái)分析評(píng)估 TDGTP 問題 .通過對(duì) BestTD 與NaiveDGTP 算法在真實(shí)路網(wǎng)合成的數(shù)據(jù)集上進(jìn)行對(duì)比，證明本文所提方法是高效可行的.