Advanced Map Matching Algorithms: A Survey and Trends

YU Juan; YANG Qiong; LU Jian-feng; HAN Jian-min; PENG Hao

doi:10.12263/DZXB.20200379

您当前的位置：

首页 >

文章列表页 >

Advanced Map Matching Algorithms: A Survey and Trends

SURVEYS AND REVIEWS | 更新时间：2025-12-08

- Advanced Map Matching Algorithms: A Survey and Trends
- ACTA ELECTRONICA SINICA Vol. 49, Issue 9, Pages: 1818-1829(2021)
- 作者机构：
  
  1.浙江师范大学数学与计算机科学学院，浙江金华 321004
  2.杭州电子科技大学计算机学院，浙江杭州 310018
- 作者简介：
- 基金信息：
- DOI：10.12263/DZXB.20200379
  CLC： TP301.6
- Received：20 April 2020，
  
  Revised：2021-05-20，
  
  Published：25 September 2021
- 稿件说明：
移动端阅览
于娟,杨琼,鲁剑锋等.高级地图匹配算法：研究现状和趋势[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 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

A Vehicle Trajectory Anomaly Detection Method Based on Noise Label Re-Weighting

Trajectory Privacy Protection Method Based on Differential Privacy

Unsupervised Speaker Adaptation Based On FVQ/HMM

Related Author

SU YUE-yang

YAO Di

BI Jing-ping

YUAN Shui-lian

PI De-chang

XU Meng

ZHAO Li

ZOU Cai-rong

Related Institution

University of Chinese Academy of Sciences

Institute of Computing Technology, Chinese Academy of Sciences

College of Computer Science and Technology， Nanjing University of Aeronautics and Astronautics

Department of Radio Engineering,Southeast University

⁰