计算机应用 ›› 2019, Vol. 39 ›› Issue (1): 220-226.DOI: 10.11772/j.issn.1001-9081.2018061291

• 数据科学与技术 • 上一篇    下一篇

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

段宗涛, 龚学辉, 唐蕾, 陈柘   

  1. 长安大学 信息工程学院, 西安 710064
  • 收稿日期:2018-06-21 修回日期:2018-08-14 出版日期:2019-01-10 发布日期:2019-01-21
  • 通讯作者: 唐蕾
  • 作者简介:段宗涛(1977-),男,陕西凤翔人,教授,博士,CCF会员,主要研究方向:服务计算与交通信息服务、交通信息综合处理及应用;龚学辉(1992-),男,河南驻马店人,硕士研究生,主要研究方向:数据挖掘;唐蕾(1983-),女,四川绵阳人,副教授,博士,主要研究方向:智能交通系统、交通信息服务计算;陈柘(1969-),男,陕西凤翔人,副教授,博士,主要研究方向:机器学习、图像处理、计算机视觉。
  • 基金资助:

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

Spatio-temporal trajectory retrieval and group discovery in shared transportation

DUAN Zongtao, GONG Xuehui, TANG Lei, CHEN Zhe   

  1. School of Information Technology, Chang'an University, Xi'an Shaanxi 710064, China
  • Received:2018-06-21 Revised:2018-08-14 Online:2019-01-10 Published:2019-01-21
  • Supported by:

    This work is partially supported by the Key Scientific and Technological Innovation Team of Shaanxi Province (2017KCT-29), the Industrial Science and Technology Research Project of Shaanxi Province (2016GY078), the Key Research and Development Plan of Shaanxi Province (2017GY-072).

摘要:

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

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

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 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 1500% 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)

中图分类号: