共享交通的時(shí)空軌跡檢索與群體發(fā)現(xiàn)

段宗濤 龔學(xué)輝 唐蕾 陳柘

摘 要：為解決共享交通下的共乘用戶群體發(fā)現(xiàn)效率低、準(zhǔn)確率不高問(wèn)題，依據(jù)R-樹(shù)原理建立GeoOD-Tree索引，并在此基礎(chǔ)上提出以最大化共乘率為目標(biāo)的群體發(fā)現(xiàn)策略。首先，對(duì)原始時(shí)空軌跡數(shù)據(jù)進(jìn)行特征提取與標(biāo)定處理，挖掘有效出行起訖點(diǎn)（OD）軌跡;其次，針對(duì)用戶起訖點(diǎn)軌跡的特征，建立GeoOD-Tree索引進(jìn)行有效的存儲(chǔ)管理;最后，給出以最大化共乘行程為目標(biāo)的群體發(fā)現(xiàn)模型，并運(yùn)用K最近鄰（KNN）查詢對(duì)搜索空間剪枝壓縮，提高群體發(fā)現(xiàn)效率。采用西安市近12000輛出租車營(yíng)運(yùn)軌跡數(shù)據(jù)，選取動(dòng)態(tài)時(shí)間規(guī)整（DTW）等典型算法與所提算法在查詢效率與準(zhǔn)確率上進(jìn)行性能對(duì)比分析。與DTW算法相比，所提算法的準(zhǔn)確率提高了10.12%，查詢效率提高了20約15倍。實(shí)驗(yàn)結(jié)果表明提出的群體發(fā)現(xiàn)策略能有效提高共乘用戶群體發(fā)現(xiàn)的準(zhǔn)確率和效率，可有效提升共乘出行方式的出行率。

關(guān)鍵詞：共乘出行;群體發(fā)現(xiàn);時(shí)空軌跡;3維R樹(shù);起訖點(diǎn)

中圖分類號(hào)： TP301.6

文獻(xiàn)標(biāo)志碼：A

Abstract： Concerning low efficiency and accuracy of the ridesharing user group discovery in shared transportation environment， a GeoOD-Tree index was established based on R-tree principle， and a group discovery strategy to maximize the multiplying rate was proposed. Firstly， the feature extraction and calibration processing of original spatio-temporal trajectory data was carried out to mine effective Origin-Destination （OD） trajectory. Secondly， a data structure termed GeoOD-Tree was established for effective storage management of OD trajectory. Finally， a group discovery model aiming at maximizing ridesharing travel was proposed， and a pruning strategy using by K Nearest Neighbors （KNN） query was introduced to improve the efficiency of group discovery. The proposed method was evaluated with extensive experiments on a real dataset of 12000 taxis in Xian， in comparison experiments with Dynamic Time Warping （DTW） algorithm， the accuracy and efficiency of the proposed algorithm was increased by 10.12% and 1500%此處英文的描述，與中文描述的20倍不一致？ respectively. The experimental results show that the proposed group discovery strategy can effectively improve the accuracy and efficiency of ridesharing user group discovery， and it can effectively improve the rideshared travel rate.

Key words： ridesharing; group discovery; spatial-temporal trajectory; 3-Dimensional R-tree （3DR-tree）; Origin-Destination （OD）

0 引言

作為一類新興交通出行方式，共享交通的出現(xiàn)有助于緩解交通擁堵與道路磨損，減少空氣污染，降低對(duì)能源的依賴性[1]。通過(guò)充分利用交通運(yùn)輸資源來(lái)提供多種形式和廉價(jià)方便的共享服務(wù)，改變?nèi)藗儌鹘y(tǒng)的消費(fèi)觀念，變擁有汽車為使用服務(wù)。由于人類的社會(huì)群居特性，人們通常期望能夠與具有相同出行特征的用戶結(jié)伴出行[2]，例如通勤共乘者往往具有相同的出行活動(dòng)路徑[3]。正是這種優(yōu)于陌生乘客的潛在特征關(guān)聯(lián)，使得乘客們?cè)谙硎艿土畠?yōu)惠的共享交通出行時(shí)，也能夠快速達(dá)成一致決策（如是否調(diào)整出行時(shí)間，是否繞道接載），提升用戶體驗(yàn)，從而促進(jìn)人們選擇共享交通出行并加以保持，因此，充分考慮個(gè)體用戶的活動(dòng)信息，推薦與其具有相似出行活動(dòng)的用戶，形成不同共乘群體，有助于保證高效與經(jīng)濟(jì)的共享出行，同時(shí)從群體層面上引導(dǎo)調(diào)控交通需求，優(yōu)化資源配置[4]。

共乘群體是指同一時(shí)間使用同一車輛出行的一組用戶[5]。他們有著相似的出行活動(dòng)，即相近的出發(fā)時(shí)間、出發(fā)地點(diǎn)以及目的地。共乘群體發(fā)現(xiàn)是查詢個(gè)體乘客在出行活動(dòng)上的相關(guān)性，為其推薦合適的群體進(jìn)行共乘。共乘群體發(fā)現(xiàn)離不開(kāi)軌跡數(shù)據(jù)的支撐。近年來(lái)，隨著移動(dòng)傳感設(shè)備以及視頻捕捉設(shè)備的廣泛應(yīng)用，軌跡數(shù)據(jù)獲取變得越來(lái)越便捷，能夠很好地表達(dá)用戶出行活動(dòng)的時(shí)空特征;然而高采樣率產(chǎn)生了海量攜帶時(shí)間標(biāo)簽的全球定位系統(tǒng)（Global Positioning System， GPS）數(shù)據(jù)，造成了群體發(fā)現(xiàn)中由于頻繁聚簇與簇內(nèi)外查詢帶來(lái)的高計(jì)算成本[6]，因此，構(gòu)造高效的數(shù)據(jù)結(jié)構(gòu)來(lái)管理大規(guī)模的軌跡數(shù)據(jù)，挖掘具有相似出行活動(dòng)的用戶形成共乘群體，將顯著提高用戶的共享出行體驗(yàn)。

國(guó)內(nèi)外專家學(xué)者對(duì)共乘群體發(fā)現(xiàn)問(wèn)題展開(kāi)了不同的分析研究。這些研究更多的是規(guī)劃用戶的出行活動(dòng)計(jì)劃，包括匹配司乘雙方[7-8]、選擇見(jiàn)面地點(diǎn)[9-10]及優(yōu)化路徑[11]。這些工作多是對(duì)數(shù)據(jù)的直接處理，沒(méi)有考慮大規(guī)模軌跡數(shù)據(jù)的處理。目前較少工作開(kāi)展建立共乘出行的軌跡索引結(jié)構(gòu)及群體快速查詢研究，因此有必要從軌跡檢索的角度深入解決共乘群體發(fā)現(xiàn)問(wèn)題。

本文分析了共乘出行下的時(shí)空軌跡及群體特征，提出了以共乘率為優(yōu)化目標(biāo)的群體發(fā)現(xiàn)模型描述。擴(kuò)展三維R樹(shù)（3DR-tree）構(gòu)造可高效管理起訖點(diǎn)（Origin-Destination， OD）軌跡的GeoOD（Geographic OD）-Tree索引結(jié)構(gòu)，提供過(guò)濾機(jī)制，降低檢索空間，提高群體發(fā)現(xiàn)效率。本文所做的主要工作如下：

1）定義共乘出行下群體發(fā)現(xiàn)問(wèn)題，提出運(yùn)用3DR-tree索引結(jié)構(gòu)來(lái)查詢?cè)跁r(shí)空域下具有相似出行活動(dòng)的用戶。

2）設(shè)計(jì)GeoOD-Tree索引結(jié)構(gòu)，用于存儲(chǔ)并壓縮海量OD軌跡，提出基于該結(jié)構(gòu)的共乘群體發(fā)現(xiàn)方法。采用真實(shí)大數(shù)據(jù)驗(yàn)證所提方法的可行性。

MixQuery，為使得MixQuery不突兀，在原文（引言最后一段）：2）設(shè)計(jì)GeoOD-Tree索引結(jié)構(gòu)，用于存儲(chǔ)并壓縮海量OD軌跡，提出基于該結(jié)構(gòu)的共乘群體發(fā)現(xiàn)方法。采用真實(shí)大數(shù)據(jù)驗(yàn)證所提方法的可行性。添加一段描述：現(xiàn)為：2）設(shè)計(jì)GeoOD-Tree索引結(jié)構(gòu)，用于存儲(chǔ)并壓縮海量OD軌跡，提出基于該結(jié)構(gòu)的共乘群體發(fā)現(xiàn)方法，即混和時(shí)間域和空間域同時(shí)進(jìn)行相似群體查詢（Mix Spatio-temporal Query），簡(jiǎn)稱MixQuery。采用真實(shí)大數(shù)據(jù)驗(yàn)證所提方法的可行性。

2）設(shè)計(jì)GeoOD-Tree索引結(jié)構(gòu)，用于存儲(chǔ)并壓縮海量OD軌跡，提出基于該結(jié)構(gòu)的共乘群體發(fā)現(xiàn)方法，即混合時(shí)間域和空間域同時(shí)進(jìn)行相似群體查詢（Mix spatio-temporal Query， MixQuery），采用真實(shí)大數(shù)據(jù)驗(yàn)證所提方法的可行性。

1 相關(guān)工作

1.1 共乘群體發(fā)現(xiàn)

共乘群體推薦問(wèn)題，主要通過(guò)分析不同用戶的出行活動(dòng)信息，匹配具有相似出行活動(dòng)的用戶并將他們作為一個(gè)共乘群體。國(guó)外諸多專家學(xué)者針對(duì)共乘群體推薦問(wèn)題展開(kāi)了不同的研究。Ghoseiri等[12]進(jìn)行了共乘匹配研究并提出了最優(yōu)匹配模型，通過(guò)分析接收到的不同乘客以及司機(jī)的出行活動(dòng)計(jì)劃，將時(shí)間和空間上鄰近的乘客群體與司機(jī)進(jìn)行匹配，從而得到共乘群體。Vanoutrive等[13]基于用戶的歷史移動(dòng)行為建立變階馬爾可夫模型（Variable Order Markov Model， VOMM），將出發(fā)地點(diǎn)、出發(fā)時(shí)間與目的地相同的用戶作為一個(gè)潛在共乘群體。Bakkal等[14]提出了一個(gè)新穎的共乘群體推薦方法，通過(guò)對(duì)出行軌跡數(shù)據(jù)建立Neo4j時(shí)空樹(shù)模型，過(guò)濾出行時(shí)間和地點(diǎn)信息，將出行時(shí)間和地點(diǎn)匹配的用戶作為最終的共乘群體。

1.2 時(shí)空軌跡索引

時(shí)空索引技術(shù)主要是針對(duì)海量時(shí)空數(shù)據(jù)的無(wú)序性，通過(guò)對(duì)海量時(shí)空軌跡建立時(shí)空索引，可以提高軌跡查詢的效率。時(shí)空軌跡索引方法一般可以被分為三類：1）索引歷史軌跡;2）索引當(dāng)前位置;3）索引移動(dòng)對(duì)象的未來(lái)位置。由于R-tree[15]在空間數(shù)據(jù)庫(kù)的良好表現(xiàn)，當(dāng)前研究的空間軌跡的索引結(jié)構(gòu)多是基于R-tree展開(kāi)的。第一種是針對(duì)大規(guī)模歷史軌跡的索引方法，如歷史R+樹(shù)（Historical R+-tree， HR+-tree）[16]、多版本三維R樹(shù)（Multi-Version 3DR-trees， MV3R-tree）[17]等。HR+-tree是一類重疊和多版本結(jié)構(gòu)的R-樹(shù)，它將時(shí)間維孤立于空間維，然后在每個(gè)時(shí)間片上建立一個(gè)R樹(shù)，在進(jìn)行時(shí)間片查詢時(shí)退化為R-樹(shù)的空間查詢。第二種索引方法主要是針對(duì)需要回答與當(dāng)前時(shí)間相關(guān)的查詢，如基于更新標(biāo)簽的R樹(shù)（R-tree with Update Memo RUM-tree）[18]、延遲更新的網(wǎng)格索引（Lazy-Update Grid-based， LUGrid）[19]，其中RUM-tree基于備忘錄的方式進(jìn)行更新，將更新操作的成本降低到只有插入操作的成本。第三種索引方法則是為了預(yù)測(cè)移動(dòng)對(duì)象的未來(lái)位置設(shè)計(jì)的索引結(jié)構(gòu)，如時(shí)間參數(shù)化R樹(shù)（Time Parameterized R-tree， TPR-tree）[20]、時(shí)間參數(shù)化的R*樹(shù)（Time Parameterized R*-tree， TPR-tree）[21]，其中TPR-tree實(shí)際上是以時(shí)間為參數(shù)的R*-tree，索引結(jié)構(gòu)的節(jié)點(diǎn)中存儲(chǔ)了對(duì)象位置和該位置上的速度，可以支持查詢未來(lái)時(shí)刻的軌跡信息。

1.3 時(shí)空軌跡相似性

時(shí)空軌跡相似性的計(jì)算不同于空間軌跡相似性，它要求某種形式上的采樣點(diǎn)對(duì)齊，即通過(guò)時(shí)間的順序來(lái)映射點(diǎn)以計(jì)算軌跡相似性;同時(shí)，它允許軌跡時(shí)移，因此兩個(gè)軌跡的采樣時(shí)間戳不必嚴(yán)格一致。研究人員對(duì)時(shí)空軌跡的相似性作了廣泛的研究。Assent等[22]利用動(dòng)態(tài)時(shí)間規(guī)劃（Dynamic Time Warping， DTW）的方法，它允許一些點(diǎn)可以重復(fù)計(jì)算以進(jìn)行最佳對(duì)齊，但噪聲的存在使得重復(fù)計(jì)算會(huì)帶來(lái)無(wú)意義的誤差。Vlachos等[23]利用最長(zhǎng)公共子序列（Longest Common SubSequence， LCSS）方法消除噪聲，但是未解決處理時(shí)間軸拉伸和收縮帶來(lái)的變形問(wèn)題此處不通順，應(yīng)該是“未解決”吧？。Chen等[24]通過(guò)剔除實(shí)際補(bǔ)償編輯距離（Edit distance with Real Penalty， ERP），利用閾值ε來(lái)量化匹配;作為一種改進(jìn)，將ERP與DTW方法的優(yōu)勢(shì)結(jié)合，通過(guò)使用恒定的參考點(diǎn)計(jì)算距離來(lái)處理時(shí)間偏移。Frentzos等[25]提出了相異性度量（DISSIMilarity measure， DISSIM）算法，通過(guò)兩個(gè)軌跡之間的歐氏距離的時(shí)間函數(shù)的定積分，定義了兩個(gè)軌跡的不相似性，算法要求這兩個(gè)軌跡具有相似的采樣周期（即每個(gè)采樣時(shí)間戳在兩個(gè)軌跡中都存在采樣點(diǎn)）;但是，由于僅考慮一對(duì)一映射，DISSIM無(wú)法應(yīng)對(duì)本地時(shí)間偏移，因此，只有當(dāng)它們以相同的速度行進(jìn)時(shí)，DISSIM才能在非均勻采樣率下檢測(cè)軌跡之間的相似性。Sankararaman等[26]提出對(duì)DTW的一種改進(jìn)算法——模型驅(qū)動(dòng)算法（Model-driven Assignment， MA），它在軌跡點(diǎn)對(duì)齊方面更加靈活。相似的軌跡部分比不相似的部分（間隙部分）貢獻(xiàn)更高的MA分值;但是它引入了時(shí)間倒退的對(duì)齊，因此違反了時(shí)間序列匹配的基本前提。

2 共乘出行下的群體發(fā)現(xiàn)

在這一章中提出了共乘群體及其共乘路徑，進(jìn)而采用共乘率形式化描述群體發(fā)現(xiàn)問(wèn)題。在計(jì)算共乘率時(shí)，本文假設(shè)乘客接受為其推薦的共乘群體。

2.1 基本定義

其中：

定義4 群體。給定乘客OD軌跡Qi，若存在M個(gè)乘客的OD軌跡Qm，使得m∈[1，M]（QiQm），則可形成具有相似出行偏好的群體RGi根據(jù)T為轉(zhuǎn)置，那么RGi應(yīng)該是矢量、向量或矩陣吧？若是的話，全文的RGi是否均是矢量、向量或矩陣？請(qǐng)明確。否則無(wú)法理解。要注意修改的連貫性=（kim）1×MT·UM此處的T，是何意？與前面一樣，是集合？還是表示向量的轉(zhuǎn)置？請(qǐng)明確。若為向量、矢量或矩陣的轉(zhuǎn)置，請(qǐng)將文中的向量、矢量或矩陣標(biāo)識(shí)出來(lái)（這些需特別加黑處理），我們按照你的提示再修改：

0，其他

2.2 問(wèn)題描述

為提高共乘效率，降低司乘雙方共乘成本，有必要準(zhǔn)確推薦群體，使得成員選取的共乘路徑最長(zhǎng)。給定一組群體RGi的OD軌跡QiRG=（Q1，Q2，…，Qs，…，QH）i，與司機(jī)OD軌跡Qdrive，一組協(xié)商上下車地點(diǎn)up、off，群體發(fā)現(xiàn)問(wèn)題是搜尋一組乘客形成群體，使得其成員共乘率最大。

定理1 當(dāng)群體成員具有相似的OD軌跡時(shí)，其群體共乘率最大。

證明 根據(jù)定義6，通過(guò)減少乘客的步行成本，能夠提高共乘率。當(dāng)給定一組群體RGi，當(dāng)兩成員滿足min（dist（oi，os）+dist（di，ds））。條件使QiQs時(shí)，成員到達(dá)其約定地點(diǎn)距離總和最近，換乘空間成本最低，因此，通過(guò)將具有相似OD軌跡的乘客推薦為一個(gè)群體能夠保證共乘成本最小，從而使得共乘率最大。

其中：‖·‖∞上面的公式中沒(méi)有出現(xiàn)“‖‖”符號(hào)，是哪個(gè)公式寫漏了？=max1≤i，s≤M（·）;Dists（·）為兩點(diǎn)的時(shí)空距離，dist（·）為兩點(diǎn)的空間距離何意，需補(bǔ)充其所代表含義。

共乘用戶群體發(fā)現(xiàn)是針對(duì)出行用戶群里的應(yīng)用目標(biāo)。選擇群體以用戶出行的空間和時(shí)間兩個(gè)特征作為選擇標(biāo)準(zhǔn)，挖掘具有特定時(shí)間范圍和空間范圍的出行者共乘小組。群體發(fā)現(xiàn)算法具有一般的過(guò)程：首先定義群體的特征，然后建立描述群體聚集度的函數(shù)表達(dá)，最后設(shè)計(jì)算法對(duì)定義的群體進(jìn)行發(fā)現(xiàn)。通常群體發(fā)現(xiàn)是NP難問(wèn)題，因此需要設(shè)計(jì)啟發(fā)式算法求其最優(yōu)解[27]。本文采用基于個(gè)體屬性特征的群體發(fā)現(xiàn)算法，利用R樹(shù)的聚類特性，通過(guò)個(gè)體屬性向量之間的相似性作為基礎(chǔ)，在屬性空間中劃分群體。在第3章中引入基于R樹(shù)的索引結(jié)構(gòu)，并仔細(xì)說(shuō)明如何進(jìn)行基于GeoOD-Tree的群體發(fā)現(xiàn)策略。

3 基于3DR-tree的群體發(fā)現(xiàn)策略

3.1 軌跡標(biāo)定

時(shí)空軌跡體現(xiàn)了用戶在不同地點(diǎn)的停留與轉(zhuǎn)移活動(dòng)，能夠挖掘用戶的出行特征，包括出行時(shí)間、出行OD與出行方式等。相關(guān)工作采用GPS數(shù)據(jù)來(lái)識(shí)別用戶出行活動(dòng)[28]，然而GPS數(shù)據(jù)在一定程度上隱藏了大量語(yǔ)義信息，而且，按照不同采樣速率與策略（例如基于持續(xù)時(shí)間、區(qū)域范圍等）識(shí)別的軌跡可能會(huì)出現(xiàn)不一致[29]，這將導(dǎo)致后期對(duì)相似用戶與群體發(fā)現(xiàn)的錯(cuò)誤識(shí)別。

在OD軌跡中，一個(gè)停留地點(diǎn)可以看作是一次行程的出發(fā)地或目的地。停留地點(diǎn)描述了用戶發(fā)生停留活動(dòng)的地理區(qū)域。一個(gè)停留地點(diǎn)具有確定的時(shí)空信息，包括地理空間（lat，lon）與停留時(shí)段（arvtime，levtime），因此，可采用停留地點(diǎn)來(lái)標(biāo)定OD軌跡。

本文的前期工作[30]中，采用有限駐留點(diǎn)（Limited to Stay Point， LSP）聚類算法提取原始軌跡的駐留點(diǎn)。LSP算法是通過(guò)在給定的時(shí)空域內(nèi)分析停留活動(dòng)，搜尋由GPS數(shù)據(jù)缺失與波動(dòng)影響的一組位置信息。這樣，采用一組停留地點(diǎn)可挖掘用戶的出行OD信息，進(jìn)而形成一條OD軌跡。

3.2 GeoOD-Tree索引結(jié)構(gòu)

為有效管理用戶的OD軌跡，提供對(duì)sODsOD為何意？請(qǐng)補(bǔ)充說(shuō)明軌跡的快速檢索，本文引入了3DR-tree索引結(jié)構(gòu)[31]。3DR-tree是在R-tree的基礎(chǔ)上加入時(shí)間域，擴(kuò)展成3維R-tree。該結(jié)構(gòu)從葉子節(jié)點(diǎn)開(kāi)始，運(yùn)用最小邊界立方體（Minimum Bounding Box， MBB）覆蓋全部對(duì)象。通過(guò)自下而上地增加樹(shù)節(jié)點(diǎn)，增加MBB面積，實(shí)現(xiàn)對(duì)空間數(shù)據(jù)進(jìn)行分割。

本文擴(kuò)展3DR-tree來(lái)構(gòu)建OD軌跡的索引結(jié)構(gòu)，GeoOD-Tree（Geographic OD-Tree）。圖2展示了GeoOD-Tree的索引結(jié)構(gòu)實(shí)例。假定節(jié)點(diǎn)的最大條目數(shù)M=4，圖2（a）給出中間節(jié)點(diǎn)（R1、R2）和葉子節(jié)點(diǎn)（A、B、C、D、E）結(jié)構(gòu)。每個(gè)葉子節(jié)點(diǎn)分別存儲(chǔ)一組鄰近的停留地點(diǎn)及其對(duì)應(yīng)的用戶信息。其中，采用（ID，state）二元組來(lái)描述用戶信息，分別代表用戶ID和地點(diǎn)的類型標(biāo)記，該標(biāo)記用于表明該地點(diǎn)是出發(fā)地或目的地。GeoOD-Tree采用MBB覆蓋上述對(duì)象的邊界，如圖2（b）中節(jié)點(diǎn)D所示。節(jié)點(diǎn)R1、R2存儲(chǔ)了MBB標(biāo)識(shí)和指向子節(jié)點(diǎn)的指針，采用（I，child-pointer）二元組表示，如圖2（b）中，R1的MBB包含了A、E、F的MBB。

在GeoOD-Tree中，除了根節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)至少包含m且至多包含M個(gè)條目（1

與傳統(tǒng)R-Tree相似，GeoOD-Tree索引結(jié)構(gòu)能夠在葉子節(jié)點(diǎn)中插入出發(fā)地或目的地對(duì)象。圖3（a）為實(shí)例的二維空間切面圖。當(dāng)需要進(jìn)行插入操作（圖中所示的對(duì)象P）時(shí)，比較對(duì)象插入前后各葉子節(jié)點(diǎn)MBB體積的變化，選取變化最小的葉子節(jié)點(diǎn)作為插入目標(biāo)。在圖3（b）中，從根節(jié)點(diǎn)R1、R2開(kāi)始，若P插入到R1時(shí)該節(jié)點(diǎn)對(duì)應(yīng)的MBB體積變化最小，則選取R1作為候選插入目標(biāo)進(jìn)行深度搜索。在同一層進(jìn)行廣度搜索，確定R3與R27節(jié)點(diǎn)為不同層的候選插入目標(biāo)。分裂步驟如圖3（c）所示，由于受節(jié)點(diǎn)條目容量（M=4）影響，若P插入到R27時(shí)該節(jié)點(diǎn)發(fā)生上溢，則啟動(dòng)平方分裂操作。R27分裂成兩個(gè)節(jié)點(diǎn)：R27和R27′，調(diào)整GeoOD-Tree結(jié)構(gòu)形成平衡樹(shù)，保證后期查詢效率的穩(wěn)定性。

當(dāng)將R27′插入到節(jié)點(diǎn)R3時(shí)候，繼續(xù)受節(jié)點(diǎn)條目容量的影響，R3發(fā)生上溢，繼續(xù)啟動(dòng)平方分裂操作，R3分裂成R3和R3′。根據(jù)體積最小原則，R3存儲(chǔ)R27、R27′、R26，R3′存儲(chǔ)R8、R25。由于R3所在節(jié)點(diǎn)的條目數(shù)小于M，R1節(jié)點(diǎn)不再分裂。

3.3 節(jié)點(diǎn)剪枝

群體發(fā)現(xiàn)在于查詢一組具有相似OD軌跡的乘客。傳統(tǒng)的查詢方法需要對(duì)所有OD對(duì)進(jìn)行相似性評(píng)估與排序，通常需要獲取軌跡的全局特征信息，導(dǎo)致高計(jì)算成本，為此降低搜索空間、減少不必要計(jì)算是提高群體發(fā)現(xiàn)效率的必要措施。

本文將乘客的換乘空間成本作為影響共乘出行選擇的因素。當(dāng)換乘空間成本超過(guò)θsp或等待時(shí)長(zhǎng)超過(guò)θts時(shí)，用戶將放棄共乘出行，群體發(fā)現(xiàn)無(wú)效。本文采用基于mindist[32]的剪枝方法預(yù)先過(guò)濾存儲(chǔ)此類用戶OD的子樹(shù)來(lái)減少節(jié)點(diǎn)訪問(wèn)次數(shù)。本文首先確定查詢閾值mindisth，用于向上剪枝無(wú)法共乘的節(jié)點(diǎn)。

其中，mindisth閾值的確定公式為：

在傳統(tǒng)空間數(shù)據(jù)庫(kù)中，OD軌跡的數(shù)據(jù)量巨大且數(shù)據(jù)結(jié)構(gòu)復(fù)雜，通常OD軌跡涵蓋了時(shí)間和空間兩個(gè)屬性，在進(jìn)行K最近鄰（K Nearest Neighbors， KNN）查詢時(shí)，通常需要進(jìn)行兩步查詢，首先進(jìn)行時(shí)間或空間查詢，然后再進(jìn)行空間或時(shí)間查詢，使得最后查詢的時(shí)間和空間代價(jià)非常昂貴。GeoOD-Tree中的每個(gè)節(jié)點(diǎn)包含了時(shí)間和空間信息，利用提出的時(shí)空距離計(jì)算公式可以同時(shí)進(jìn)行時(shí)間和空間的查詢，因此使得查詢代價(jià)降低。同傳統(tǒng)R樹(shù)一樣，KNN查詢和范圍查詢是由根節(jié)點(diǎn)開(kāi)始向下查詢，直到葉子節(jié)點(diǎn)。查詢過(guò)程中需要遍歷每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)的最小外包矩形與待查詢對(duì)象的距離，然后選取合適節(jié)點(diǎn)繼續(xù)向下一層遍歷。在進(jìn)行遍歷過(guò)程中加入上文所提剪枝算法，如果在一次計(jì)算中，節(jié)點(diǎn)距查詢對(duì)象的距離大于mindisth，則可以直接減掉該節(jié)點(diǎn)，從而可以大幅度減少查詢過(guò)程中的計(jì)算量，提高GeoOD-Tree的查詢效率。

3.4 群體發(fā)現(xiàn)策略

本文在時(shí)空約束下壓縮搜索空間，提供了基于KNN的OD軌跡查詢。OD軌跡查詢的描述如下。

本文在時(shí)空約束下壓縮搜索空間，基于KNN方法，對(duì)OD軌跡進(jìn)行時(shí)空閾混合查詢即MixQuery。OD軌跡的混合查詢的描述如下。

本文從GeoOD-Tree根節(jié)點(diǎn)進(jìn)行最佳優(yōu)先搜索。用KNN查詢分別搜索滿足上述條件的K個(gè)對(duì)象。以下給出了此類查詢的執(zhí)行過(guò)程，最終將查詢得到兩個(gè)集合OSet，DSet。通過(guò)對(duì)兩個(gè)集合在用戶ID上取交，返回候選OD對(duì)集合法返回候選OD對(duì)集合，算法如下此句不通順，請(qǐng)作相應(yīng)調(diào)整。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 數(shù)據(jù)描述

本文使用西安市一天的出租車營(yíng)運(yùn)數(shù)據(jù)（全市有12000余輛出租車，一天的原始軌跡的數(shù)據(jù)輛約2.8GB）。經(jīng)過(guò)數(shù)據(jù)預(yù)處理和軌跡標(biāo)定后，提取約1205700條出租車OD軌跡數(shù)據(jù)。

4.2 參數(shù)設(shè)置

本文設(shè)定了GeoOD-Tree中最小條目數(shù)m與最大條目數(shù)M關(guān)系為m=M/2。本文首先分析了M對(duì)構(gòu)造GeoOD-Tree的影響，如圖4（a），當(dāng)M<32時(shí)，隨著M的增大，建立完整的GeoOD-Tree結(jié)構(gòu)所花費(fèi)的時(shí)間呈緩慢下降趨勢(shì)。在M=32時(shí)，建立的花費(fèi)時(shí)間達(dá)到最低，但隨著M的繼續(xù)增大，GeoOD-Tree花費(fèi)時(shí)間呈快速上升趨勢(shì)。對(duì)于M參數(shù)與樹(shù)的深度關(guān)系，如圖4（b）中，隨著M的增大，與之對(duì)應(yīng)的樹(shù)的深度隨之下降。

為了探究參數(shù)M對(duì)查詢速度的影響，本文對(duì)比了KNN查詢和Range查詢效率與M值的關(guān)系。實(shí)驗(yàn)設(shè)置K為500，結(jié)果如圖5（a）所示，KNN的查詢效率曲線近似V字型，在M為32時(shí)，KNN查詢時(shí)延最小。

然后實(shí)驗(yàn)繼續(xù)分析了Range查詢效率，本文在數(shù)據(jù)集范圍內(nèi)隨機(jī)生成1000個(gè)Range查詢，可以看到在M為32時(shí)查詢效率最高。隨著M的增大效率降低，在M為128時(shí)發(fā)生波動(dòng)，查詢效率達(dá)到最低，然后隨著M的增大效率開(kāi)始緩慢上升，但始終低于M=32時(shí)的查詢效率。

上述實(shí)驗(yàn)中，在M=32時(shí)，建立GeoOD-Tree的時(shí)間達(dá)到最小，當(dāng)M繼續(xù)增大時(shí)，建立時(shí)間隨之增大，這是因?yàn)樵诮eoOD-Tree的過(guò)程時(shí)，由于每個(gè)節(jié)點(diǎn)索引條目較多，在調(diào)整樹(shù)形以保證所有節(jié)點(diǎn)都在同一深度時(shí)，需要花費(fèi)更多的時(shí)間。在進(jìn)行查詢時(shí)，當(dāng)樹(shù)的深度增加時(shí)，需要進(jìn)行多次計(jì)算來(lái)查找與查詢對(duì)象相交的節(jié)點(diǎn)。由于節(jié)點(diǎn)的MBB會(huì)出現(xiàn)重疊，因此當(dāng)M增大時(shí)，節(jié)點(diǎn)之間的重疊度增加，在進(jìn)行查詢時(shí)可能會(huì)遍歷較多無(wú)關(guān)節(jié)點(diǎn)降低了整體查詢效率。通過(guò)圖5可以看到，當(dāng)M=32時(shí)，范圍查詢和KNN查詢都達(dá)到了最高效率，因此，本文選取M=32作為后續(xù)OD查詢的參數(shù)。

4.3 查詢性能分析

本文選取DTW以及Duan等[30]算法進(jìn)行對(duì)比，DTW算法是處理時(shí)空軌跡的經(jīng)典算法，當(dāng)前的大多數(shù)的時(shí)空軌跡的查詢都是在DTW的方法上進(jìn)行改進(jìn)。Duan等[30]算法是前期工作利用停留點(diǎn)建立用戶位置軌跡和服務(wù)軌跡模型來(lái)進(jìn)行相似用戶發(fā)現(xiàn)的算法。

關(guān)于ByPOI：ByPOI是對(duì)論文Duan等[30]論文所用算法的一個(gè)總結(jié)，并沒(méi)有給定全稱，故根據(jù)其特征用ByPOI來(lái)代替此方法。

為便于理解，在本文的原文：本文選取DTW以及Duan中的算法，DTW算法是處理時(shí)空軌跡的經(jīng)典算法，當(dāng)前的大多數(shù)的時(shí)空軌跡的查詢都是在DTW的方法上進(jìn)行改進(jìn)。Duan 算法是前期工作利用停留點(diǎn)建立用戶位置軌跡和服務(wù)軌跡模型來(lái)進(jìn)行相似用戶發(fā)現(xiàn)的算法。添加部分描述。

現(xiàn)修改為：本文選取DTW以及Duan [30]中提取的算法ByPOI，DTW算法是處理時(shí)空軌跡的經(jīng)典算法，當(dāng)前的大多數(shù)的時(shí)空軌跡的查詢都是在DTW的方法上進(jìn)行改進(jìn)。ByPOI算法是前期工作利用停留點(diǎn)建立用戶位置軌跡以及利用POI建立服務(wù)軌跡模型來(lái)進(jìn)行相似用戶發(fā)現(xiàn)的算法。

