Optimal path planning method based on taxi trajectory data
QI Xin1, LIANG Weitao1, MA Yong2
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
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.
[1] ZHENG Y. Trajectory data mining:an overview[J].ACM Transactions on Intelligent Systems and Technology, 2015, 6(3):29-70. [2] ZHUANG L J, GONG J F, HE Z C, et al. Framework of experienced route planning based on taxis' GPS data[C]//Proceedings of the 15th International IEEE Conference on Intelligent Transportation Systems. Piscataway, NJ:IEEE, 2012:1026-1031. [3] YUAN J, XIE X, ZHENG Y, et al. T-Drive:enhancing driving directions with taxi drivers' intelligence[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(1):220-233. [4] YUAN J, ZHENG Y, ZHANG C Y, et al. T-Drive:driving directions based on taxi trajectories[C]//Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York:ACM, 2010:99-108. [5] 唐炉亮,常晓猛,李清泉.出租车经验知识建模与路径规划[J].测绘学报,2010,39(4):406-412.(TANG L L, CHANG X M, LI Q Q. The knowledge modeling and route planning based on taxi' experience[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(4):406-412.) [6] YUAN J, ZHENG Y, XIE X, et al. Driving with knowledge from the physical world[C]//Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York:ACM, 2011:316-324. [7] VINCENT W Z, ZHENG Y, XIE X, et al. Towards mobile intelligence:learning from GPS history data for collaborative recommendation[J].Artificial Intelligence, 2012, 184(1):17-37. [8] YUAN J, ZHENG Y, ZHANG C Y. An interactive-voting based map matching algorithm[C]//Proceedings of the 11th International Conference on Mobile Data Management. Washington, DC:IEEE Computer Society, 2010:43-52. [9] LI Y, HUANG Q X, KERBER M, et al. Large-scale joint map matching of GPS traces[C]//Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York:ACM, 2013:214-223. [10] LI Q Q, ZENG Z, ZHANG T, et al. Path-finding through flexible hierarchical road networks:an experiential approach using taxi trajectory data[J]. International Journal of Applied Earth, Observation & Geoinformation, 2011, 13(1):110-119. [11] HU J H, HUANG Z, DENG J. A hierarchical path planning method using the experience of taxi drivers[C]//Proceedings of the 13th COTA International Conference of Transportation Professionals. Amsterdam:Elsevier, 2013:1898-1909. [12] QIAO S J, HAN N, ZHU W, et al. TraPlan:an effective three-in-one trajectory prediction model in transportation networks[J]. IEEE Transactions on Intelligent Transportation Systems, 2015, 16(3):1188-1198. [13] QIAO S J, TANG C J, JIN H D, et al. PutMode:prediction of uncertain trajectories in moving objects databases[J]. Applied Intelligence, 2010, 33(3):370-386 [14] LEVENSHTEIN V I. Binary codes capable of correcting deletions, insertions and reversals[J]. Soviet Physics Doklady, 1966, 10(8):707-710. [15] 刘坤,杨杰.基于编辑距离的轨迹相似性度量[J].上海交通大学学报,2009,43(11):1725-1729.(LIU K,YANG J. Trajectory distance metric based on edit distance[J]. Journal of Shanghai Jiao Tong University, 2009, 43(11):1725-1729.) [16] 张翼,唐国金,陈磊.时相关车辆路径规划问题的改进A*算法[J].控制工程,2012,19(5):750-756.(ZHANG Y, TANG G J, CHEN L. Improved A* algorithm for time-dependent vehicle routing problem[J]. Control Engineering, 2012, 19(5):750-756.)
2017, Vol. 37 
