An Improvement on the Topological Map Matching Algorithm at Junctions: A Heuristic Approach

Document Type : Research Paper


1 Faculty of Civil, Water and Environmental Engineering, Shahid Beheshti University

2 Islamic Azad University Science and Research Branch

3 Shahid Beheshti University


Nowadays, there is a growing demand for transportation and location-based services. The rapid progress in wireless and positioning systems caused an ever-increasing use of these systems in vehicles and transportation. Navigation of vehicles relies on matching received positions by Global Positioning System (GPS) or other sensors with the map of road networks to show the user which part of the road they are on. There is a possibility that the algorithm can't recognize the correct link out of the candidate links due to errors in positioning sensors, digital maps, and map matching algorithms. Location-based services, intelligent transportation systems, and users may be misled by incorrect road detection. By combining a topological map-matching algorithm with the Analytic Hierarchy Process (AHP) optimization method, a compound method has been devised. As the material of the study, we have used Garmin GPS data and a 1:2000 urban map of the national cartographic center. We conducted a case study in a dense part of Tehran City in order to test the efficiency of the algorithm. There are three components to the algorithm, one being an initial map match, two being a mapping on a link, and three being a mapping at a junction through the AHP method. The algorithm has been executed in a dense urban network. Because of the presence of high buildings in urban areas we have the most errors in this area. From 906 positioned points the link has been successfully realized in 97.3% of cases. The results are acceptable, and in 2.7% of the remaining cases, error in the positioning system is responsible for the error and it is recommended to improve positioning system errors.