本文選取DTW以及Duan等[30]提出的算法ByPOI，DTW算法是處理時(shí)空軌跡的經(jīng)典算法，當(dāng)前大多數(shù)的時(shí)空軌跡的查詢都是在DTW方法上進(jìn)行改進(jìn)。ByPOI算法是前期工作利用停留點(diǎn)建立用戶位置軌跡以及利用POI（Point of Interest）建立服務(wù)軌跡模型來(lái)進(jìn)行相似用戶發(fā)現(xiàn)的算法。

在實(shí)驗(yàn)中，將時(shí)間變化范圍設(shè)置為5min，對(duì)應(yīng)空間距離設(shè)置為[300，400，500]。進(jìn)行歸一化后設(shè)定λ∈[0.0177，0.0197]，τ∈[0.0035]，δ=λe-ωτ∈[0.0175，0.0195]，其中ω=-2。圖6給出了算法的性能對(duì)比。在查準(zhǔn)率方面圖6（a）：在δ等于0.0185時(shí)，即空間約束為500m、時(shí)間約束為5min時(shí)，本文提出的算法的準(zhǔn)確率達(dá)到最高為79%;隨著δ的增加，對(duì)共乘的約束減小，即空間和時(shí)間的范圍更大，在實(shí)際共乘交通中這將導(dǎo)致出行用戶放棄共乘，因此導(dǎo)致了查準(zhǔn)率的下降。在查全率方面圖6（b）：隨著δ的增加，即意味著空間和時(shí)間的約束變得寬松，所有算法的查全率都有所提高，并且提出算法的查全率都比其他算法高;在δ=0.0185時(shí)，本文所提算法的準(zhǔn)確性達(dá)到最高為86%。為了評(píng)價(jià)算法的綜合的性能，比較了三種算法的F1值此處是否應(yīng)該為“F1”？請(qǐng)明確?；貜?fù)：文中應(yīng)為F1值，結(jié)果如圖6（c）所示，三種算法在δ=0.0185時(shí)達(dá)到最好，接著隨著δ的增大準(zhǔn)確度開(kāi)始下降;在具體表現(xiàn)方面，本文所提的算法比其他兩種算法平均高出約9%。最后，本文比較了三種算法的執(zhí)行效率，如圖6（d），本文算法由于采用了GeoOD-Tree，在進(jìn)行群體查詢時(shí)的時(shí)間花費(fèi)上其他兩種算法幾倍的幾分之一，效率遠(yuǎn)遠(yuǎn)高于其他兩種算法。通過(guò)四個(gè)實(shí)驗(yàn)對(duì)比，可以看出本文提出的MixQuery算法在查準(zhǔn)率和查全率方面皆優(yōu)于其他兩種算法，而在加入了GeoOD-Tree索引后，算法整體效率遠(yuǎn)遠(yuǎn)高于其他兩種算法，因此，本文提出的群體發(fā)現(xiàn)算法明優(yōu)于其他兩種算法。

5 結(jié)語(yǔ)

本文運(yùn)用時(shí)空軌跡分析共乘出行特征與群體發(fā)現(xiàn)問(wèn)題，首先定義了以最大共乘率為目標(biāo)的群體發(fā)現(xiàn)模型，將問(wèn)題轉(zhuǎn)化為搜索一組具有相似OD軌跡的乘客;然后設(shè)計(jì)了GeoOD-Tree索引結(jié)構(gòu)來(lái)有效存儲(chǔ)與管理出行OD軌跡，并設(shè)計(jì)有效的剪枝算法以進(jìn)行快速查詢滿足時(shí)空約束的用戶組成群體;最后通過(guò)真實(shí)出租車營(yíng)運(yùn)數(shù)據(jù)對(duì)提出的算法進(jìn)行性能評(píng)估。實(shí)驗(yàn)結(jié)果表明，本文提出的算法比其他算法具有較高的查詢效率以及較優(yōu)的查全率與查準(zhǔn)率。在未來(lái)的工作中，將繼續(xù)分析并存儲(chǔ)出行路徑、活動(dòng)類型等特征，進(jìn)一步提高群體發(fā)現(xiàn)方法的適用性。

參考文獻(xiàn) （References）

[1] ZHANG D， HE T， LIU Y， et al. A carpooling recommendation system for taxicab services [J]. IEEE Transactions on Emerging Topics in Computing， 2017， 2（3）：254-266.

[2] ARTAN Y， BULAN O， LOCE R P， et al. Passenger compartment violation detection in HOV/HOT lanes [J]. IEEE Transactions on Intelligent Transportation Systems， 2016， 17（2）：395-405.

[3] DONG H， MA L， BROACH J. Promoting sustainable travel modes for commute tours： a comparison of the effects of home and work locations and employer-provided incentives [J]. International Journal of Sustainable Transportation， 2016， 10（6）： 485-494.

[4] 陳艷艷，劉小明.城市交通出行行為機(jī)理及引導(dǎo)策略[M].北京：科學(xué)出版社，2016：10-13（CHEN Y Y， LIU X M. Urban Traffic Travel Behavior Mechanism and Guidance Strategy[M]. Beijing： Science Press，2016：10-13.

[5] AGATZ N， ERERA A， SAVELSBERGH M， et al. Optimization for dynamic ride-sharing： a review [J]. European Journal of Operational Research， 2012， 223（2）： 295-303.

[6] TANG L A， ZHENG Y， YUAN J， et al. A framework of traveling companion discovery on trajectory data streams [J]. ACM Transactions on Intelligent Systems & Technology， 2014， 5（1）：1-34.

[7] TA N， LI G， ZHAO T， et al. An efficient ride-sharing framework for maximizing shared route [J]. IEEE Transactions on Knowledge and Data Engineering， 2018， 30（2）： 219-233.

