Erin Chambers
Brittany Terese Fasy
Abstract
We consider several variants of the map-matching problem, which seeks to find a path Q in graph G that has the smallest distance to a given trajectory P (which is likely not to be exactly on the graph). In a typical application setting, P models a noisy GPS trajectory from a person traveling on a road network, and the desired path Q should ideally correspond to the actual path in G that the person has traveled. Existing map-matching algorithms in the literature consider all possible paths in G as potential candidates for Q. We find solutions to the map-matching problem under different settings. In particular, we restrict the set of paths to shortest paths, or concatenations of shortest paths, in G. As a distance measure, we use the Fréchet distance, which is a suitable distance measure for curves since it takes the continuity of the curves into account.
- Mahmuda Ahmed and Carola Wenk. 2012. Constructing street networks from GPS trajectories. In Proceedings of the 20th Annual European Symposium on Algorithms. 60--71.Google Scholar
Digital Library
- Helmut Alt, Alon Efrat, Günter Rote, and Carola Wenk. 2003. Matching planar maps. Journal of Algorithms 49 (2003), 262--283.Google ScholarDigital Library
- Helmut Alt and Michael Godau. 1995. Computing the Fréchet distance between two polygonal curves. International Journal of Computational Geometry 8 Applications 5 (1995), 75--91.Google ScholarCross Ref
- Theo A. Arentze and Harry J. P. Timmermans. 2004. A learning-based transportation oriented simulation system. Transportation Research Part B: Methodological 38, 7 (2004), 613--633. DOI:https://doi.org/10.1016/j.trb.2002.10.001Google ScholarCross Ref
- Michael Balmer, Kay Axhausen, and Kai Nagel. 2006. Agent-based demand-modeling framework for large-scale microsimulations. Transportation Research Record: Journal of the Transportation Research Board 1985 (2006), 125--134. DOI:https://doi.org/10.3141/1985-14Google ScholarCross Ref
- Sotiris Brakatsoulas, Dieter Pfoser, Randall Salas, and Carola Wenk. 2005. On map-matching vehicle tracking data. In Proceedings of the 31st Conference on Very Large Data Bases (VLDB’05). 853--864.Google ScholarDigital Library
- Erin W. Chambers, Brittany Terese Fasy, Yusu Wang, and Carola Wenk. 2018. Map-matching using shortest paths. In Proceedings of the 3rd International Workshop on Interactive and Spatial Computing. 44--51.Google ScholarDigital Library
- Ron Dalumpines and Darren M. Scott. 2017. Determinants of route choice behavior: A comparison of shop versus work trips using the potential path area--gateway (PPAG) algorithm and path-size logit. Journal of Transport Geography 59 (2017), 59--68. DOI:https://doi.org/10.1016/j.jtrangeo.2017.01.003Google ScholarCross Ref
- Maurice Fréchet. 1906. Sur quelques points du calcul fonctionnel. Rendiconti del Circolo Matematico di Palermo 22, 1 (1906), 1--74.Google Scholar
- Amin Gheibi, Anil Maheshwari, and Jörg-Rüdiger Sack. 2016. Minimizing walking length in map matching. In Proceedings of the International Conference on Topics in Theoretical Computer Science. 105--120.Google ScholarCross Ref
- Mithilesh Jha, Samer Madanat, and Srinivas Peeta. 1998. Perception updating and day-to-day travel choice dynamics in traffic networks with information provision. Transportation Research Part C: Emerging Technologies 6, 3 (1998), 189--212. DOI:https://doi.org/10.1016/S0968-090X(98)00015-1Google ScholarCross Ref
- Antonio Lima, Rade Stanojevic, Dina Papagiannaki, Pablo Rodriguez, and Marta C. González. 2016. Understanding individual routing behaviour. Journal of the Royal Society Interface 13, 16 (2016), 20160021. DOI:https://doi.org/10.1098/rsif.2016.0021Google ScholarCross Ref
- Yin Lou, Chengyang Zhang, Yu Zheng, Xing Xie, Wei Wang, and Yan Huang. 2009. Map-matching for low-sampling-rate GPS trajectories. In Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. 352--361.Google ScholarDigital Library
- E. J. Manley, J. D. Addison, and T. Cheng. 2015. Shortest path or anchor-based route choice: A large-scale empirical analysis of minicab routing in London. Journal of Transport Geography 43 (2015), 123--139. DOI:https://doi.org/10.1016/j.jtrangeo.2015.01.006Google ScholarCross Ref
- Paul Newson and John Krumm. 2009. Hidden Markov map matching through noise and sparseness. In Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. 336--343.Google ScholarDigital Library
- Carlo Prato and Shlomo Bekhor. 2006. Applying branch-and-bound technique to route choice set generation. Transportation Research Record: Journal of the Transportation Research Board 1985 (2006), 19--28. DOI:https://doi.org/10.3141/1985-03Google ScholarCross Ref
- Piotr Szwed and Kamil Pekala. 2014. An incremental map-matching algorithm based on hidden Markov model. In Artificial Intelligence and Soft Computing. Lecture Notes in Computer Science, Vol. 8468. Springer, 579--590.Google Scholar
- Muhammad Reaz Uddin, Chinya Ravishankar, and Vassilis J. Tsotras. 2011. A system for discovering regions of interest from trajectory data. In Advances in Spatial and Temporal Databases. Lecture Notes in Computer Science, Vol. 6849. Springer, 481--485.Google Scholar
- Jing Yuan, Yu Zheng, Chengyang Zhang, Wenlei Xie, Xing Xie, and Yan Huang. 2010. T-Drive: Driving directions based on taxi trajectories. In Proceedings of the 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. 99--108.Google ScholarDigital Library
- Lei Zhang, David M. Levinson, and Shanjiang Zhu. 2008. Agent-based model of price competition, capacity choice, and product differentiation on congested networks. Journal of Transport Economics and Policy 42, 3 (2008), 435--461.Google Scholar
- Shanjiang Zhu and David Levinson. 2015. Do people use the shortest path? An empirical test of Wardrop’s first principle. PLoS ONE 10 (2015), 1--18. DOI:https://doi.org/10.1371/journal.pone.0134322Google Scholar
Index Terms
- Map-Matching Using Shortest Paths
Recommendations
Map-matching using shortest paths
IWISC '18: Proceedings of the 3rd International Workshop on Interactive and Spatial ComputingWe consider several variants of the map-matching problem, which seeks to find a path Q in graph G that has the smallest distance to a given trajectory P (which is likely not to be exactly on the graph). In a typical application setting, P models a noisy ...
Improved algorithms for the k simple shortest paths and the replacement paths problems
Given a directed, non-negatively weighted graph G=(V,E) and s,t@?V, we consider two problems. In the k simple shortest paths problem, we want to find the k simple paths from s to t with the k smallest weights. In the replacement paths problem, we want ...
Generalization of Shortest Path Map
ITNG '10: Proceedings of the 2010 Seventh International Conference on Information Technology: New GenerationsWe consider the problem of constructing shortest path maps in two dimensions under angle constraint. Shortest path maps are used for planning short length paths from a fixed source point s to varying goal points. In the standard shortest path map the ...
Comments