- Ahadi, M., Mahpour, A. and Taraghi, V., 2018. A Combined Fuzzy Logic and Analytical Hierarchy Process Method for Optimal Selection and Locating of Pedestrian Crosswalks. Journal of Optimization in Industrial Engineering, 11(2), pp.79-89.
- Baella, Pla, M., 2005. Reorganizing the Topographic Databases of the Institut Cartogràfic de Catalunya applying generalization 8th ICA Workshop on Generalization and Multiple Representation. A Coruña, July, page 7-8.
- Blazquez C. A., and Vonderohe, A. P., 2005. Simple map-matching algorithm applied to intelligent winter maintenance vehicle data. Transportation Research Recor, Journal of the TransportationResearch Board, vol., page 68-76.
- Chen, W., Yu, M., Li, Z.L., and Chen, Y.Q., 2003. Integrated vehicle navigation system for urban applications. In: Proceedings of International Conference on Global Navigation Satellite Systems (GNSS), Graz, Austria, April 22–24, pp. 15–22.
- Forsi, Hossein, 2013. Moving objects Map-matching in GIS with emphasis on optimization methods. MSc thesis, Science and Research Branch, Islamic Azad University.
- Juan, Y.U., Qiong, Y.A.N.G., Jian-feng, L.U., Jian-min, H.A.N. and Hao, P.E.N.G., 2021. Advanced Map Matching Algorithms: A Survey and Trends. ACTA ELECTONICA SINICA, 49(9), p.1818.
- Huang, Z., Qiao, S., Han, N., Yuan, C.A., Song, X. and Xiao, Y., 2021. Survey on vehicle map matching techniques. CAAI Transactions on Intelligence Technology, 6(1), pp.55-71.
- Kim, J.S., Lee, J.H., Kang, T.H., Lee, W.Y., and Kim, Y.G., 1996. Node based map-matching algorithm for car navigation system. In: Proceedings of 29th International Symposium on Automotive Technology and Automation (ISATA), Florence, Italy, vol. 10, pp. 121–126.
- Li, J., and Fu, M., 2003. Research on route planning and map-matching in vehicle GPS/dead-reckoning/electronic map integrated navigation system. In: Proceedings of IEEE Conference on Intelligent Transportation Systems, pp. 1639–1643.
- Li, Z., and Chen, W., 2005. A new approach to map-matching and parameter correcting for vehicle navigation system in the area of shadow of GPS signal. In: Proceedings of IEEE Conference on Intelligent Transportation Systems, pp. 425–430.
- Mahpour, A., Amiri, A.M., Deldar, M., Saffarzadeh, M. and Nazifi, A., 2018. A heuristic method to determine traffic bottlenecks based on ant colony: A case study of Iran. Case Studies on Transport Policy, 6(4), pp.716-721.
- Mahpour, A., Amiri, P. and Farzin, I., 2021. Prioritizing TOD Indices Using analytic hierarchy process for the case of Tehran Metropolis. Journal of Transportation Research, 18 (2), pp. 81-90
- Mahpour, A., Mamdoohi, A. and Hakimelahi, A., 2020. A heuristic technique for traffic assignment with variable step size and number of iterations. Transportation Research Procedia, 48, pp.2569-2579.
- Meng, Y., and Chen, W., 2002. A simplified map-matching algorithm for in vehicle navigation uni. Annals of GIS, vol. 8, page 24-30.
- Ochieng, W.Y., Quddus, M.A., and Noland, R.B., 2004. Map matching in complex urban road networks. Brazilian Journal of Cartography 55 (2), 1–18.
- Phuyal, B.P., 2002. Method and use of aggregated dead reckoning sensor and GPS data for map matching. In: Proceedings of Institute of Navigation-GPS (ION-GPS) Annual Conference, Portland, pp. 430–437.
- Pyo, J.S., Dong-Ho, S., and Sung, T.K., 2001. Development of a map matching method using the multiple hypothesis technique. In: Proceedings of IEEE Intelligent Transportation Systems Conference, Oakland, Calif., pp. 23–27.
- Quddus, M.A., Ochieng, W.Y. and Noland, R.B., 2007. Current map-matching algorithms for transport applications: State-of-the art and future research directions. Transportation research part c: Emerging technologies, 15(5), pp.312-328.
- Quddus, M.A., Ochieng, W.Y., and Noland, R.B., 2006. A high accuracy fuzzy logic-based map matching algorithm for road transport. Journal of Intelligent Transportation Systems: Technology, Planning, and Operations 10 (3), 103–115.
- Rahbar, M., 2011. Moving objects Map-matching in urban Transportation Networks. MSc thesis, K.N.Toosi University of Technology.
- Syed, S., and Cannon, M.E., 2004. Fuzzy logic-based map matching algorithm for vehicle navigation system in urban canyons. In: Proceedings of Institute of Navigation (ION) National Technical Meeting, California.
- Velaga, Nagendra R., Quddus, M. A., Bristow, and Abigail L., 2009. Developing an enhanced weight-based topological map-matching algorithm for intelligent transport systems. Transportation Research Part C 17: Emerging Technologies, Pages 672–683.
- Velaga, Nagendra R., Quddus, M. A., Bristow, and Abigail L., 2010. Detecting and correcting map-matching errors in location-based Intelligent Transport Systems, Transport Studies Group, Department of Civil and Building Engineering, Loughborough University, Loughborough, Leicestershire, LE11 3TU, UK.
- White, C.E., Bernstein, D., and Kornhauser, A.L., 2000. Some map matching algorithms for personal navigation assistants. Transportation Research Part C: Emerging Technologies 8 (1), page 91–108.
- Yang, D., Cai, B., and Yuan, Y., 2003. An improved map-matching algorithm used in vehicle navigation system. In: Proceedings of IEEE Conference on Intelligent Transportation Systems, pp.1246–1250.
- Yin, H., and Wolfson, O., 2004. A weight-based map matching method in moving objects databases. In: Proceedings of IEEE International Conference on Scientific and Statistical Database Management (SSDBM’04), pp. 437–438.
- Zhang, D., Dong, Y. and Guo, Z., 2021. A turning point-based offline map matching algorithm for urban road networks. Information Sciences, 565, pp.32-45.
- Zhao, K., Yang, Y, and Qu, B., 2003. A Point-Based Map Matching Algorithm for GPS/DR Integrated Navigation Systems. Guidance and Fuze.
- Zhao, L., Ochieng, W.Y., Quddus, M.A., and 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. Journal of Navigation 56, page 257–275.