[8] LI X， CEIKUTE V， JENSEN C S， et al. Effective online group discovery in trajectory databases [J]. IEEE Transactions on Knowledge and Data Engineering， 2013， 25（12）：2752-2766.

[9] KHAN A K M， CORREA O， TANIN E， et al. Ride-sharing is about agreeing on a destination[C]// Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York： ACM， 2017： 6.

[10] REZA R M， ALI M E， CHEEMA M A. The optimal route and stops for a group of users in a road network [J]. ArXiv Preprint， 2017， 2017： 1706.07829.

[11] 李妍峰，高自友，李軍.基于實(shí)時(shí)交通信息的城市動(dòng)態(tài)網(wǎng)絡(luò)車輛路徑優(yōu)化問(wèn)題[J].系統(tǒng)工程理論與實(shí)踐，2013，33（7）：1813-1819.（LI Y F， GAO Z Y， LI J. Vehicle routing problem in dynamic urban network with real-time traffic information [J]. Systems Engineering — Theory & Practice， 2013， 33（7）：1813-1819.）

[12] GHOSEIRI K， HAGHANI A E， HAMEDI M， et al. Real-time Rideshare Matching Problem [M]. Berkeley： Mid-Atlantic Universities Transportation Center， 2011：21-30.

[13] VANOUTRIVE T， VIJVER E V D， MALDEREN L V， et al. What determines carpooling to workplaces in Belgium： location， organization， or promotion？ [J]. Journal of Transport Geography， 2012， 22（2）：77-86.

[14] BAKKAL F， EKEN S， SAVAS N S， et al. Modeling and querying trajectories using Neo4j spatial and TimeTree for carpool matching[C]// Proceedings of the 2017 IEEE International Conference on Innovations in Intelligent Systems and Applications. Piscataway， NJ： IEEE， 2017：219-222.

[15] GUTTMAN A. R-trees： a dynamic index structure for spatial searching [C]// Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data. New York： ACM， 1984： 47-57.

[16] TAO Y， PAPADIAS D. Efficient historical R-trees[C]// Proceedings of the 13th International Conference on Scientific and Statistical Database Management. Washington， DC： IEEE Computer Society， 2001： 223.

[17] TAO Y， PAPADIAS D. The MV3R-tree： a spatio-temporal access method for timestamp and interval queries[C]// Proceedings of the 27th International Conference on Very Large Data Bases. Madison： Morgan Kaufmann， 2001： 431-440.

[18] SILVA Y N， XIONG X， AREF W G. The RUM-tree： supporting frequent updates in R-trees using memos[J]. The International Journal on Very Large Data Bases， 2009， 18（3）： 719-738.

[19] XIONG X， MOKBEL M F， AREF W G. LUGrid： update-tolerant grid-based indexing for moving objects[C]// Proceedings of the 2006 International Conference on Mobile Data Management. Washington， DC： IEEE Computer Society， 2006： 13.

[20] SALTENIS S， JENSEN C S， LEUTENEGGER S T， et al. Indexing the positions of continuously moving objects [J]. ACM SIGMOD Record， 2000， 29（2）：331-342.

[21] TAO Y， PAPADIAS D， SUN J. The TPR*-tree： an optimized spatiotemporal access method for predictive queries[C]// Proceedings of the 29th International Conference on Very Large Data Bases. [S.l.]： VLDB Endowment， 2003： 790-801.

[22] ASSENT I， WICHTERICH M， KRIEGER R， et al. Anticipatory DTW for efficient similarity search in time series databases[J]. Proceedings of the VLDB Endowment， 2009，2（1）：826-837，.

[23] VLACHOS M， KOLLIOS M， GUNOPULOS D. Discovering similar multidimensional trajectories[C]// Proceedings of the 2002 International Conference on Data Engineering. Piscataway， NJ： IEEE， 2002： 673-684.

[24] CHEN L， NG R. On the marriage of LP-norms and edit distance[C]// Proceedings of the Thirtieth International Conference on Very Large Data Bases. [S.l.]： VLDB Endowment， 2004： 792-803.

[25] FRENTZOS E， GRATSIAS K， THENODORIDIS Y. Index-based most similar trajectory search[C]// Proceedings of the 2007 IEEE 23rd International Conference on Data Engineering. Piscataway， NJ： IEEE， 2007： 816-825.

[26] SANKARARAMAN S， AGARWAL P K， MOLHAVE T， et al. Model-driven matching and segmentation of trajectories[C]// Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York： ACM， 2013： 234-243.

[27] 潘理，吳鵬，黃丹華.在線社交網(wǎng)絡(luò)群體發(fā)現(xiàn)研究進(jìn)展[J].電子與信息學(xué)報(bào)，2017，39（9）：2097-2107.（PAN L， WU P， HUANG D H. Reviews on group detection in online social networks[J]. Journal of Electronics & Information Technology， 2017， 39（9）：2097-2107.）

[28] TA N， LI G L， XIE Y Q. Signature-based trajectory similarity join [J]. IEEE Transactions on Knowledge and Data Engineering， 2017， 29（4）： 870-883.

[29] SU H， ZHENG K， HUANG J， et al. Calibrating trajectory data for spatio-temporal similarity analysis[J]. The VLDB Journal， 2015， 24（1）， 93-116.

[30] DUAN Z， TANG L， GONG X， et al. Personalized service recommendations for travel using trajectory pattern discovery [J]. International Journal of Distributed Sensor Networks， 2018， 14（3）：155014771876784.

[31] TODORIDIS Y， VAZIRGIANNIS M， SELLIS T. Spatio-temporal indexing for large multimedia applications[C]// Proceedings of the Third IEEE International Conference on Multimedia Computing and Systems. Piscataway， NJ： IEEE， 1996： 441-448.

[32] ROUSSOPOULOS N， KELLEY S， VINCENT F. Nearest neighbor queries[C]// SIGMOD 95： Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data. New York： ACM， 1995： 71-79.