Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (7): 2106-2113.DOI: 10.11772/j.issn.1001-9081.2017.07.2106

Previous Articles     Next Articles

Optimal path planning method based on taxi trajectory data

QI Xin1, LIANG Weitao1, MA Yong2   

  1. 1. School of Computer Science and Technology, Wuhan University of Technology, Wuhan Hubei 430063, China;
    2. School of Navigation, Wuhan University of Technology, Wuhan Hubei 430063, China
  • Received:2017-01-13 Revised:2017-02-25 Online:2017-07-10 Published:2017-07-18
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (51579202), the China Postdoctoral Foundation (2015T80848).

基于出租车轨迹数据的最优路径规划方法

戚欣1, 梁伟涛1, 马勇2   

  1. 1. 武汉理工大学 计算机科学与技术学院, 武汉 430063;
    2. 武汉理工大学 航运学院, 武汉 430063
  • 通讯作者: 梁伟涛
  • 作者简介:戚欣(1978-),男,湖北武汉人,副教授,博士,主要研究方向:Web数据挖掘、智能Web系统;梁伟涛(1990-),男,山东临沂人,硕士研究生,主要研究方向:Web数据挖掘、智能交通;马勇(1983-),男,湖北枣阳人,副教授,博士,主要研究方向:智能海事保障技术、无人艇路径规划。
  • 基金资助:
    国家自然科学基金资助项目(51579202);中国博士后基金资助项目(2015T80848)。

Abstract: Focusing on the issue that the path calculated by traditional path planning algorithm is not necessarily the optimal path in reality, a path planning algorithm which combined the experience of taxi driving and took time as a measure was proposed. The implementation of this algorithm was to transform the path planning technology which took calculation as the center into data-driven mining technology which regarded data as the center. Firstly, the real manned trajectory data were extracted from a large number of taxi trajectory data and matched to the road network data. Then, the access frequency of the road segments were calculated according to the calculation results of map-matching, and Top-k road sections were selected as hot sections; Secondly, the similarity of road tracks between hot sections was calculated, and the trajectories were clustered to build k sections of hot road map based on the road network. Finally, an improved A* algorithm was used to calculate the optimal path. The experimental results show that compared with the traditional shortest path planning algorithm and the path planning algorithm based on hierarchical road network, the path planning method based on hot section map can shorten the length of the planning path and the travel time and improve the time efficiency of path planning.

Key words: intelligent transportation, taxi driving experience, improved A* algorithm, hot section map, path planning

摘要: 针对传统的路径规划算法并不一定能计算得到现实中最优路径的问题,提出一种融合了出租车驾驶经验并以时间为度量的路径规划算法。该算法的实现是将路径规划这个以计算为中心的技术变为以数据为中心的数据驱动挖掘技术。首先,从大量的出租车轨迹数据中提取真实的载人轨迹数据,并将载人轨迹数据匹配到路网数据中;然后,根据地图匹配结果计算路段的访问频次,选取前Top-k个路段作为热点路段;其次,计算热点路段间行车轨迹的相似度,对轨迹进行聚类分析,在路网的基础上构建该k个路段的热点路段图;最后,使用一种改进的A*算法实现路径规划。实验结果表明,与传统的最短路径规划算法和基于驾驶经验路网分层的路径规划算法相比,所提出的基于热点路段图的路径规划方法有效地缩短规划路径的长度及路径行驶时间,提高路径规划的用时效率。

关键词: 智能交通, 出租车驾驶经验, 改进A*算法, 热点路段图, 路径规划

CLC Number: