高级地图匹配算法：研究现状和趋势

于娟; 杨琼; 鲁剑锋; 韩建民; 彭浩

doi:10.12263/DZXB.20200379

您当前的位置：

首页 >

文章列表页 >

高级地图匹配算法：研究现状和趋势

综述评论 | 更新时间：2025-12-08

- 高级地图匹配算法：研究现状和趋势
- Advanced Map Matching Algorithms: A Survey and Trends
- 电子学报 2021年49卷第9期页码：1818-1829
- 作者机构：
  
  1.浙江师范大学数学与计算机科学学院，浙江金华 321004
  2.杭州电子科技大学计算机学院，浙江杭州 310018
- 作者简介：
  
  [ "于　娟　女, 1983年9月出生于湖南省张家界市.现为浙江师范大学数学与计算机科学学院讲师、硕士生导师.主要研究方向为时空数据挖掘、数据隐私保护.E‑mail:yujuan@zjnu.edu.cn" ]
  [ "杨　琼　女, 1982年5月出生于湖南省吉首市.杭州电子科技大学计算机学院博士研究生.主要研究方向为时空数据挖掘、隐私保护.E‑mail:yangqiong525@hdu.edu.cn" ]
  [ "鲁剑锋（通信作者）　男, 1982年10月出生于湖北嘉鱼县.现为浙江师范大学数学与计算机科学学院教授，博士生导师.主要研究方向为群智感知和博弈论.E‑mail:lujianfeng@zjnu.cn" ]
  [ "韩建民　男, 1969年7月出生于辽宁大连.现为浙江师范大学数学与计算机科学学院教授，博士生导师.主要研究方向为数据发布隐私保护.E‑mail:hanjm@zjnu.cn" ]
  [ "彭　浩　男, 1982年12月出生于江苏省泰兴市.现为浙江师范大学校双龙学者特聘教授、硕士生导师，从事网络安全、人工智能安全方面的研究工作.E‑mail:hpeng@zjnu.edu.cn" ]
- 基金信息：
  
  国家自然科学基金(61702148;61672648;62072411;62072412);浙江省自然科学基金(LR21F020001);浙江省教育厅一般项目(Y201941364)
- DOI：10.12263/DZXB.20200379
  中图分类号： TP301.6
- 收稿：2020-04-20，
  
  修回：2021-05-20，
  
  纸质出版：2021-09-25
- 稿件说明：
移动端阅览
于娟,杨琼,鲁剑锋等.高级地图匹配算法：研究现状和趋势[J].电子学报,2021,49(09):1818-1829.

YU Juan,YANG Qiong,LU Jian-feng,et al.Advanced Map Matching Algorithms: A Survey and Trends[J].ACTA ELECTRONICA SINICA,2021,49(09):1818-1829.
于娟,杨琼,鲁剑锋等.高级地图匹配算法：研究现状和趋势[J].电子学报,2021,49(09):1818-1829. DOI： 10.12263/DZXB.20200379.

YU Juan,YANG Qiong,LU Jian-feng,et al.Advanced Map Matching Algorithms: A Survey and Trends[J].ACTA ELECTRONICA SINICA,2021,49(09):1818-1829. DOI： 10.12263/DZXB.20200379.

摘要

地图匹配是许多位置服务与轨迹挖掘应用的基础.随着定位技术和位置服务应用的发展，地图匹配研究不断演进，从早期基于高采样率GPS(Global Position System)的实时匹配，到近期基于低采样率GPS轨迹的离线匹配、再到当前非GPS定位数据或高精度地图匹配。迄今已有许多地图匹配算法相继提出，但鲜有研究对这些算法进行全面总结.为此，对近十年提出的地图匹配算法进行调研，归纳出地图匹配算法的统一框架及常用时空特征.从模型或实现技术角度分类发现：现有算法大都采用HMM(Hidden Markov Model)模型，其次是最大权重模型；深度学习技术近期开始用于地图匹配，将是未来高精度地图匹配研究的趋势.

Abstract

Map matching is a necessary procedure for many trajectory data mining and various location-based applications.Map matching algorithms are continuously evolving with the development of positioning techniques and application requirements.Research on map matching has undergone several stages

from real-time GPS data map matching

to low-sampling rate GPS trajectories offline map matching

