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

Spatio-temporal trajectory retrieval and group discovery in shared transportation

作　　者：段宗涛[1] 龚学辉 唐蕾[1] 陈柘[1] DUAN Zongtao;GONG Xuehui;TANG Lei;CHEN Zhe(School of Information Technology,Chang'an University,Xi'an Shaanxi 710064,China)

机构地区：[1]长安大学信息工程学院,西安710064

出　　处：《计算机应用》2019年第1期220-226,共7页journal of Computer Applications

基　　金：陕西省重点科技创新团队项目(2017KCT-29);陕西省工业科技攻关项目(2016GY078);陕西省重点研发计划项目(2017GY-072)~~

摘　　要：为解决共享交通下的共乘用户群体发现效率低、准确率不高问题,依据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.

关 键 词：共乘出行 群体发现 时空轨迹 3维R树 起讫点 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]