一种面向海量浮动车数据的地图匹配方法

doi:10.3724/SP.J.1047.2015.01143

Abstract

Abstract:

Floating Car Data (FCD) has been widely applied into traffic supervision, smart travelling, urban planning and so forth. Map-matching is one of the key technologies of FCD, for current map-matching algorithms, it is difficult to improve their map-matching efficiency considerably with a guaranteed accuracy. To solve this problem, our research proposes a map-matching model based on Hidden Markov Model (HMM), and makes a variety of improvements compared with the traditional model: (1) in addition to the position information, it introduces the heading angle variable to emission probability calculation, and discusses its influences on model accuracy and how to set a reasonable weight; (2) it divides road network according to a square grid, constructs candidate road segments searching algorithm based on hash index, and then discusses the optimization approach of the candidate road segment collection; (3) the numbers of segments in the path is used as the measurement for transition probability computation instead of the practical length, which simplifies the calculation procedure; (4) by preprocessing the road net, it constructs a road segment transition matrix according to the characteristic that floating cars have a limited scope of space activities in a given time, which realizes the fast calculation of road segment transition probability and reduces the time complexity of road matching calculation to a significant extent. We have applied this map-matching model in analyzing Beijing taxis’ trajectory data, in which the sampling time interval varies from 1 s to 120 s. The result demonstrates that this model is practicable, the required road segment transition matrix can be constructed in affordable space cost, and its efficiency is improved significantly with the condition that the accuracy meets the application requirements, which makes the model more applicable for massive FCD map-matching. As a conclusion, the proposed model has a high application value for multiple cases.

Key words: FCD, map matching, HMM, grid, road segment transition matrix

WANG Xiaomeng,CHI Tianhe,LIN Hui,SHAO Jing,YAO Xiaojing,YANG Lina. A Research of Map-Matching Method for Massive Floating Car Data[J].Journal of Geo-information Science, 2015, 17(10): 1143-1151.DOI:10.3724/SP.J.1047.2015.01143

Figures/Tables 12

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Tab. 1

Static data scale"

名称	键值对组织方式	规模（万条）	占用空间（MB）
路网邻接矩阵	$rs, NS$	12.48	2.7
网格-子路段关系	$grid, SS$	28.84	5.8
子路段-路段关系	$ss, rs$	58.39	7.9
有限路段转移集合	$s i, s j, d i j, p i j$	4000	847

Tab. 1

Fig. 6

Fig. 7

Fig. 8

Fig. 9

Fig. 10

Tab. 2

References 20

[1]	Yuan Y F, Van Lint H, Van Wageningen-Kessels F, et al. Network-wide traffic state estimation using loop detector and floating car data[J]. Journal of Intelligent Transportation Systems, 2014,18(1):41-50.
[2]	Yuan J, ZhengY, Xie X, et al. T-Drive: Enhancing driving directions with taxi drivers' intelligence[J]. IEEE Transactions on Knowledge and Data Engineering, 2013,26(1):220-232.
[3]	Mori U, Mendiburu A, Álvarez M, et al.A review of travel time estimation and forecasting for advanced traveller information systems[J]. Transportmetrica a-Transport Science, 2015,11(2):119-157.
[4]	Yuan N J, Zheng Y, Xie X, et al.Discovering urban functional zones using latent activity trajectories[J]. IEEE Transactions on Knowledge and Data Engineering, 2015,27(3):712-725.
[5]	Quddus M A, Ochieng W Y, Noland R B.Current map-matching algorithms for transport applications: State-of-the art and future research directions[J]. Transportation Research Part C:Emerging Technologies, 2007,15(5):312-328.
[6]	Marchal F, Hackney J, Axhausen K.Efficient map matching of large global positioning system data sets: Tests on speed-monitoring experiment in zürich[J]. Transportation Research Record: Journal of the Transportation Research Board, 2005,1935:93-100.
[7]	Pyo J S, Shin D H, Sung T K.Development of a map matching method using the multiple hypothesis technique[C]. Proceedings of IEEE Intelligent Transportation Systems, 2001:23-27.
[8]	Raymond R, Morimura T, Osogami T.Map matching with Hidden Markov Model on sampled road network[C]. Pattern Recognition (ICPR), IEEE, 2012:2242-2245.
[9]	章威,徐建闽,林绵峰.基于大规模浮动车数据的地图匹配算法[J].交通运输系统工程与信息,2007,7(2):39-45.
[10]	李宇光,李清泉.利用地图栅格化的海量浮动车数据道路匹配快速算法[J].武汉大学学报(信息科学版),2014,39(6):724-728,733.
[11]	Lou Y, Zhang C Y, Zheng Y, et al.Map-matching for low-sampling-rate GPS trajectories[C]. ACM SIGSPATIAL GIS, 2009:352-361.
[12]	Newson P, Krumm J.Hidden Markov map matching through noise and sparseness[C]. Workshop on Advances in Geographic Information Systems, 2009:336-343.
[13]	Goh C Y, Dauwels J, Mitrovic N, et al.Online map-matching based on Hidden Markov model for real-time traffic sensing applications[C]. 15th International IEEE Conference on Intelligent Transportation Systems (ITSC), 2012:776-781.
[14]	李清泉,黄练.基于GPS轨迹数据的地图匹配算法[J].测绘学报,2010,39(2):207-212.
[15]	Chen B Y, Yuan H, Li Q Q.Map-matching algorithm for large-scale low-frequency floating car data[J]. International Journal of Geographical Information Science, 2014,28(1):22-38.
[16]	Brakatsoulas S, Pfoser D, Salas R, et al.On map-matching vehicle tracking data[C]. In Proc. 31st VLDB Conference, 2005:853-864.
[17]	Wang W, Jin J, Ran B, et al.Large-scale freeway network traffic monitoring: A map-matching algorithm based on low-logging frequency GPS probe data[J]. Journal of Intelligent Transportation Systems, 2011,15(2):63-74.
[18]	He Z C, She X W, Zhuang L J, et al.On-line map-matching framework for floating car data with low sampling rate in urban road networks[J]. IET Intelligent Transport Systems, 2013,7(4):404-414.
[19]	Gutierrez E, Medaglia A L.Labeling algorithm for the shortest path problem with turn prohibitions with application to large-scale road networks[J]. Annals of Operations Research, 2008,157(1):169-182.
[20]	Miwa T, Kiuchi D, Yamamoto T, et al.Development of map matching algorithm for low frequency probe data[J]. Transportation Research Part C: Emerging Technologies, 2012,22:132-145.

算法类型	路段查找(s)	路径匹配(s)	总耗时(s)	平均(点/s)
传统模型	20.73	43.69	64.42	817.83
本文模型	5.89	0.63	6.52	6219.11

A Research of Map-Matching Method for Massive Floating Car Data

RichHTML

PDF (PC)

Like

Knowledge

Cited

Abstract

Cite this article

share this article

Figures/Tables 12

References 20

Related Articles 15

Metrics

Comments

Recommended 0

[1]	LIAN Licong, WAN Zhiwei, JU Min, JIA Yulian, HONG Yijun, JIANG Meixin, ZENG Fenghai. Reconstruction of the Cropland Area and Its Spatial Distribution Pattern at Dongting Lake District of Hunan Province in the Middle of the Republic of China [J]. Journal of Geo-information Science, 2020, 22(5): 989-996.
[2]	ZHANG Xingang, YAN Haowen, ZHANG Liming. A Perceptual Hash Algorithm for DEM Data Authentication and Tamper Localization [J]. Journal of Geo-information Science, 2020, 22(3): 379-388.
[3]	HUANG Nan, YANG Xin, LIU Hailong. A Method of Saddle Point Extraction based on Contour Spatial Relationship [J]. Journal of Geo-information Science, 2020, 22(3): 410-421.
[4]	ZHENG Shichen, SHENG Yehua, LV Haiyang. Vehicle Trajectory-map Matching based on Particle Filter [J]. Journal of Geo-information Science, 2020, 22(11): 2109-2117.
[5]	LI Yatong, ZHANG Lijun, YE Shilin, QI Xinhua. Improvement and Application of Two-dimensional Fractal Model of Urban Growth and Morphology [J]. Journal of Geo-information Science, 2020, 22(11): 2140-2151.
[6]	CUI Xiaolin, ZHANG Jiabei, WU Feng, ZHANG Qian, WU Yaohui. Spatio-temporal Analysis of Population Dynamics based on Multi-source Data Integration for Beijing Municipal City [J]. Journal of Geo-information Science, 2020, 22(11): 2199-2211.
[7]	WANG Jinxin,ZHAO Guangcheng,LU Fengnian,ZHANG Gubin,ZENG Tao,QIAO Tianrong. Sphere Geodesic Octree Grid Method for True Three-Dimensional Geological Model Construction [J]. Journal of Geo-information Science, 2019, 21(8): 1161-1169.
[8]	Jian PENG, Feixiong XU. Effect of Grid Size on Habitat Quality Assessment: A Case Study of Huangshan City [J]. Journal of Geo-information Science, 2019, 21(6): 887-897.
[9]	SHI Guoping, HE Yongjian, ZHANG Mei, QIU Xinfa, ZENG Yan. Spatial Distribution of THI in Zhejiang Province based on the GridMet Model [J]. Journal of Geo-information Science, 2019, 21(12): 1923-1933.
[10]	LIU Lin, JI Jiakai, SONG Guangwen, LIAO Weiwei, YU Hongjie, LIU Wenjuan. Hotspot Prediction of Public Property Crime based on Spatial Differentiation of Crime and Built Environment [J]. Journal of Geo-information Science, 2019, 21(11): 1655-1668.
[11]	HU Zengzeng,ZHAO Zhilong,ZHANG Guixiang. Simulation and Projection of the Spatial Pattern of the Population in Beijing under the Background of Non-capital Function Extraction [J]. Journal of Geo-information Science, 2018, 20(2): 205-216.
[12]	XU Zhen,JING Yaodong,BI Rutian,GAO Yang,WANG Peng. The Discovery of Spatial Association Patterns of Resource and Environment Information Based on Grid Data [J]. Journal of Geo-information Science, 2018, 20(1): 28-36.
[13]	ZHAO Tongtong,SONG Bangguo,CHEN Yuansheng,YAN Huimin,XU Zengrang. Analysis of Population Distribution and Its Spatial Relationship with Terrain Elements in the Yarlung Zangbo River, Nyangqu River and Lhasa River Region, Tibet [J]. Journal of Geo-information Science, 2017, 19(2): 225-237.
[14]	LI Xiang,CHEN Zhenjie,WU Jiexuan,WANG Wenxiang,QU Lean,ZHOU Chen,HAN Xiaofeng. Gridding Methods of City Permanent Population Based on Night Light Data and Spatial Regression Models [J]. Journal of Geo-information Science, 2017, 19(10): 1298-1305.
[15]	WU Yong,YAO Ling,TONG Weimin. A New Image Retrieval Method Based on Image Viewshed [J]. Journal of Geo-information Science, 2016, 18(8): 1030-1036.