Map matching algorithm based on massive bus trajectory data mining

doi:10.11772/j.issn.1001-9081.2017123041

Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (7): 1923-1928.DOI: 10.11772/j.issn.1001-9081.2017123041

Previous Articles Next Articles

Map matching algorithm based on massive bus trajectory data mining

CHEN Hui¹, JIANG Guifeng¹, JIANG Guiyuan², WU Jigang¹

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

Received:2017-12-26 Revised:2018-02-08 Online:2018-07-10 Published:2018-07-12
Supported by:
This work is partially supported by the Guangdong Provincial Science and Technology Program (2017A040402009).

基于海量公交轨迹数据挖掘的地图匹配算法

陈辉¹, 蒋圭峰¹, 姜桂圆², 武继刚¹

1. 广东工业大学计算机学院, 广州 510006;
2. 南洋理工大学计算机科学与工程学院, 新加坡新加坡 639798

通讯作者: 蒋圭峰
作者简介:陈辉(1974-),男,广东梅州人,副教授,硕士,主要研究方向:计算机网络、云计算、数据科学;蒋圭峰(1991-),男,江西上饶人,硕士研究生,主要研究方向:机器学习、数据挖掘、数据科学;姜桂圆(1985-),男,山东临沂人,博士,主要研究方向:城市智能交通系统、交通大数据处理、交通资源优化;武继刚(1963-),男,江苏沛县人,教授,博士,CCF会员,主要研究方向:数据科学、网络设计、机器智能、容错计算、软硬件协同设计。
基金资助:
广东省省级科技计划资助项目（2017A040402009）。

Abstract

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.

Key words: bus trajectory data, map matching, data driven, high frequency trajectory data mining

摘要： 针对现有地图匹配算法（如基于经典隐马尔可夫及其变体、先进算法等）对于低频轨迹数据匹配效果不甚理想的问题，提出一种基于海量公交历史轨迹数据的轨迹数据挖掘方法。首先，以公交站点为序列骨架，从大量低频轨迹中挖掘、提取轨迹点数据，进行重组、排序形成高质量高频轨迹数据序列；然后，将高质量高频轨迹数据序列应用基于经典隐马尔可夫模型地图匹配算法，得到公交路线地图匹配结果。与未经过挖掘算法处理的低频轨迹数据的匹配方法相比，所提方法在匹配误差上平均下降6.3%，匹配所需的数据规模、时间大幅缩减；且该方法对于低频、不稳定的噪声数据具有鲁棒性，适用于所有公交路线的地图匹配问题。

关键词: 公交轨迹数据, 地图匹配, 数据驱动, 高频轨迹数据挖掘

CLC Number:

TP301.6

CHEN Hui, JIANG Guifeng, JIANG Guiyuan, WU Jigang. Map matching algorithm based on massive bus trajectory data mining[J]. Journal of Computer Applications, 2018, 38(7): 1923-1928.

陈辉, 蒋圭峰, 姜桂圆, 武继刚. 基于海量公交轨迹数据挖掘的地图匹配算法[J]. 计算机应用, 2018, 38(7): 1923-1928.

References

[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.)

Map matching algorithm based on massive bus trajectory data mining

基于海量公交轨迹数据挖掘的地图匹配算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 5

Recommended Articles

Metrics

[1]	WANG Shuo, WANG Peiliang. Fault detection method for batch process based on deep long short-term memory network and batch normalization [J]. Journal of Computer Applications, 2019, 39(2): 370-375.
[2]	WANG Liwei, WANG Xiaoyi, WANG Li, BAI Yuting, LU Yutian. Distribution analysis method of industrial waste gas for non-detection zone based on bi-directional error multi-layer neural network [J]. Journal of Computer Applications, 2018, 38(5): 1500-1504.
[3]	ZHENG Linjang, LIU Xu, YI Bing. Dynamic weighted real-time map matching algorithm considering spatio-temporal property [J]. Journal of Computer Applications, 2017, 37(8): 2381-2386.
[4]	CHENG Jin, WANG Jian. Endpoint prediction method for steelmaking based on multi-task learning [J]. Journal of Computer Applications, 2017, 37(3): 889-895.
[5]	. Map matching algorithm based on short-term prediction [J]. Journal of Computer Applications, 2010, 30(11): 2910-2913.