Abstract

Online map matching is a fundamental problem in location-based services,aiming to incrementally match trajectory data step-by-step onto a road network.However, existing methods fail to meet the needs for efficiency, robustness,and accuracy required by large-scale online applications, making this taskstill challenging. This paper introduces a novel framework that achieves highaccuracy and efficient matching while ensuring robustness in handling diversescenarios. To improve efficiency, we begin by modeling the online map matchingproblem as an Online Markov Decision Process (OMDP) based on its inherentcharacteristics. This approach helps efficiently merge historical and real-timedata, reducing unnecessary calculations. Next, to enhance robustness, we designa reinforcement learning method, enabling robust handling of real-time datafrom dynamically changing environments. In particular, we propose a novel modellearning process and a comprehensive reward function, allowing the model tomake reasonable current matches from a future-oriented perspective, and tocontinuously update and optimize during the decision-making process based onfeedback. Lastly, to address the heterogeneity between trajectories and roads,we design distinct graph structures, facilitating efficient representationlearning through graph and recurrent neural networks. To further aligntrajectory and road data, we introduce contrastive learning to decrease theirdistance in the latent space, thereby promoting effective integration of thetwo. Extensive evaluations on three real-world datasets confirm that our methodsignificantly outperforms existing state-of-the-art solutions in terms ofaccuracy, efficiency and robustness.