1. School of Computers, Guangdong University of Technology, Guangzhou Guangdong 510006, China; 2. School of Computer Science and Engineering, Nanyang Technological University, Singapore 639798, Singapore
Abstract:Concerning poor matching effect of existing map matching algorithms (such as classical Hidden Markov and its variants, advanced algorithms) for low-frequency trajectory data, a trajectory data mining method based on massive bus historical trajectory data was proposed. Taking bus stations as the sequence skeleton firstly, by mining, extracting, regrouping and sorting trajectory data from a large number of low frequency trajectory points to form high frequency trajectory data, then the high-frequency trajectory data sequence was processed by the map matching algorithm based on classical hidden Markov model to get the bus route map matching results. Compared with the matching method on the low-frequency data not processed by the mining algorithm, the proposed method reduces the matching error by an average of 6.3%, requires smaller data size and costs less time. In addition, this method is robust to low-frequency, unstable noise trajectory data, and it is suitable for map matching of all bus routes.
[1] LU L, CAO N, LIU S, et al. Visual analysis of uncertainty in trajectories[C]//Proceedings of the 18th Pacific-Asia Conference Advances Knowledge Discovery Data Mining. Berlin:Springer, 2014:509-520. [2] NEWSON P, KRUMM J. Hidden Markov map matching through noise and sparseness[C]//Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York:ACM, 2009:336-343. [3] LOU Y, ZHANG C, ZHENG Y, et al. Map-matching for low-sampling-rate GPS trajectories[C]//Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York:ACM, 2009:352-361. [4] JAN-HENRIK H, BENEDIKT B. An algorithm for map matching given incomplete road data[C]//Proceedings of the 20th International Conference on Advances in Geographic Information Systems. New York:ACM, 2012:510-513. [5] LIU X L, LIU K, LI M X, et al. A ST-CRF map-matching method for low-frequency floating car data[J]. IEEE Transactions on Intelligent Transportation Systems, 2017, 18(5):1241-1254. [6] HU G, SHAO J, LIU F L, et al. IF-Matching:towards accurate map-matching with information fusion[J]. IEEE Transactions on Knowledge & Data Engineering, 2016, 29(1):114-127. [7] YUAN J, ZHENG Y, ZHANG C Y, et al. An interactive-voting based map matching algorithm[C]//Proceedings of the 2010 Eleventh International Conference on Mobile Data Management. Washington, DC:IEEE Computer Society, 2010:43-52. [8] HUMMEL B. Map matching for vehicle guidance[M]//Dynamic and Mobile GIS:Investigating Space and Time. Boca Raton, FL:CRC Press, 2006:18-27. [9] ALT H, EFRAT A, ROTE G, et al. Matching planar maps[J]. Journal of Algorithms, 2003, 49(2):262-283. [10] BRAKATSOULAS S, PFOSER D, SALAS R, et al. On map-matching vehicle tracking data[C]//VLDB 2005:Proceedings of the 31st International Conference on Very Large Databases.[S.l.]:VLDB Endowment, 2005:853-864. [11] LAMB P, THIEBAUX S. Avoiding explicit map-matching in vehicle location[C]//ITS-99:Proceedings of the 6th World Conference on Intelligent Transportation Systems. Toronto:[s.n.], 1999:1-9. [12] HOFLEITNER A, HERRING R, ABBEEL P, et al. Learning the dynamics of arterial traffic from probe data using a dynamic Bayesian network[J]. IEEE Transactions on Intelligent Transportation Systems, 2012, 13(4):1679-1693. [13] MATTHEIS S, AL-ZAHID K, ENGELMANN B, et al. Putting the car on the map:a scalable map matching system for the open source community[C]//Proceedings of INFORMATIK 2014:Workshop Automotive Software Engineering. Stuttgart:[s.n.], 2014:2109-2119. [14] 王美玲,程林.浮动车地图匹配算法研究[J].测绘学报,2012,41(1):133-138.(WANG M L, CHENG L, Study on map-matching algorithm for floating car[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(1):133-138.) [15] 曾喆,李清泉,邹海翔,等.曲率积分约束的GPS浮动车地图匹配方法[J].测绘学报,2015,44(10):1167-1176.(ZENG Z, LI Q Q, ZOU H X, et al. Curvature integration constrained map matching method for GPS floating car data[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(10):1167-1176.) [16] 章威,徐建闽,林绵峰.基于大规模浮动车数据的地图匹配算法[J].交通运输系统工程与息,2007,7(2):39-45.(ZHANG W, XU J M, LIN M F. Map matching algorithm of large scale probe vehicle data[J]. Journal of Transportation Systems Engineering and Information Technology, 2007, 7(2):39-45.)