共享交通的时空轨迹检索与群体发现

Spatio-temporal trajectory retrieval and group discovery in shared transportation

为解决共享交通下的共乘用户群体发现效率低、准确率不高问题,依据R-树原理建立Geo OD-Tree索引,并在此基础上提出以最大化共乘率为目标的群体发现策略。首先,对原始时空轨迹数据进行特征提取与标定处理,挖掘有效出行起讫点(OD)轨迹;其次,针对用户起讫点轨迹的特征,建立Geo OD-Tree索引进行有效的存储管理;最后,给出以最大化共乘行程为目标的群体发现模型,并运用K最近邻(KNN)查询对搜索空间剪枝压缩,提高群体发现效率。采用西安市近12 000辆出租车营运轨迹数据,选取动态时间规整(DTW)等典型算法与所提算法在查询效率与准确率上进行性能对比分析。与DTW算法相比,所提算法的准确率提高了10. 12%,查询效率提高了约15倍。实验结果表明提出的群体发现策略能有效提高共乘用户群体发现的准确率和效率,可有效提升共乘出行方式的出行率。

Concerning low efficiency and accuracy of the ridesharing user group discovery in shared transportation environment, a Geo OD-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 Geo OD-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 12 000 taxis in Xi’an, in comparison experiments with Dynamic Time Warping( DTW) algorithm, the accuracy and efficiency of the proposed algorithm was increased by 10. 12% and 1 500% 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.