to recently non-GPS positioning data or high resolution map matching.Various advanced map matching algorithms have been proposed.However

there is a short of a complete review of recent map matching algorithms.To bridge this gap

this paper conducts a comprehensive survey on map matching algorithms proposed in the last decade.A general framework of map matching algorithms is extracted

and spatial or spatial-temporal features commonly used in these algorithms are summarized.From the technical perspective

the HMM is the most commonly-used model in existing algorithms

before the maximum weights model.The deep learning technique has been recently applied into map matching

and is becoming a future trend for high resolution map matching.

关键词

Keywords

references

GU F Q , HU X K , et al . Indoor localization improved by spatial context⁃a survey [J]. ACM Comput.Surv , 2019 , 52 ( 3 ): 1 - 35 .

WU Y , CHEN P , et al . HTrack: An efficient heading-aided map matching for indoor localization and tracking [J]. IEEE Sensors Journal , 2019 , 19 ( 8 ): 3100 - 3110 .

ZHOU R , TANG M , et al . FreeTrack: device-free human tracking with deep neural networks and particle filtering [J]. IEEE Systems Journal , 2020 , 14 ( 2 ): 2990 - 3000 .

CHEN P , ZHENG X P , et al . Path distance-based map matching for Wi-Fi fingerprinting positioning [J]. Future Generation Computer Systems , 2020 , 107 : 82 - 94 .

FANG S K , ZIMMERMANN R . EnAcq : energy-efficient GPS trajectory data acquisition based on improved map matching[A]. ACM SIGSPATIAL GIS'11 [C]. New York : ACM , 2011 . 221 - 230 .

DONG J X , HICKS C , LI D J . A heuristics based global navigation satellite system data reduction algorithm integrated with map-matching [J]. Annals of Operations Research , 2020 , 290 ( 1 ): 731 - 746 .

GONG X R , HUANG Z , et al . High-performance spatiotemporal trajectory matching across heterogeneous data sources [J]. Future Generation Computer Systems , 2020 , 105 : 148 - 161 .

CHAO P F , HUA W , et al . A survey and quantitative study on map inference algorithms from GPS trajectories [J/OL]. IEEE Transactions on Knowledge and Data Engineering (Early Access) , doi:10.1109/TKDE.2020.2977034 doi:10.1109/TKDE.2020.2977034 , 2020 .

ZONG F , WU T , JIA H . Taxi drivers' cruising patterns—insights from taxi GPS traces [J]. IEEE Transactions on Intelligent Transportation Systems , 2019 , 20 ( 2 ): 571 - 582 .

LI L , JIANG R , et al . Trajectory data-based traffic flow studies: A revisit [J]. Transportation Research Part C: Emerging Technologies , 2020 , 114 : 225 - 240 .

CHEN D , DRIEMEL A , et al . Approximate map matching with respect to the Fréchet distance [A]. ALENEX 2011 [C]. San Francisco : SIAM , 2011 . 75 - 83 .

VELAGA N R , QUDDUS M A , BRISTOW A L . Developing an enhanced weight-based topological map-matching algorithm for intelligent transport systems [J]. Transportation Research Part C: Emerging Technologies , 2009 , 17 ( 6 ): 672 - 683 .

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 .

WEI H , WANG Y , et al . Map matching : Comparison of approaches using sparse and noisy data [A]. ACM SIGSPATIAL GIS'13 [C]. New York : ACM , 2013 . 444 - 447 .

HASHEMI M , KARIMI H A . A critical review of real-time map-matching algorithms: Current issues and future directions [J]. Computers , Environment and Urban Systems, 2014 , 48 : 153 - 165 .

SINGH J , SINGH S , et al . Evaluating the performance of map matching algorithms for navigation systems: an empirical study [J]. Spatial Information Research , 2018 , 27 : 63 - 74 .

KUBICKA M , CELA A , et al . Comparative study and application-oriented classification of vehicular map-matching methods [J]. IEEE Intelligent Transportation Systems Magazine , 2018 , 10 ( 2 ): 150 - 166 .

高文超 , 李国良 , 塔娜 . 轨迹路网匹配算法综述 [J]. 软件学报 , 2018 , 29 ( 2 ): 225 - 250 .

GAO W C , LI G L , TA N . Survey of map matching algorithms [J]. Journal of Software , 2018 , 29 ( 2 ): 225 - 250 . (in Chinese)

