Annals of Computer Science and Information Systems, Volume 21

DOI: http://dx.doi.org/10.15439/2020F139

Citation: Proceedings of the 2020 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 21, pages 563–566 (2020)

Full text

Abstract. GPS sensors embedded in almost all mobile devices and vehicles generate a large amount of data that can be used in both practical applications and transportation research. Despite the high accuracy of location measurements in 3-5 meters on average, this data can not be used for practical use without preprocessing. The preprocessing step that is needed to identify the correct path as a sequence of road segments by a series of location measurements and road network data is called map matching. In this paper, we consider the offline map matching problem in which the whole trajectory is processed after it has been collected. We propose a map matching algorithm based on a dynamic programming approach. The experimental studies on the dataset collected in Samara, Russia, showed that the proposed algorithm outperforms other comparable algorithms in terms of accuracy.

References

1. A. Agafonov and A. Yumaganov, “Short-term traffic flow forecasting using a distributed spatial-temporal k nearest neighbors model,” in Proceedings - 21st IEEE International Conference on Computational Science and Engineering, CSE 2018, 2018. http://dx.doi.org/10.1109/CSE.2018.00019 pp. 91–98.
2. A. Nagy and V. Simon, “Identifying hidden influences of traffic incidents’ effect in smart cities,” in Proceedings of the 2018 Federated Conference on Computer Science and Information Systems, FedCSIS 2018, 2018. http://dx.doi.org/10.15439/2018F194 pp. 651–658.
3. Y. Amara, A. Amamra, Y. Daheur, and L. Saichi, “A GIS data realistic road generation approach for traffic simulation,” in Proceedings of the 2019 Federated Conference on Computer Science and Information Systems, FedCSIS 2019, 2019. http://dx.doi.org/10.15439/2019F223 pp. 385–390.
4. D. Da Silva, J. Torres, A. Pinheiro, F. De Caldas Filho, F. Mendonca, B. Praciano, G. De Oliveira Kfouri, and R. De Sousa, “Inference of driver behavior using correlated IoT data from the vehicle telemetry and the driver mobile phone,” in Proceedings of the 2019 Federated Conference on Computer Science and Information Systems, FedCSIS 2019, 2019. http://dx.doi.org/10.15439/2019F263 pp. 487–491.
5. V. Myasnikov, “Reconstruction of functions and digital images using sign representations,” Computer Optics, vol. 43, no. 6, pp. 1041–1052, 2019. http://dx.doi.org/10.18287/2412-6179-2019-43-6-1041-1052
6. M. Kubička, A. Cela, H. Mounier, and S. Niculescu, “On designing robust real-time map-matching algorithms,” in 2014 17th IEEE International Conference on Intelligent Transportation Systems, ITSC 2014, 2014. http://dx.doi.org/10.1109/ITSC.2014.6957733 pp. 464–470.
7. C. White, D. Bernstein, and A. Kornhauser, “Some map matching algorithms for personal navigation assistants,” Transportation Research Part C: Emerging Technologies, vol. 8, no. 1-6, pp. 91–108, 2000. http://dx.doi.org/10.1016/S0968-090X(00)00026-7
8. H. Wei, Y. Wang, G. Forman, Y. Zhu, and H. Guan, “Fast Viterbi map matching with tunable weight functions,” in GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems, 2012. http://dx.doi.org/10.1145/2424321.2424430 pp. 613–616.
9. D. Fiedler, M. Čáp, J. Nykl, P. Žilecký, and M. Schaefer, “Map Matching Algorithm for Large-scale Datasets,” https://arxiv.org/abs/1910.05312 [cs, eess], Sep. 2019, https://arxiv.org/abs/ 1910.05312. [Online]. Available: http://arxiv.org/abs/1910.05312
10. Y. Li, Q. Huang, M. Kerber, L. Zhang, and L. Guibas, “Large-scale joint map matching of GPS traces,” in GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems, 2013. http://dx.doi.org/10.1145/2525314.2525333 pp. 214–223.
11. M. Kubicka, A. Cela, H. Mounier, and S.-I. Niculescu, “Comparative Study and Application-Oriented Classification of Vehicular Map-Matching Methods,” IEEE Intelligent Transportation Systems Magazine, vol. 10, no. 2, pp. 150–166, 2018. http://dx.doi.org/10.1109/MITS.2018.2806630 Conference Name: IEEE Intelligent Transportation Systems Magazine.
12. M. Hashemi and H. A. Karimi, “A critical review of real-time map-matching algorithms: Current issues and future directions,” Computers, Environment and Urban Systems, vol. 48, pp. 153–165, Nov. 2014. http://dx.doi.org/10.1016/j.compenvurbsys.2014.07.009
13. D. Srinivasan, R. Cheu, and C. Tan, “Development of an improved ERP system using GPS and AI techniques,” in IEEE Conference on Intelligent Transportation Systems, Proceedings, ITSC, vol. 1, 2003. http://dx.doi.org/10.1109/ITSC.2003.1252014 pp. 554–559.
14. S. Brakatsoulas, D. Pfoser, R. Salas, and C. Wenk, “On map-matching vehicle tracking data,” in VLDB 2005 - Proceedings of 31st International Conference on Very Large Data Bases, vol. 2, 2005, pp. 853–864.
15. H. Yin and O. Wolfson, “A weight-based map matching method in moving objects databases,” in Proceedings of the International Conference on Scientific and Statistical Database Management, SSDBM, vol. 16, 2004, pp. 437–438.
16. L. Li, M. Quddus, and L. Zhao, “High accuracy tightly-coupled integrity monitoring algorithm for map-matching,” Transportation Research Part C: Emerging Technologies, vol. 36, pp. 13–26, Nov. 2013. http://dx.doi.org/10.1016/j.trc.2013.07.009
17. P. Newson and J. Krumm, “Hidden Markov map matching through noise and sparseness,” in GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems, 2009. http://dx.doi.org/10.1145/1653771.1653818 pp. 336–343.
18. R. Raymond, T. Morimura, T. Osogami, and N. Hirosue, “Map matching with Hidden Markov Model on sampled road network,” in Proceedings - International Conference on Pattern Recognition, 2012, pp. 2242–2245.
19. Y. Yin, R. Shah, and R. Zimmermann, “A general feature-based map matching framework with trajectory simplification,” in Proceedings of the 7th ACM SIGSPATIAL International Workshop on GeoStreaming, IWGS 2016, 2016. http://dx.doi.org/10.1145/3003421.3003426
20. C. Yang and G. Gidófalvi, “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. http://dx.doi.org/10.1080/13658816.2017.1400548
21. “GraphHopper library,” Jul. 2020, original-date: 2014-12-10T09:38:00Z. [Online]. Available: https://github.com/graphhopper/map-matching