Locating devices on the road network is crucial for any location-based system. Accuracy of map matching algorithms may highly affect the accuracy of any location-based service. This paper includes an empirical review of five major map matching algorithms for locating a device on a digital road network. A standard dataset was used to simulate the working of map matching algorithms. After ascertaining the accuracy of map matching algorithms, it was tested on a real road network. Six different routes varying from 0.6 kilometers to 32 kilometers, covering a total distance of 82.2 kilometers were included in the experiment. Performance of map matching algorithms was evaluated on a total of 2094 road nodes with 1271070 Global Positioning System (GPS) points on the basis of matched, unmatched nodes with root mean square error. It was concluded that Hidden-Markov Model based map matching algorithms has reasonably good accuracy (96% using global data and 89% using Indian dataset) and execution time in comparison to geometric, topological, Kalman filter and Frechet distance based algorithms.

[1] Ali A. and Schmid F., “Data Quality Assurance for Volunteered Geographic Information,” in Proceedings of International Conference on Geographic Information Science, Vienna, pp. 126-141, 2014.

[2] Alt H. and Godau M., “Computing the Fréchet Distance Between Two Polygonal Curves,” International Journal of Computational Geometry and Applications, vol. 5, no. 1, pp. 75-91, 1995.

[3] Arregui H., Loyo E., Otaegui O., and Arbelaitz O., “Impact of The Road Network Configuration on Map-Matching Algorithms for FCD in Urban Environments,” IET Intelligent Transport Systems, vol. 12, no. 1, pp. 12-21, 2018.

[4] Asadi R., Kareem S., Asadi M. and Asadi S., “An Unsupervised Feed Forward Neural Network Method for Efficient Clustering,” The International Arab Journal of Information Technology, vol. 14, no. 4, pp. 436-441, 2017.

[5] Atia M., Hilal A., Stellings C., Hartwell E., Toonstra J., Miners W., and Basir O., “A Low- Cost Lane-Determination System Using GNSS/IMU Fusion and HMM-Based Multistage Map Matching,” IEEE Transactions on Intelligent Transportation Systems, vol. 18, no. 11, pp. 3027-3037, 2017.

[6] Bernstein D. and Kornhauser A., An Introduction to Map Matching for Personal Navigation Assistants, New Jersey TIDE Center, New Jersey, 1998.

[7] Bierlaire M., Chen J., and Newman J., “A Probabilistic Map Matching Method for Smartphone GPS Data,” Transportation Research Part C: Emerging Technologies, vol. 26, pp. 78-98, 2013.

[8] El Najjar M. and Bonnifait P., “A Road- Matching Method for Precise Vehicle Localization Using Belief Theory and Kalman Filtering,” Autonomous Robots, vol. 19, no. 2, pp. 173-191, 2005.

[9] Gong Y., Chen E., Zhang X., Ni L., and Zhang J., “AntMapper: An ant Colony-Based Map Matching Approach for Trajectory-Based Applications,” IEEE Transactions on Intelligent Transportation Systems, vol. 19, no. 2, pp. 390- 401, 2017.

[10] Jagadeesh G. and Srikanthan T., “Online Map- Matching of Noisy and Sparse Location Data With Hidden Markov and Route Choice Models,” IEEE Transactions on Intelligent Transportation Systems, vol. 18, no. 9 pp. 2423- 2434, 2017.

[11] Kassas Z., Maaref M., Morales J., Khalife J., and Shamei K., “Robust Vehicular Localization and Map Matching in Urban Environments Through IMU, GNSS, and Cellular Signals,” IEEE Intelligent Transportation Systems Magazine, vol. 12, no. 3, pp. 36-52, 2020.

[12] Kim W., Jee G., and Lee J., “Efficient Use of Digital Road Map in Various Positioning for ITS,” in Proceedings of IEEE Position Location and Navigation Symposium, San Diego, pp. 170- 176, 2000.

[13] Kubička M., Cela A., Moulin P., Mounier H., and Niculescu S., “Dataset for Testing and Training of Map-Matching Algorithms,” in Proceedings of IEEE Intelligent Vehicles Symposium, Seoul, pp. 1088-1093, 2015.

[14] Li L., Quddus M., and Zhao L., “High Accuracy Tightly-Coupled Integrity Monitoring Algorithm for Map-Matching,” Transportation Research 148 The International Arab Journal of Information Technology, Vol. 19, No. 2, March 2022 Part C: Emerging Technologies, vol. 36, pp. 13- 26, 2013.

[15] Liu X., Liu K., Li M., and Lu F., “A ST-CRF Map-Matching Method for Low-Frequency Floating Car Data,” IEEE Transactions on Intelligent Transportation Systems, vol. 18, no. 5, 1241-1254, 2017.

[16] Lou Y., Zhang C., Zheng Y., Xie X., Wang W., and Huang Y., “Map-Matching for Low- Sampling-Rate GPS Trajectories,” in Proceedings of 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Seattle, pp. 352-361, 2009.

[17] Meng Y., Chen W., Li Z., Chen Y., and Chao J., “A Simplified Map-Matching Algorithm for in- Vehicle Navigation Unit,” Geographic Information Sciences, vol. 8, no. 1, pp. 24-30, 2002.

[18] Miler M., Todić F., and Ševrović M., “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, vol. 68, pp. 185-193, 2016.

