An offline map matching algorithm based on shortest paths

ABSTRACT

Offline map matching identifies corresponding roads to a GPS trajectory represented by a series of recorded geographic coordinates (GPS points) to the road network. This paper defines matching error as cost on the corresponding road-link to matched GPS points and formulates the offline map matching problem as a shortest path problem with resource constraints. By regarding matched points on one link as a type of resource consumed, the resource constraint indicates that the number of matched GPS points equals the total number of points in the given trajectory. We propose an offline map matching algorithm based on shortest paths by calculating the matching error on each link and extending the classic label-setting shortest path algorithm to find the path with the minimum total matching error for all GPS points. We use real-world taxi trajectories to compare our algorithm with three state-of-the-art map matching algorithms. Our algorithm outperforms all benchmark algorithms in terms of both matching accuracy and computational efficiency. Our algorithm achieves greater matched length (5.36 to 12.27% larger) and lower mis-matched length (3.72 to 75.30% smaller) at a very high matching speed (60.59 points per second on average over thirteen sampling intervals).

KEYWORDS:

• GPS trajectory
• resource constraints
• label-setting algorithm
• time-dependence

Acknowledgments

Guo would like to thank the financial supports from the National Natural Science Foundation of China (Grant No. 71872118), the MOE (Ministry of Education in China) Project of Humanities and Social Sciences (Grant No. 18YJC630045) and Sichuan University (Grant No.s 2018hhs-37, SKSYL201819). Zhang would like to thank the China Scholarship Council for financial supports. Data source: DiDi Chuxing GAIA Open Dataset Initiative.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1. The offline map matching model in Section 2 has only one resource constraint corresponding to Equation (6)(6) $z_P(0)=K$(6) . In addition, we consider three types of position information of node $v$ in path $P_k\cup v$. Therefore, according to the definition of $l_v(k)$ in Sub-section 3.1, we have $l_v(k)=\{C(k),R_1(k),O_1(k),O_2(k),O_3(k)\}$. To simplify the presentation and improve readability, we use new notations to represent the elements in $l_v(k)$.

Additional information

Funding

This work was supported by the China Scholarship Council; Innovation Spark Fund of Sichuan University [SKSYL201819,s 2018hhs-37]; National Natural Science Foundation of China [71872118]; Ministry of Education in China [18YJC630045].

Notes on contributors

Dongqing Zhang

Dongqing Zhang received the B.S. degree from the Business School, Sichuan University, Chengdu, China, in 2016. She is currently pursuing the Ph.D. Degree from the Business School, Sichuan University, Chengdu, China. Her current research interests include transportation big data mining, spatio-temporal data analysis, and data-driven decision making.

Zhaoxia Guo

Zhaoxia Guo received the B.S. and M.S. degrees in control theory and control engineering from Donghua University, Shanghai, China, in 2000 and 2003, respectively, and the Ph.D. degree in operation management from Hong Kong Polytechnic University, Hong Kong, in 2007. He is currently a professor at the Business School, Sichuan University, Chengdu, China. His current research interests include logistics and supply chain management, data-driven decision making, computing intelligence and applications.

Feng Guo

Feng Guo received the B.S. degree in electrical engineering and automation from Fuzhou  University, Fuzhou, China, in 2016, and the M.S. degree in management from Central China Normal University, Wuhan, China, in 2019. He is currently pursuing the Ph.D. Degree from the Business School, Sichuan University, Chengdu, China. His main interests include deep learning, spatio-temporal data analysis, and data-driven decision making.

Yucheng Dong

Yucheng Dong received the B.S. and M.S. degrees in mathematics from Chongqing University, Chongqing, China, in 2002 and 2004, respectively, and the Ph.D. degree in management from Xi’an Jiaotong University, Xi’an, China, in 2008. Now, he is currently a professor at the Business School, Sichuan University, Chengdu, China. His current research interests include decision analysis, human dynamics, big data analytics, social network, and risk analysis. Prof. Dong has been identified by Clarivate as Highly Cited Researcher in the field of computer science.