Skip to main content
SpringerLink
Log in

Evaluating the performance of map matching algorithms for navigation systems: an empirical study

  • Published:
Spatial Information Research Aims and scope Submit manuscript

Abstract

Navigation systems are extensively used for location identification and route finding. The efficiency of navigation systems is highly affected by map matching algorithms. This paper provides a review of major map matching algorithms. The performance of reviewed algorithms was further evaluated with the help of an empirical study. A dataset of forty seven kilometers was collected to deploy various map matching algorithms so as to measure their performance. A comparison of geometric, topological and Kalman filter based map matching algorithms was performed on the same dataset. It was concluded that performance of Kalman filter algorithm provide better results in comparison to geometrical and topological algorithms.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10

Similar content being viewed by others

References

  1. Scott, C. A., & Drane, C. (1994). Increased accuracy of motor vehicle position estimation by utilising map data: vehicle dynamics, and other information sources. In Proceedings of the vehicle navigation and information systems conference, 1994 (pp. 585–590). IEEE.

  2. Zhao, Y. (1997). Vehicle location and navigation systems. The Artech House ITS series (2010th ed.). Boston: Artech House. http://www.worldcat.org/title/vehicle-location-and-navigation-systems/oclc/917742102.

  3. Mohammed Quddus, S. W. (2015). Shortest path and vehicle trajectory aided map-matching for low frequency GPS data. Transportation Research Part C: Emerging Technologies, 55, 328. https://doi.org/10.1016/j.trc.2015.02.017.

    Article  Google Scholar 

  4. Naumann, S., & Kovalyov, M. Y. (2017). Pedestrian route search based on open-streetmap. In Intelligent transport systems and travel behaviour (pp. 87–96). Springer.

  5. Quddus, M. A., Ochieng, W. Y., Zhao, L., & Noland, R. B. (2003). A general map matching algorithm for transport telematics applications. GPS Solutions, 7(3), 157–167.

    Article  Google Scholar 

  6. Ochieng, W. Y., Quddus, M. A., & Noland, R. B. (2003). Map-matching in complex urban road networks. Brazilian Journal of Cartography, 55(2), 1. https://dspace.lboro.ac.uk/2134/5484.

    Google Scholar 

  7. Syed, S., & Cannon, M. E. (2004). Fuzzy logic-based map matching algorithm for vehicle navigation system in urban canyons. In ION national technical meeting, San Diego, CA (Vol. 1, pp. 26–28).

  8. Pereira, F. C., Costa, H., & Pereira, N. M. (2009). An off-line map-matching algorithm for incomplete map databases. European Transport Research Review, 1(3), 107–124.

    Article  Google Scholar 

  9. Kim, W., Jee, G. I., & Lee, J. (2000). Efficient use of digital road map in various positioning for its. In Position location and navigation symposium, IEEE 2000 (pp. 170–176). IEEE.

  10. Bernstein, D., & Kornhauser, A. (1998). An introduction to map matching for personal navigation assistants.

  11. Kim, J. (1996). Node based map matching algorithm for car navigation system. In International symposium on automotive technology & automation (29th: 1996: Florence, Italy). Global deployment of advanced transportation telematics/ITS.

  12. Greenfeld, J. S. (2002). Matching gps observations to locations on a digital map. In Transportation research board 81st annual meeting.

  13. Bouju, A., Stockus, A., Bertrand, F., & Boursier, P. (2002). Location-based spatial data management in navigation systems. In Intelligent vehicle symposium, 2002. IEEE (Vol. 1, pp. 172–177). IEEE.

  14. White, C. E., Bernstein, D., & Kornhauser, A. L. (2000). Some map matching algorithms for personal navigation assistants. Transportation Research Part C: Emerging Technologies, 8(1), 91–108.

    Article  Google Scholar 

  15. Blazquez, C., & Vonderohe, A. (2005). Simple map-matching algorithm applied to intelligent winter maintenance vehicle data. Transportation Research Record: Journal of the Transportation Research Board (1935), 68–76.

  16. Krakiwsky, E. J., Harris, C. B., & Wong, R. V. (1988). A kalman filter for integrating dead reckoning, map matching and gps positioning. In Position location and navigation symposium, 1988. Record. Navigation into the 21st Century. IEEE PLANS’88, IEEE (pp. 39–46). IEEE.

  17. Ebner, J. (2001). Dead reckoning and estimated positions. Performance Research, 6(3), 3.

    Article  Google Scholar 

  18. Jimenez, A. R., Seco, F., Prieto, C., & Guevara, J. (2009). A comparison of pedestrian dead-reckoning algorithms using a low-cost mems imu. In IEEE International symposium on intelligent signal processing, 2009. WISP 2009 (pp. 37–42). IEEE.

  19. Taylor, G., Blewitt, G., Steup, D., Corbett, S., & Car, A. (2001). Road reduction filtering for GPS-GIS navigation. Transactions in GIS, 5(3), 193–207.

    Article  Google Scholar 

  20. Srinivasan, D., Cheu, R. L., & Tan, C. W. (2003). Development of an improved erp system using gps and ai techniques. In Proceedings of the intelligent transportation systems, 2003 (Vol. 1, pp. 554–559). IEEE.

  21. Yang, D., Cai, B., & Yuan, Y. (2003). An improved map-matching algorithm used in vehicle navigation system. In Proceedings of the intelligent transportation systems, 2003 IEEE (Vol. 2, pp. 1246–1250). IEEE.

  22. Zhao, L., Ochieng, W. Y., Quddus, M. A., & Noland, R. B. (2003). An extended Kalman filter algorithm for integrating GPS and low cost dead reckoning system data for vehicle performance and emissions monitoring. The Journal of Navigation, 56(2), 257–275.

    Article  Google Scholar 

  23. Loomis, P. V. W. (2018). Vehicle navigation by dead reckoning and GNSS-aided map-matching. US Patent App. 15/270,299.

  24. Meng, Y., Chen, W., Li, Z., Chen, Y., & Chao, J. C. (2002). A simplified map-matching algorithm for in-vehicle navigation unit. Geographic Information Sciences, 8(1), 24–30.

    Google Scholar 

  25. Xu, A., Yang, D., Cao, F., Xiao, W., Law, C., Ling, K., & Chua, H. (2002). Prototype design and implementation for urban area in-car navigation system. In Proceedings of the the IEEE 5th international conference on intelligent transportation systems, 2002 (pp. 517–521). IEEE.

  26. Fu, M., Li, J., & Wang, M. (2003). A hybrid map matching algorithm based on fuzzy comprehensive judgment. In International IEEE conference on intelligent transportation systems (pp. 613–617).

  27. Velaga, N. R., Quddus, M. A., & Bristow, A. L. (2009). Developing an enhanced weight-based topological map-matching algorithm for intelligent transport systems. Transportation Research Part C: Emerging Technologies, 17(6), 672–683.

    Article  Google Scholar 

  28. Kim, S., & Kim, J. H. (2001). Q-factor map matching method using adaptive fuzzy network. In 1999 IEEE international conference on fuzzy systems conference proceedings, 1999. FUZZ-IEEE’99 (Vol. 2, pp. 628–633). IEEE.

  29. El Najjar, M. E., & Bonnifait, P. (2005). A road-matching method for precise vehicle localization using belief theory and Kalman filtering. Autonomous Robots, 19(2), 173–191.

    Article  Google Scholar 

  30. Yanagisawa, H. (2010). An offline map matching via integer programming. In 2010 Proceedings of the 20th international conference on pattern recognition (ICPR) (pp. 4206–4209). IEEE.

  31. Lou, Y., Zhang, C., Zheng, Y., Xie, X., Wang, W., & Huang, Y. (2009). Map matching for low-sampling-rate gps trajectories. In Proceedings of the 17th ACM SIGSPATIAL international conference on advances in geographic information systems (pp. 352–361). ACM.

  32. Sakic, E. (2012). Map-matching algorithms for android applications. Bachelor thesis, Department of Electrical Engineering and Information Technology.

  33. Newson, P., & Krumm, J. (2009). Hidden markov map matching through noise and sparseness. In Proceedings of the 17th ACM SIGSPATIAL international conference on advances in geographic information systems (pp. 336–343). ACM.

  34. Mohamed, R., Aly, H., & Youssef, M. (2014). Accurate and efficient map matching for challenging environments. In Proceedings of the 22nd ACM SIGSPATIAL international conference on advances in geographic information systems (pp. 401–404). ACM.

  35. Mansour, M. F., & Waters, D. W. (2013). Map-assisted Kalman filtering. In 2013 IEEE international conference on acoustics, speech and signal processing (ICASSP) (pp. 3208–3212). IEEE.

  36. Miler, M., Todić, F., & Ševrović, M. (2016). Extracting accurate location information from a highly inaccurate traffic accident dataset: A methodology based on a string matching technique. Transportation Research Part C: Emerging Technologies, 68, 185–193.

    Article  Google Scholar 

  37. Li, Y., Huang, Q., Kerber, M., Zhang, L., Guibas, L. (2013). Large-scale joint map matching of gps traces. In Proceedings of the 21st ACM SIGSPATIAL international conference on advances in geographic in title suppressed due to excessive length 19 formation systems (pp. 214–223). ACM.

  38. Li, L., Quddus, M., & Zhao, L. (2013). High accuracy tightly-coupled integrity monitoring algorithm for map-matching. Transportation Research Part C: Emerging Technologies, 36, 13.

    Article  Google Scholar 

  39. Toledo-Moreo, R., Bétaille, D., & Peyret, F. (2010). Lane-level integrity provision for navigation and map matching with GNSS, dead reckoning, and enhanced maps. IEEE Transactions on Intelligent Transportation Systems, 11(1), 100–112.

    Article  Google Scholar 

  40. Duckworth, D. (2012). Using Kalman filter in python for data prediction. https://pykalman.github.io/. Accessed July 18, 2018.

Download references

Author information

Authors and Affiliations

  1. Department of Computer Applications, CUIET, Chitkara University, Punjab, 140401, India

    Jaiteg Singh

  2. Department of Computer Science Engineering, CUIET, Chitkara University, Punjab, 140401, India

    Saravjeet Singh

  3. Department of CSE, Guru Nanak Dev Engineering College, Ludhiana, India

    Sukhjit Singh

  4. Department of Civil Engineering, Guru Nanak Dev Engineering College, Ludhiana, India

    Hardeep Singh

Authors
  1. Jaiteg Singh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Saravjeet Singh
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Sukhjit Singh
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Hardeep Singh
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jaiteg Singh.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Singh, J., Singh, S., Singh, S. et al. Evaluating the performance of map matching algorithms for navigation systems: an empirical study. Spat. Inf. Res. 27, 63–74 (2019). https://doi.org/10.1007/s41324-018-0214-y

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s41324-018-0214-y

Keywords

Search

Navigation