共享交通的時空軌跡檢索與群體發現

段宗濤 龔學輝 唐蕾 陳柘

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

關鍵詞：共乘出行;群體發現;時空軌跡;3維R樹;起訖點

中圖分類號： TP301.6

文獻標志碼：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 引言

作為一類新興交通出行方式，共享交通的出現有助于緩解交通擁堵與道路磨損，減少空氣污染，降低對能源的依賴性[1]。通過充分利用交通運輸資源來提供多種形式和廉價方便的共享服務，改變人們傳統的消費觀念，變擁有汽車為使用服務。由于人類的社會群居特性，人們通常期望能夠與具有相同出行特征的用戶結伴出行[2]，例如通勤共乘者往往具有相同的出行活動路徑[3]。正是這種優于陌生乘客的潛在特征關聯，使得乘客們在享受低廉優惠的共享交通出行時，也能夠快速達成一致決策（如是否調整出行時間，是否繞道接載），提升用戶體驗，從而促進人們選擇共享交通出行并加以保持，因此，充分考慮個體用戶的活動信息，推薦與其具有相似出行活動的用戶，形成不同共乘群體，有助于保證高效與經濟的共享出行，同時從群體層面上引導調控交通需求，優化資源配置[4]。

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

國內外專家學者對共乘群體發現問題展開了不同的分析研究。這些研究更多的是規劃用戶的出行活動計劃，包括匹配司乘雙方[7-8]、選擇見面地點[9-10]及優化路徑[11]。這些工作多是對數據的直接處理，沒有考慮大規模軌跡數據的處理。目前較少工作開展建立共乘出行的軌跡索引結構及群體快速查詢研究，因此有必要從軌跡檢索的角度深入解決共乘群體發現問題。

本文分析了共乘出行下的時空軌跡及群體特征，提出了以共乘率為優化目標的群體發現模型描述。擴展三維R樹（3DR-tree）構造可高效管理起訖點（Origin-Destination， OD）軌跡的GeoOD（Geographic OD）-Tree索引結構，提供過濾機制，降低檢索空間，提高群體發現效率。本文所做的主要工作如下：

1）定義共乘出行下群體發現問題，提出運用3DR-tree索引結構來查詢在時空域下具有相似出行活動的用戶。

2）設計GeoOD-Tree索引結構，用于存儲并壓縮海量OD軌跡，提出基于該結構的共乘群體發現方法。采用真實大數據驗證所提方法的可行性。

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

2）設計GeoOD-Tree索引結構，用于存儲并壓縮海量OD軌跡，提出基于該結構的共乘群體發現方法，即混合時間域和空間域同時進行相似群體查詢（Mix spatio-temporal Query， MixQuery），采用真實大數據驗證所提方法的可行性。

1 相關工作

1.1 共乘群體發現

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

1.2 時空軌跡索引

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

1.3 時空軌跡相似性

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

2 共乘出行下的群體發現

在這一章中提出了共乘群體及其共乘路徑，進而采用共乘率形式化描述群體發現問題。在計算共乘率時，本文假設乘客接受為其推薦的共乘群體。

2.1 基本定義

其中：

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

0，其他

2.2 問題描述

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

定理1 當群體成員具有相似的OD軌跡時，其群體共乘率最大。

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

其中：‖·‖∞上面的公式中沒有出現“‖‖”符號，是哪個公式寫漏了？=max1≤i，s≤M（·）;Dists（·）為兩點的時空距離，dist（·）為兩點的空間距離何意，需補充其所代表含義。

共乘用戶群體發現是針對出行用戶群里的應用目標。選擇群體以用戶出行的空間和時間兩個特征作為選擇標準，挖掘具有特定時間范圍和空間范圍的出行者共乘小組。群體發現算法具有一般的過程：首先定義群體的特征，然后建立描述群體聚集度的函數表達，最后設計算法對定義的群體進行發現。通常群體發現是NP難問題，因此需要設計啟發式算法求其最優解[27]。本文采用基于個體屬性特征的群體發現算法，利用R樹的聚類特性，通過個體屬性向量之間的相似性作為基礎，在屬性空間中劃分群體。在第3章中引入基于R樹的索引結構，并仔細說明如何進行基于GeoOD-Tree的群體發現策略。

3 基于3DR-tree的群體發現策略

3.1 軌跡標定

時空軌跡體現了用戶在不同地點的停留與轉移活動，能夠挖掘用戶的出行特征，包括出行時間、出行OD與出行方式等。相關工作采用GPS數據來識別用戶出行活動[28]，然而GPS數據在一定程度上隱藏了大量語義信息，而且，按照不同采樣速率與策略（例如基于持續時間、區域范圍等）識別的軌跡可能會出現不一致[29]，這將導致后期對相似用戶與群體發現的錯誤識別。

在OD軌跡中，一個停留地點可以看作是一次行程的出發地或目的地。停留地點描述了用戶發生停留活動的地理區域。一個停留地點具有確定的時空信息，包括地理空間（lat，lon）與停留時段（arvtime，levtime），因此，可采用停留地點來標定OD軌跡。

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

3.2 GeoOD-Tree索引結構

為有效管理用戶的OD軌跡，提供對sODsOD為何意？請補充說明軌跡的快速檢索，本文引入了3DR-tree索引結構[31]。3DR-tree是在R-tree的基礎上加入時間域，擴展成3維R-tree。該結構從葉子節點開始，運用最小邊界立方體（Minimum Bounding Box， MBB）覆蓋全部對象。通過自下而上地增加樹節點，增加MBB面積，實現對空間數據進行分割。

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

在GeoOD-Tree中，除了根節點，每個節點至少包含m且至多包含M個條目（1

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

當將R27′插入到節點R3時候，繼續受節點條目容量的影響，R3發生上溢，繼續啟動平方分裂操作，R3分裂成R3和R3′。根據體積最小原則，R3存儲R27、R27′、R26，R3′存儲R8、R25。由于R3所在節點的條目數小于M，R1節點不再分裂。

3.3 節點剪枝

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

本文將乘客的換乘空間成本作為影響共乘出行選擇的因素。當換乘空間成本超過θsp或等待時長超過θts時，用戶將放棄共乘出行，群體發現無效。本文采用基于mindist[32]的剪枝方法預先過濾存儲此類用戶OD的子樹來減少節點訪問次數。本文首先確定查詢閾值mindisth，用于向上剪枝無法共乘的節點。

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

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

3.4 群體發現策略

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

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

本文從GeoOD-Tree根節點進行最佳優先搜索。用KNN查詢分別搜索滿足上述條件的K個對象。以下給出了此類查詢的執行過程，最終將查詢得到兩個集合OSet，DSet。通過對兩個集合在用戶ID上取交，返回候選OD對集合法返回候選OD對集合，算法如下此句不通順，請作相應調整。

4 實驗結果與分析

4.1 數據描述

本文使用西安市一天的出租車營運數據（全市有12000余輛出租車，一天的原始軌跡的數據輛約2.8GB）。經過數據預處理和軌跡標定后，提取約1205700條出租車OD軌跡數據。

4.2 參數設置

本文設定了GeoOD-Tree中最小條目數m與最大條目數M關系為m=M/2。本文首先分析了M對構造GeoOD-Tree的影響，如圖4（a），當M<32時，隨著M的增大，建立完整的GeoOD-Tree結構所花費的時間呈緩慢下降趨勢。在M=32時，建立的花費時間達到最低，但隨著M的繼續增大，GeoOD-Tree花費時間呈快速上升趨勢。對于M參數與樹的深度關系，如圖4（b）中，隨著M的增大，與之對應的樹的深度隨之下降。

