Using Map Matching Algorithms to Extract Traffic Information from Low Sampling Rate GPS Trajectories

Document Type : Scientific - Research

Authors

1 MSc. Grad., School of Surveying and Geospatial Engineering, College of Engineering, University of Tehran, Tehran, Iran

2 Assistant Professor, School of Surveying and Geospatial Engineering, College of Engineering, University of Tehran, Tehran, Iran

Abstract

GPS, among the various methods of traffic data collection has special popularity due to the low cost and wide access. The primary factor for reliability of determined parameters extracted GPS trajectories is the correct calculation of a vehicle location on a road segment, which is realized by a map-matching algorithm. High percent of GPS trajectories is taken from a variety of sources including mobile GPS, GPS equipped vehicles the, fleet public transport, and social networks are in low sampling rate between 2 to 6 minutes. So determining a suitable map matching algorithm to reduce data errors seems necessary. This paper aims to implement ST-matching and IVVM algorithms to match the GPS tracking data and extract traffic parameters and traffic map by matched trajectories. A special characteristics of ST-matching algorithm is to employ simultaneous spatial, temporal and topology analysis. IVMM algorithm not only considers the spatial and temporal information of a GPS trajectory but also devise a voting-based strategy to model the weighted mutual influences between GPS points. To evaluate these algorithms GPS trajectories with 2 minutes sampling rate of public fleet transport related to bus lines are used. ST-matching algorithm use only one point before each sampling point to match it there for the first point has not any before point, there is no the previous point, so the algorithm is highly dependent on the starting point. IVMM algorithm by modeling mutual influences between GPS points provides more effective and strong result. Distance Weight Function plays an important role in IVMM algorithm. By increasing the value of the parameter beta in Distance Weight function increases map matching accuracy. The obtained accuracy of the method of IVMM and the ST-matching is 88% 73% respectively. The results of this study show the IVMM algorithm outperforms the ST-matching method. Also In the face of U-turn IVMM gives better results.

Keywords

References

- دوباش، الف. (1393) «تطبیق مشاهدات جی. ­پی. ­اس بر نقشه به صورت برون­خط"، پایان نامه  کارشناسی­ارشد، دانشکده مهندسی کامپیوتر، دانشگاه صنعتی­شریف، تهران.
- شهرداری تهران. معاونت وسازمان حمل­و­نقل و ترافیک (1391) «گزارش عملکرد حمل و نقل همگانی»، فصل پنجم عملکرد سامانه اتوبوسرانی، تهران.
- Aung, S. S. and Naing, T. T. (2014) "Mining data for traffic detection system using GPS_Enable mobile phone in mobile cloud infrastructure ", International Journal on Cloud Computing: Services and Architecture (IJCCSA), Vol. 4, No. 3, p. 12.
- Brakatsoulas, S., Pfoser, D., Salas, R. and Wenk, C. (2005) "On map-matching vehicle tracking data", Proceedings of the 31st International Conference on Very Large Data- bases, VLDB Endowment, pp. 853-864.
- Greenfeld, J. S. (2002) "Matching GPS observations to locations on a digital map", Transportation Research Board 81st Annual Meeting, Washington D.C, p.13.
- Kim, S. and Kim, J. (2001) "Adaptive fuzzy-network-based C-measure map-matching algorithm for car navigation system", Industrial Electronics, IEEE Transactions, Vol. 48, No, 2, pp. 432-441.
- Leduc, G. (2008) "Road traffic data: Collection methods and applications", European Commission, Joint Research Center, Institute of Prospective Technological Studies, JRC 47967.
- Li, H., Kulik, L. and Ramamohanarao, K. (2015) "Robust inferences of travel paths from GPS trajectories", International Journal of Geographical Information Science. Vol. 29, No.12, pp. 2194-2222.
- Lou, Y., Zhang, Ch. and Zheng, Y. (2009) "Map-matching for low-sampling-rate GPS trajectories", Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM. p. 352.
- Marchal, F., Hackney, J. and Axhausen, K. W. (2005) "Efficient map matching of large global positioning system data sets: Tests on speed-monitoring experiment in Zürich", Transportation Research Record: Journal of the Transportation Research Board. Vol. 1, No. 1935. pp. 93-100.
- Miwa, T., Kiuchi, D. and Yamamoto, T. (2012) "Development of map matching algorithm for low frequency probe data", Transportation Research Part C: Emerging Technologies, Vol. 22, pp. 132-145.
- Newson, P. and Krumm, J. (2009) "Hidden Markov map matching through noise and sparseness", Proceedings of the 17th ACM SIGSPATIAL International Conference On Advances In Geographic Information Systems, Washington, New York, ACM. pp. 336-343. 
- Quddus, M. A., Ochieng, W. 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. Vol. 15, No. 5, pp. 312-328.
- Rauschert, I., Agrawal, P., Sharma, R., Fuhrmann, S., Brewer, I. and MacEachren, A. (2002) "Designing a human-centered, multimodal GIS interface to support emergency management", Proceedings of the 10th ACM international symposium on Advances in geographic information systems, McLean, Virginia, USA, ACM. pp. 119-124.   
- Syed, S. and Cannon, M. E. (2004) "Fuzzy logic-based map matching algorithm for vehicle navigation system in urban canyons", In Proceedings of the Institute of Navigation (ION) National Technical Meeting, 26-28 January, California, USA.
- Tao, S., Manolopoulos, V., Rodriguez, S. and Rusu, A. (2012) "Real-time urban traffic state estimation with A-GPS mobile phones as probes", Journal of Transportation Technologies. Vol. 2, No. 01, p. 22.
- Wang, D., Wang, Zh., Li, X. and XIAO, Zh. (2014) "A Map Matching Algorithm to Eliminate Miscalculation Based on Low-Sample-Rate Data", 3rd International Conference on Computer Science and Service System, Atlantis Press.
- Wu, D., Zhu, T., Lv, W. and Gao, X. (2007) "A heuristic map-matching algorithm by using vector-based recognition", Computing in the Global Information Technology, 2007. ICCGI 2007, International Multi-Conference on, IEEE. pp. 18-24.
- Yin, H. and Wolfson, O. (2004) "A weight-based map matching method in moving objects databases", Scientific and Statistical Database Management, 2004. Proceedings, 16th International Conference on, Washington, DC, USA, IEEE. pp. 437-438. 
- Yuan, J., Zheng, Y., Zhang, C., Xie, X. and Sun, G-Z. (2010) "An interactive-voting based map matching algorithm", Proceedings of the 2010 Eleventh International Conference on Mobile Data Management, IEEE Computer Society. pp. 43-52.
- Zeng, Z., Zhang, T., Li, Q. and Wu, Z. (2015) "Curvedness feature constrained map matching for low-frequency probe vehicle data" , International Journal of Geographical Information Science, Vol. 30. No. 4, pp. 1-31.
- Zhou, P., Jiang, S. and Li, M .(2015) "Urban Traffic Monitoring with the Help of Bus Riders", Distributed Computing Systems (ICDCS), 2015 IEEE 35th International Conference on, Columbus, OH, USA, IEEE. p. 21-30. 

Files

History

  • Receive Date: 02 March 2016
  • Accept Date: 10 July 2016

Share

How to cite

Statistics