[19] Mohamed R., Aly H., and Youssef M., “Accurate and Efficient Map Matching for Challenging Environments,” in Proceedings of 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Dallas, pp. 401-404, 2014.

[20] Mohamed R., Aly H., and Youssef M., “Accurate Real-Time Map Matching for Challenging Environments,” IEEE Transactions on Intelligent Transportation Systems, vol. 18, no. 4, pp. 847- 857, 2017.

[21] Mooney P. and Corcoran P., “Using OSM for LBS-an Analysis of Changes to Attributes of Spatial Objects,” in Proceedings of Advances in Location-Based Services, Berlin, pp. 165-179, 2012.

[22] Naumann S. and Kovalyov M., “Pedestrian route Search Based on Open Street Map,” in Proceedings of Intelligent Transport Systems and Travel Behaviour, Katowice, pp. 87-96 2017.

[23] Newson P. and Krumm J., “Hidden Markov Map Matching Through Noise and Sparseness,” in Proceedings of 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Seattle, pp. 336-343, 2009.

[24] Quddus M., Ochieng W., and Noland R., “Current Map-Matching Algorithms for Transport Applications: State-of-The Art and Future Research Directions,” Transportation Research Part C: Emerging Technologies, vol. 15, no. 5, pp. 312-328, 2017.

[25] Shalaby M., Mohammed A., and Kassem S., “Supervised Fuzzy C-Means Techniques to Solve the Capacitated Vehicle Routing Problem,” The International Arab Journal of Information Technology, vol. 18, no. 3A, pp. 452-463, 2021.

[26] Singh S. and Singh J., Fog, Edge, and Pervasive Computing in Intelligent IoT Driven Applications, Wiley-IEEE Press, 2020.

[27] Singh S., Singh J., and Sehra S., “Genetic- Inspired Map Matching Algorithm for Real- Time GPS Trajectories,” Arabian Journal for Science and Engineering, vol. 45, pp. 2587- 2603, 2020.

[28] Ta N., Wang J., and Li G., “Map Matching Algorithms: An Experimental Evaluation,” in Proceedings of Asia-Pacific Web (APWeb) and Web-Age Information Management (WAIM) Joint International Conference on Web and Big Data, Macau, pp. 182-198, 2018.

[29] Taguchi S., Koide S., and Yoshimura T., “Online Map Matching with Route Prediction,” IEEE Transactions on Intelligent Transportation Systems, vol. 20, no. 1, pp. 338-347, 2018.

[30] Velaga N., Quddus M., and Bristow A., “Developing an Enhanced Weight-Based Topological Map-Matching Algorithm for Intelligent Transport Systems,” Transportation Research Part C: Emerging Technologies, vol. 17, no. 6, pp. 672-683, 2009.

[31] Xu H., Liu H., Tan C., and Bao Y., “Development and Application of an Enhanced Kalman Filter and Global Positioning System Error-Correction Approach for Improved Map- Matching,” Journal of Intelligent Transportation Systems, vol. 14, no. 1, pp. 27-36, 2010.

[32] Xu Z., Li Y., Rizos C., and Xu X., “Novel hybrid of LS-SVM and Kalman Filter for GPS/INS Integration,” The Journal of Navigation, vol. 63, no. 2, pp. 289-299, 2010.

[33] Yang C. and Gidofalvi G., “Fast Map Matching: an Algorithm Integrating Hidden Markov Model with Precomputation,” International Journal of Geographical Information Science, vol. 32, no. 3, pp. 547-570, 2018.

[34] Yang H., Cheng S., Jiang H., and An S., “An Enhanced Weight-Based Topological Map Matching Algorithm for Intricate Urban Road Network,” Procedia-Social and Behavioral Sciences, vol. 96, pp. 1670-1678, 2013.

[35] Yue Y., Zhao C., Wen M., Wu Z., and Wang D., “Collaborative Semantic Perception and Relative Localization Based on Map Matching,” in Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, Las Vegas, pp. 6188-6193, 2020.

[36] Zeng Z., Zhang T., Li Q., Wu Z., Zou H., and Gao C., “Curvedness Feature Constrained Map Matching for Low-Frequency Probe Vehicle Map Matching Algorithm: Empirical Review Based on Indian OpenStreetMap Road Network Data 149 Data,” International Journal of Geographical Information Science, vol. 30, no. 4, pp. 660-690, 2016.

[37] Zhang H., Luo Y., Yu Q., Zheng X., and Li X., “Map-Matching Approach Based on Link Factor and Hidden Markov Model,” Journal of Intelligent and Fuzzy Systems Preprint, vol. 40, no. 3, pp. 5455-5471, 2021.

[38] Zhang Y. and Sui X., “RCIVMM: A Route Choice-based Interactive Voting Map Matching Approach for Complex Urban Road Networks,” IEEE Transactions on Big Data, vol. 1, 2021.

[39] Zhang, D., Dong Y., and Guo Z., “A Turning Point-Based Offline Map Matching Algorithm for Urban Road Networks,” Information Sciences, vol. 565, pp. 32-45, 2021.

[40] Zhao X., Cheng X., Zhou J., Xu Z., Dey N., Ashour A., and Satapathy S., “Advanced Topological Map Matching Algorithm Based on D-S Theory,” Arabian Journal for Science and Engineering, vol. 43, no. 8, pp. 3863-3874, 2018.