為了探究參數M對查詢速度的影響，本文對比了KNN查詢和Range查詢效率與M值的關系。實驗設置K為500，結果如圖5（a）所示，KNN的查詢效率曲線近似V字型，在M為32時，KNN查詢時延最小。

然后實驗繼續分析了Range查詢效率，本文在數據集范圍內隨機生成1000個Range查詢，可以看到在M為32時查詢效率最高。隨著M的增大效率降低，在M為128時發生波動，查詢效率達到最低，然后隨著M的增大效率開始緩慢上升，但始終低于M=32時的查詢效率。

上述實驗中，在M=32時，建立GeoOD-Tree的時間達到最小，當M繼續增大時，建立時間隨之增大，這是因為在建立GeoOD-Tree的過程時，由于每個節點索引條目較多，在調整樹形以保證所有節點都在同一深度時，需要花費更多的時間。在進行查詢時，當樹的深度增加時，需要進行多次計算來查找與查詢對象相交的節點。由于節點的MBB會出現重疊，因此當M增大時，節點之間的重疊度增加，在進行查詢時可能會遍歷較多無關節點降低了整體查詢效率。通過圖5可以看到，當M=32時，范圍查詢和KNN查詢都達到了最高效率，因此，本文選取M=32作為后續OD查詢的參數。

4.3 查詢性能分析

本文選取DTW以及Duan等[30]算法進行對比，DTW算法是處理時空軌跡的經典算法，當前的大多數的時空軌跡的查詢都是在DTW的方法上進行改進。Duan等[30]算法是前期工作利用停留點建立用戶位置軌跡和服務軌跡模型來進行相似用戶發現的算法。

關于ByPOI：ByPOI是對論文Duan等[30]論文所用算法的一個總結，并沒有給定全稱，故根據其特征用ByPOI來代替此方法。

為便于理解，在本文的原文：本文選取DTW以及Duan中的算法，DTW算法是處理時空軌跡的經典算法，當前的大多數的時空軌跡的查詢都是在DTW的方法上進行改進。Duan 算法是前期工作利用停留點建立用戶位置軌跡和服務軌跡模型來進行相似用戶發現的算法。添加部分描述。

現修改為：本文選取DTW以及Duan [30]中提取的算法ByPOI，DTW算法是處理時空軌跡的經典算法，當前的大多數的時空軌跡的查詢都是在DTW的方法上進行改進。ByPOI算法是前期工作利用停留點建立用戶位置軌跡以及利用POI建立服務軌跡模型來進行相似用戶發現的算法。

本文選取DTW以及Duan等[30]提出的算法ByPOI，DTW算法是處理時空軌跡的經典算法，當前大多數的時空軌跡的查詢都是在DTW方法上進行改進。ByPOI算法是前期工作利用停留點建立用戶位置軌跡以及利用POI（Point of Interest）建立服務軌跡模型來進行相似用戶發現的算法。

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

5 結語

本文運用時空軌跡分析共乘出行特征與群體發現問題，首先定義了以最大共乘率為目標的群體發現模型，將問題轉化為搜索一組具有相似OD軌跡的乘客;然后設計了GeoOD-Tree索引結構來有效存儲與管理出行OD軌跡，并設計有效的剪枝算法以進行快速查詢滿足時空約束的用戶組成群體;最后通過真實出租車營運數據對提出的算法進行性能評估。實驗結果表明，本文提出的算法比其他算法具有較高的查詢效率以及較優的查全率與查準率。在未來的工作中，將繼續分析并存儲出行路徑、活動類型等特征，進一步提高群體發現方法的適用性。

參考文獻 （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] 陳艷艷，劉小明.城市交通出行行為機理及引導策略[M].北京：科學出版社，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] 李妍峰，高自友，李軍.基于實時交通信息的城市動態網絡車輛路徑優化問題[J].系統工程理論與實踐，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] 潘理，吳鵬，黃丹華.在線社交網絡群體發現研究進展[J].電子與信息學報，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.