计算机工程与应用 ›› 2019, Vol. 55 ›› Issue (13): 239-245.DOI: 10.3778/j.issn.1002-8331.1804-0095

• 工程与应用 • 上一篇    下一篇

基于三维时空轨迹的拼车改进算法研究

张承德,别紫妮   

  1. 中南财经政法大学 信息与安全工程学院,武汉 430073
  • 出版日期:2019-07-01 发布日期:2019-07-01

Research on Improved Carpool Algorithm Based on 3D Space-Time Trajectory

ZHANG Chengde, BIE Zini   

  1. School of Information and Safety Engineering, Zhongnan University of Economics and Law, Wuhan 430073, China
  • Online:2019-07-01 Published:2019-07-01

摘要: 由于私家车数量剧增导致道路拥堵日益严重,拼车作为一种更加环保的出行方式成为人们出行的重要选择。为了提高拼车服务质量,轨迹匹配正成为一个新的研究热点。传统的基于Hausdorff距离的轨迹匹配存在两个问题:只考虑了路径上点的坐标信息,忽略了用户等待时间;直接计算整段路径的Hausdorff距离,无法体现特殊路段对匹配度量的影响。针对上述问题提出两点改进:提出带有时间约束的Hausdorff距离计算方法;提出了一种优化的轨迹匹配方法:用转向点分割原路径,将匹配度量细化到每个子路段。为了评估所提出框架的性能,从Google地图获取到大量中国湖北省武汉市的路线图,实证研究表明,相较于传统的最小完成时间在线模式调度(MCT)算法,所提出的方法能够帮助乘客找到更匹配的轨迹,减少等待时间,从而减少大气污染。

关键词: 时空多媒体分析, 时间约束, 谷歌地图, 拼车

Abstract: As the increasing number of private cars has caused serious traffic jams, carpooling as an environmentally-friendly way has become an important choice for people. In order to improve the quality of carpooling service, trajectory matching becomes a new research hotspot. Generally, there are two problems with the traditional trajectory matching based on Hausdorff distance:only the coordinate information of the point on the path is considered, and the user’s waiting time is ignored; calculating the Hausdorff distance of the entire path directly, which can’t reflect the influence of the special road segment on the matching metrics. This paper proposes two improvements for the above issues:a Hausdorff distance calculation method with time constraints is proposed; an optimized trajectory matching method is proposed:dividing the original path with turning points and refining the matching metrics to each segment. In order to evaluate the performance of the proposed framework, a large number of roadmaps in Wuhan City of the Hubei Province are downloaded from Google map. Empirical studies have shown that compared with the traditional Minimum Completion Time(MCT) online mode scheduling algorithm, the proposed method can help passengers find better matches and reduce waiting time, and thus reducing air pollution.

Key words: spatio-temporal multimedia analysis, time constraint, Google maps, carpool