KUMAR P , GANTI R K , RAINA G . A new technique to find candidate links for map matching for transportation applications [A]. The 8th International Conference on Communication Systems and Networks [C]. New Jersey, USA : IEEE , 2016 . 1 - 6 .

KOLLER H , WIDHALM P , et al . Fast hidden Markov model map-matching for sparse and noisy trajectories [A]. ITSC 2015 [C]. New Jersey, USA : IEEE , 2015 . 2557 - 2561 .

LI H F , KULIK L , RAMAMOHANARAO K . Spatio-temporal trajectory simplification for inferring travel paths [A]. ACM SIGSPATIALGIS'14 [C]. New York : ACM , 2014 . 63 - 72 .

LIU X L , YU L , et al . ST-PF : Spatio-temporal particle filter for floating-car data pre-processing[A]. (IF&IGIS'17 [C]. Switzerland : Springer , 2018 . 197 - 211 .

RAPPOS E , ROBERT S , CUDRÉ-MAUROUX P . A force-directed approach for offline GPS trajectory map matching [A]. ACM SIGSPATIAL GIS'18 [C]. New York : ACM , 2018 . 319 - 328 .

OSOGAMI T , RAYMOND R . Map matching with inverse reinforcement learning [A]. IJCAI'13 [C]. Palo Alto, California : AAAI , 2013 . 2547 - 2553 .

LOU Y , ZHANG C Y , et al . Map-matching for low-sampling-rate GPS trajectories [A]. ACM SIGSPATIAL GIS'09 [C]. New York : ACM , 2009 . 352 - 361 .

YANG C , GIDÓFALVI G . Fast map matching, an algorithm integrating hidden Markov model with precomputation [J]. International Journal of Geographical Information Science , 2018 , 32 ( 3 ): 547 - 570 .

NEWSON P , KRUMM J . Hidden Markov map matching through noise and sparseness [A]. ACM SIGSPATIAL GIS'09 [C]. New York : ACM , 2009 . 336 - 343 .

GOH C Y , DAUWELS J , et al . Online map-matching based on Hidden Markov model for real-time traffic sensing applications [A]. ITSC'12 [C]. New Jersey, USA : IEEE , 2012 . 776 - 781 .

AN Q , FENG Z , et al . A green self-adaptive approach for online map matching [J]. IEEE Access , 2018 , 6 : 51456 - 51469 .

JAGADEESH G R , SRIKANTHAN T . Online map-matching of noisy and sparse location data with hidden Markov and route choice models [J]. IEEE Transactions on Intelligent Transportation Systems , 2017 , 18 ( 9 ): 2423 - 2434 .

HUANG Y , RAO W , et al . Frequent pattern-based map-matching on low sampling rate trajectories [A]. IEEE MDM'18 [C]. New Jersey, USA : IEEE , 2018 . 266 - 273 .

XU M , DU Y M , et al . Map matching based on conditional random fields and route preference mining for uncertain trajectories [J]. Mathematical Problems in Engineering , 2015 , 717095 : 1 - 13 .

SONG C , YAN X , et al . Hidden Markov model and driver path preference for floating car trajectory map matching [J]. IET Intelligent Transport Systems , 2018 , 12 ( 10 ): 1433 - 1441 .

OZDEMIR E , TOPCU A E , OZDEMIR M K . A hybrid HMM model for travel path inference with sparse GPS samples [J]. Transportation , 2018 , 45 ( 1 ): 233 - 246 .

HU G , Shao J , et al . IF-Matching: towards accurate map-matching with information fusion [J]. IEEE Transactions on Knowledge and Data Engineering , 2017 , 29 ( 1 ): 114 - 127 .

ZHANG Y , HE Y . An advanced interactive-voting based map matching algorithm for low-sampling-rate GPS data [A]. IEEE ICNSC 2018 [C]. New Jersey, USA : IEEE , 2018 . 1 - 7 .

YUAN J , ZHENG Y , et al . An interactive-voting based map matching algorithm [A]. IEEE MDM'10 [C]. New Jersey, USA : IEEE , 2010 . 43 - 52 .

ZHENG K , ZHENG Y , et al . Reducing uncertainty of low-sampling-rate trajectories [A]. IEEE ICDE'12 [C]. New Jersey, USA : IEEE , 2012 . 1144 - 1155 .

XIE Y , ZHOU K , et al . High-accuracy off-line map-matching of trajectory network division based on weight adaptation HMM [J]. IEEE Access , 2020 , 8 : 7256 - 7266 .

WANG G F , ZIMMERMANN R . Eddy : An error-bounded delay-bounded real-time map matching algorithm using HMM and online viterbi decoder[A]. ACM SIGSPATIAL GIS'14 [C]. New York : ACM , 2014 . 33 - 42 .

JAGADEESH G R , SRIKANTHAN T . Probabilistic map matching of sparse and noisy smartphone location data [A]. IEEE ITSC'15 [C]. New Jersey, USA : IEEE , 2015 . 812 - 817 .

YIN Y F , SHAH R R , ZIMMERMANN R . A general feature-based map matching framework with trajectory simplification [A]. ACM SIGSPATIAL IWGS'16 [C]. Burlingame, California, USA : ACM , 2016 . 7 : 1 - 7 : 10 .

LUO L B , HOU X T , et al . Incremental route inference from low-sampling GPS data: An opportunistic approach to online map matching [J]. Information Sciences , 2020 , 512 : 1407 - 1423 .

CHE M L , WANG Y L , et al . An enhanced hidden Markov map matching model for floating car data [J]. Sensors , 2018 , 18 ( 6 ): 1758 .

LIAO L , FOX D , KAUTZ H . Extracting places and activities from GPS traces using hierarchical conditional random fields [J]. The International Journal of Robotics Research , 2007 , 26 ( 1 ): 119 - 134 .

LIU X L , LIU K , 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 .

HUNTER T , ABBEEL P , BAYEN A . The path inference filter: model-based low-latency map matching of probe vehicle data [J]. IEEE Transactions on Intelligent Transportation Systems , 2014 , 15 ( 2 ): 507 - 529 .

YANG J , MENG L Q . Feature selection in conditional random fields for map matching of GPS trajectories [A]. Progress in Location-Based Services 2014 [C]. Switzerland : Springer , 2015 . 121 - 135 .

CHEN B Y , YUAN H , et al . Map-matching algorithm for large-scale low-frequency floating car data [J]. International Journal of Geographical Information Science , 2014 , 28 ( 1 ): 22 - 38 .

CHANDIO A A , TZIRITAS N , et al . An approach for map-matching strategy of GPS-Trajectories based on the locality of road networks [A]. Internet of Vehicles - Safe and Intelligent Mobility [C]. Switzerland : Springer , 2015 . 234 - 246 .

LIU S Y , LIU C , et al . Calibrating large scale vehicle trajectory data [A]. IEEE MDM 2012 [C]. New Jersey, USA : IEEE , 2012 . 222 - 231 .

TUO Y , YUN X , ZHANG Y . MSTM : A novel map matching approach for low-sampling-rate trajectories[A]. IEEE PIMRC 2017 [C]. Montreal, QC, Canada : IEEE , 2017 . 1 - 7 .

HSUEH Y L , CHEN H C . Map matching for low-sampling-rate GPS trajectories by exploring real-time moving directions [J]. Information Sciences , 2018 , 433-434 : 55 - 69 .

NIKOLIĆ M , JOVIĆ J . Implementation of generic algorithm in map-matching model [J]. Expert Systems with Applications , 2017 , 72 : 283 - 292 .

GONG Y J , CHEN E , et al . AntMapper: an ant colony-based map matching approach for trajectory-based applications [J]. IEEE Transactions on Intelligent Transportation Systems , 2018 , 19 ( 2 ): 390 - 401 .

BANERJEE P , RANU S , RAGHAVAN S . Inferring uncertain trajectories from partial observations [A]. IEEE ICDM 2014 [C]. New Jersey, USA : IEEE , 2014 . 30 - 39 .

CHEN C , ZHANG X D , et al . Map-matching based on driver behavior model and massive trajectories [A]. IEEE ITSC2014 [C]. New Jersey, USA : IEEE , 2014 . 2817 - 2822 .

WU H , MAO J Y , et al . Probabilistic robust route recovery with spatio-temporal dynamics [A]. ACM SIGKDD'16 [C]. New York : ACM , 2016 , 1915 - 1924 .

CINTIA P , NANNI M . An effective Time-Aware map matching process for low sampling GPS data [DB/OL].arXiv: 1603.07376 , 2016 .

WU H , SUN W W , Zheng B H . Is only one GPS position sufficient to locate you to the road network accurately [A]. ACM UbiComp'16 [C]. New York : ACM , 2016 . 740 - 751 .

ZHAO K , FENG J , et al . DeepMM : deep learning based map matching with data augmentation[A]. ACM SIGSPATIAL GIS'19 [C]. Chicago : ACM , 2019 . 452 - 455 .

卢家品 , 罗月童 , 等 . 基于排名学习和多源信息的地图匹配方法 [J]. 浙江大学学报(理学版) , 2020 , 47 ( 1 ): 27 - 35, 66 .

LU J P , LUO Y T , et al . An information fusion map matching methond based on ranking learning [J]. Journal of Zhejiang University(Science Edition) , 2020 , 47 ( 1 ): 27 - 35,66 . (in Chinese)

SHEN Z H , DU W , et al . DMM : fast map matching for cellular data[A]. MobiCom'20 [C]. New York : ACM , 2020 . 1 - 14 .

SRIVATSA M , GANTI R , et al . Map matching : facts and myths[A]. ACM SIGSPATIALGIS'13 [C]. New York : ACM , 2013 . 484 - 487 .

RAHMANI M , KOUTSOPOULOS H N . Path inference from sparse floating car data for urban networks [J]. Transportation Research Part C: Emerging Technologies , 2013 , 30 : 41 - 54 .

LI Y , HUANG Q X , et al . Large-scale joint map matching of GPS traces [A]. ACM SIGSPATIAL GIS'13 [C]. New York : ACM , 2013 . 214 - 223 .

KONG X F , YANG J W . A scenario-based map-matching algorithm for complex urban road network [J]. Journal of Intelligent Transportation Systems , 2019 , 23 ( 6 ): 617 - 631 .

孙文彬 , 熊婷 . 历史数据和强化学习相结合的低频轨迹数据匹配算法 [J]. 测绘学报 , 2016 , 45 ( 11 ): 1328 - 1334 .

SUM W B , XIONG T . A low-sampling-rate trajectory matching algorithm in combination of history trajectory and reinforcement learning [J]. Acta Geodaetica et Cartographica Sinica , 2016 , 45 ( 11 ): 1328 - 1334 . (in Chinese)

KRUGER R , SIMEONOV G , et al . Visual interactive map matching [J]. IEEE Transactions on Visualization and Computer Graphics , 2018 , 24 ( 6 ): 1881 - 1892 .

LIANG B W , WANG T J , et al . Online learning for accurate real-time map matching [A]. PAKDD 2016 [C]. Switzerland : Springer , 2016 . 67 - 78 .

TAGUCHI S , KOIDE S , YOSHIMURA T . Online map matching with route prediction [J]. IEEE Transactions on Intelligent Transportation Systems , 2019 , 20 ( 1 ): 338 - 347 .

LI H F , KULIK L , RAMAMOHANARAO K . Robust inferences of travel paths from GPS trajectories [J]. International Journal of Geographical Information Science , 2015 , 29 ( 12 ): 2194 - 2222 .

IMAMICHI T , OSOGAMI T , RAYMOND, R.Truncating shortest path search for efficient map matching [A]. IJCAI 2016 [C]. Palo Alto, California : AAAI , 2016 . 589 - 595 .

高需 , 武延军 , 等 . 基于偏好的个性化路网匹配算法 [J]. 软件学报 , 2018 , 29 ( 11 ): 3500 - 3516 .

GAO X , WU Y J , et al . Personalized map-matching algorithm based on driving preference [J]. Journal of Software , 2018 , 29 ( 11 ): 3500 - 3516 . (in Chinese)

MAAREF M , KASSAS Z M . Ground vehicle navigation in GNSS-Challenged environments using signals of opportunity and a closed-loop map-matching approach [J]. IEEE Transactions on Intelligent Transportation Systems , 2020 , 21 ( 7 ): 2723 - 2738 .

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于噪声标签重加权的车辆轨迹异常检测方法

基于差分隐私的轨迹隐私保护方法

基于FVQ/HMM的无教师说话人自适应