{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T19:47:59Z","timestamp":1774986479475,"version":"3.50.1"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"DOI":"10.13039\/501100006374","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62425203, 62032003, U21B2016"],"award-info":[{"award-number":["62425203, 62032003, U21B2016"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,17]]},"abstract":"<jats:p>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 task still challenging. This paper introduces a novel framework that achieves high accuracy and efficient matching while ensuring robustness in handling diverse scenarios. To improve efficiency, we begin by modeling the online map matching problem as an Online Markov Decision Process (OMDP) based on its inherent characteristics. This approach helps efficiently merge historical and real-time data, reducing unnecessary calculations. Next, to enhance robustness, we design a reinforcement learning method, enabling robust handling of real-time data from dynamically changing environments. In particular, we propose a novel model learning process and a comprehensive reward function, allowing the model to make reasonable current matches from a future-oriented perspective, and to continuously update and optimize during the decision-making process based on feedback. Lastly, to address the heterogeneity between trajectories and roads, we design distinct graph structures, facilitating efficient representation learning through graph and recurrent neural networks. To further align trajectory and road data, we introduce contrastive learning to decrease their distance in the latent space, thereby promoting effective integration of the two. Extensive evaluations on three real-world datasets confirm that our method significantly outperforms existing state-of-the-art solutions in terms of accuracy, efficiency and robustness.<\/jats:p>","DOI":"10.1145\/3725346","type":"journal-article","created":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:23:29Z","timestamp":1750281809000},"page":"1-26","source":"Crossref","is-referenced-by-count":3,"title":["RLOMM: An Efficient and Robust Online Map Matching Framework with Reinforcement Learning"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-0476-6174","authenticated-orcid":false,"given":"Minxiao","family":"Chen","sequence":"first","affiliation":[{"name":"Beijing University of Posts and Telecommunications, Beijing, China and Beiyou Shenzhen Institute, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6721-065X","authenticated-orcid":false,"given":"Haitao","family":"Yuan","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-3933-1662","authenticated-orcid":false,"given":"Nan","family":"Jiang","sequence":"additional","affiliation":[{"name":"Beijing University of Posts and Telecommunications, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-8896-4222","authenticated-orcid":false,"given":"Zhihan","family":"Zheng","sequence":"additional","affiliation":[{"name":"Beijing University of Posts and Telecommunications, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1866-9197","authenticated-orcid":false,"given":"Sai","family":"Wu","sequence":"additional","affiliation":[{"name":"Zhejiang University, Zhejiang, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5743-9418","authenticated-orcid":false,"given":"Ao","family":"Zhou","sequence":"additional","affiliation":[{"name":"Beijing University of Posts and Telecommunications, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7245-1298","authenticated-orcid":false,"given":"Shangguang","family":"Wang","sequence":"additional","affiliation":[{"name":"Beiyou Shenzhen Institute, Beijing, China and Beijing University of Posts and Telecommunications, Beijing, China"}]}],"member":"320","published-online":{"date-parts":[[2025,6,18]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2015. kaggle. https:\/\/www.kaggle.com\/c\/pkdd-15-taxi-trip-time-prediction-ii"},{"key":"e_1_2_1_2_1","unstructured":"2021. GAIA. https:\/\/outreach.didichuxing.com\/research\/opendata\/"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-39469-1_10"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Minxiao Chen Haitao Yuan Nan Jiang Zhifeng Bao and Shangguang Wang. 2024. Urban Traffic Accident Risk Prediction Revisited: Regionality Proximity Similarity and Sparsity. In CIKM. ACM 281--290.","DOI":"10.1145\/3627673.3679567"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Kyunghyun Cho Bart van Merrienboer \u00c7aglar G\u00fcl\u00e7ehre Dzmitry Bahdanau Fethi Bougares Holger Schwenk and Yoshua Bengio. 2014. Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation. In EMNLP Alessandro Moschitti Bo Pang and Walter Daelemans (Eds.). ACL 1724--1734.","DOI":"10.3115\/v1\/D14-1179"},{"key":"e_1_2_1_6_1","volume-title":"Current opinion in structural biology","author":"Eddy Sean R","unstructured":"Sean R Eddy. 1996. Hidden markov models. In Current opinion in structural biology, Vol. 6. Elsevier, 361--365."},{"key":"e_1_2_1_7_1","first-page":"2372","article-title":"DeepMM: Deep Learning Based Map Matching With Data Augmentation","volume":"21","author":"Feng Jie","year":"2022","unstructured":"Jie Feng, Yong Li, Kai Zhao, Zhao Xu, Tong Xia, Jinglin Zhang, and Depeng Jin. 2022. DeepMM: Deep Learning Based Map Matching With Data Augmentation. In TMC, Vol. 21. 2372--2384.","journal-title":"TMC"},{"key":"e_1_2_1_8_1","first-page":"9993860","article-title":"An Online Map Matching Algorithm Based on Second-Order Hidden Markov Model","volume":"2021","author":"Fu Xiao","year":"2021","unstructured":"Xiao Fu, Jiaxu Zhang, and Yue Zhang. 2021. An Online Map Matching Algorithm Based on Second-Order Hidden Markov Model. In JAT, Vol. 2021. 9993860.","journal-title":"JAT"},{"key":"e_1_2_1_9_1","volume-title":"Ali Oran, and Patrick Jaillet.","author":"Goh Chong Yang","year":"2012","unstructured":"Chong Yang Goh, Justin Dauwels, Nikola Mitrovic, Muhammad Tayyab Asif, Ali Oran, and Patrick Jaillet. 2012. Online map-matching based on Hidden Markov model for real-time traffic sensing applications. In ITSC. IEEE, 776--781."},{"key":"e_1_2_1_10_1","volume-title":"Jensen","author":"Guo Chenjuan","year":"2018","unstructured":"Chenjuan Guo, Bin Yang, Jilin Hu, and Christian S. Jensen. 2018. Learning to Route with Sparse Trajectory Sets. In ICDE. IEEE Computer Society, 1073--1084."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1162\/neco.1997.9.8.1735"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.79.8.2554"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2617326"},{"key":"e_1_2_1_14_1","first-page":"5039","article-title":"AMM: An Adaptive Online Map Matching Algorithm","volume":"24","author":"Hu Hanwen","year":"2023","unstructured":"Hanwen Hu, Shiyou Qian, Jingchao Ouyang, Jian Cao, Han Han, JieWang, and Yirong Chen. 2023. AMM: An Adaptive Online Map Matching Algorithm. In TITS, Vol. 24. 5039--5051.","journal-title":"TITS"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1049\/cit2.12030"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177703732"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2017.2647967"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3550486"},{"key":"e_1_2_1_19_1","volume-title":"Towards Effective Next POI Prediction: Spatial and Semantic Augmentation with Remote Sensing Data","author":"Jiang Nan","unstructured":"Nan Jiang, Haitao Yuan, Jianing Si, Minxiao Chen, and ShangguangWang. 2024. Towards Effective Next POI Prediction: Spatial and Semantic Augmentation with Remote Sensing Data. In ICDE. IEEE, 5061--5074."},{"key":"e_1_2_1_20_1","volume-title":"Kingma and Jimmy Ba","author":"Diederik","year":"2015","unstructured":"Diederik P. Kingma and Jimmy Ba. 2015. Adam: A Method for Stochastic Optimization. In ICLR, Yoshua Bengio and Yann LeCun (Eds.)."},{"key":"e_1_2_1_21_1","volume-title":"Kipf and Max Welling","author":"Thomas","year":"2017","unstructured":"Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In ICLR."},{"key":"e_1_2_1_22_1","first-page":"150","article-title":"Comparative Study and Application- Oriented Classification of Vehicular Map-Matching Methods","volume":"10","author":"Kubicka Matej","year":"2018","unstructured":"Matej Kubicka, Arben \u00c7ela, Hugues Mounier, and Silviu-Iulian Niculescu. 2018. Comparative Study and Application- Oriented Classification of Vehicular Map-Matching Methods. In ITSM, Vol. 10. 150--166.","journal-title":"ITSM"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-31750-2_6"},{"key":"e_1_2_1_24_1","volume-title":"CoRR","author":"Lipton Zachary Chase","unstructured":"Zachary Chase Lipton. 2015. A Critical Review of Recurrent Neural Networks for Sequence Learning. In CoRR, Vol. abs\/1506.00019."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3287739"},{"key":"e_1_2_1_26_1","volume-title":"SIGSPATIAL, Divyakant Agrawal, Walid G. Aref, Chang-Tien Lu, Mohamed F","author":"Lou Yin","unstructured":"Yin Lou, Chengyang Zhang, Yu Zheng, Xing Xie, Wei Wang, and Yan Huang. 2009. Map-matching for low-samplingrate GPS trajectories. In SIGSPATIAL, Divyakant Agrawal, Walid G. Aref, Chang-Tien Lu, Mohamed F. Mokbel, Peter Scheuermann, Cyrus Shahabi, and Ouri Wolfson (Eds.). ACM, 352--361."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2023.3322841"},{"key":"e_1_2_1_28_1","volume-title":"Riedmiller","author":"Mnih Volodymyr","year":"2013","unstructured":"Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin A. Riedmiller. 2013. Playing Atari with Deep Reinforcement Learning. In CoRR, Vol. abs\/1312.5602."},{"key":"e_1_2_1_29_1","first-page":"847","article-title":"Accurate Real-time Map Matching for Challenging Environments","volume":"18","author":"Mohamed Reham","year":"2017","unstructured":"Reham Mohamed, Heba Aly, and Moustafa Youssef. 2017. Accurate Real-time Map Matching for Challenging Environments. In TITS, Vol. 18. 847--857.","journal-title":"TITS"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1653771.1653818"},{"key":"e_1_2_1_31_1","first-page":"1555","article-title":"Anytime Stochastic Routing with Hybrid Learning","volume":"13","author":"Pedersen Simon Aagaard","year":"2020","unstructured":"Simon Aagaard Pedersen, Bin Yang, and Christian S. Jensen. 2020. Anytime Stochastic Routing with Hybrid Learning. In VLDB, Vol. 13. 1555--1567.","journal-title":"VLDB"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.3390\/ijgi12080330"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.trc.2007.05.002"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467238"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s42979-022-01340-5"},{"key":"e_1_2_1_36_1","first-page":"1","article-title":"DMM: fast map matching for cellular data","volume":"60","author":"Shen Zhihao","year":"2020","unstructured":"Zhihao Shen, Wan Du, Xi Zhao, and Jianhua Zou. 2020. DMM: fast map matching for cellular data. In MobiCom. ACM, 60:1--60:14.","journal-title":"MobiCom. ACM"},{"key":"e_1_2_1_37_1","volume-title":"DMM: A Deep Reinforcement Learning based Map Matching Framework for Cellular Data","author":"Shen Zhihao","year":"2024","unstructured":"Zhihao Shen, Kang Yang, Xi Zhao, Jianhua Zou, Wan Du, and Junjie Wu. 2024. DMM: A Deep Reinforcement Learning based Map Matching Framework for Cellular Data. In TKDE. IEEE."},{"key":"e_1_2_1_38_1","volume-title":"LHMM: A Learning Enhanced HMM Model for Cellular Trajectory Map Matching","author":"Shi Weijie","year":"2023","unstructured":"Weijie Shi, Jiajie Xu, Junhua Fang, Pingfu Chao, An Liu, and Xiaofang Zhou. 2023. LHMM: A Learning Enhanced HMM Model for Cellular Trajectory Map Matching. In ICDE. IEEE, 2429--2442."},{"key":"e_1_2_1_39_1","first-page":"1","article-title":"Real-time navigation of independent agents using adaptive roadmaps","volume":"56","author":"Sud Avneesh","year":"2008","unstructured":"Avneesh Sud, Russell Gayle, Erik Andersen, Stephen J. Guy, Ming C. Lin, and Dinesh Manocha. 2008. Real-time navigation of independent agents using adaptive roadmaps. In SIGGRAPH. ACM, 56:1--56:10.","journal-title":"SIGGRAPH. ACM"},{"key":"e_1_2_1_40_1","first-page":"338","article-title":"Online Map Matching With Route Prediction","volume":"20","author":"Taguchi Shun","year":"2019","unstructured":"Shun Taguchi, Satoshi Koide, and Takayoshi Yoshimura. 2019. Online Map Matching With Route Prediction. In TITS, Vol. 20. 338--347.","journal-title":"TITS"},{"key":"e_1_2_1_41_1","volume-title":"CoRR","author":"van den Oord A\u00e4ron","unstructured":"A\u00e4ron van den Oord, Yazhe Li, and Oriol Vinyals. 2018. Representation Learning with Contrastive Predictive Coding. In CoRR, Vol. abs\/1807.03748."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v30i1.10295"},{"key":"e_1_2_1_43_1","unstructured":"Ashish Vaswani Noam Shazeer Niki Parmar Jakob Uszkoreit Llion Jones Aidan N. Gomez Lukasz Kaiser and Illia Polosukhin. 2017. Attention is All you Need. In NIPS. 5998--6008."},{"key":"e_1_2_1_44_1","first-page":"921","article-title":"Deep Trajectory Recovery with Fine-Grained Calibration using Kalman Filter","volume":"33","author":"Lu Xinxi","year":"2021","unstructured":"JingyuanWang, NingWu, Xinxi Lu,Wayne Xin Zhao, and Kai Feng. 2021. Deep Trajectory Recovery with Fine-Grained Calibration using Kalman Filter. In TKDE, Vol. 33. 921--934.","journal-title":"TKDE"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1111\/tgis.13107"},{"key":"e_1_2_1_46_1","unstructured":"Keyulu Xu Weihua Hu Jure Leskovec and Stefanie Jegelka. 2019. How Powerful are Graph Neural Networks?. In ICLR."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1080\/13658816.2017.1400548"},{"key":"e_1_2_1_48_1","first-page":"63","article-title":"A Survey of Traffic Prediction: from Spatio-Temporal Data to Intelligent Transportation. In Data Sci","volume":"6","author":"Yuan Haitao","year":"2021","unstructured":"Haitao Yuan and Guoliang Li. 2021. A Survey of Traffic Prediction: from Spatio-Temporal Data to Intelligent Transportation. In Data Sci. Eng., Vol. 6. 63--85.","journal-title":"Eng."},{"key":"e_1_2_1_49_1","first-page":"393","article-title":"Route Travel Time Estimation on A Road Network Revisited: Heterogeneity, Proximity, Periodicity and Dynamicity","volume":"16","author":"Yuan Haitao","year":"2022","unstructured":"Haitao Yuan, Guoliang Li, and Zhifeng Bao. 2022. Route Travel Time Estimation on A Road Network Revisited: Heterogeneity, Proximity, Periodicity and Dynamicity. In VLDB, Vol. 16. 393--405.","journal-title":"VLDB"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389771"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2010.14"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3347146.3359090"},{"key":"e_1_2_1_53_1","doi-asserted-by":"crossref","unstructured":"Kai Zheng Yu Zheng Xing Xie and Xiaofang Zhou. 2012. Reducing Uncertainty of Low-Sampling-Rate Trajectories. In ICDE Anastasios Kementsietsidis and Marcos Antonio Vaz Salles (Eds.). 1144--1155.","DOI":"10.1109\/ICDE.2012.42"},{"key":"e_1_2_1_54_1","first-page":"1","article-title":"RLER-TTE: An Efficient and Effective Framework for En Route Travel Time Estimation with Reinforcement Learning","volume":"3","author":"Zheng Zhihan","year":"2025","unstructured":"Zhihan Zheng, Haitao Yuan, Minxiao Chen, and Shangguang Wang. 2025. RLER-TTE: An Efficient and Effective Framework for En Route Travel Time Estimation with Reinforcement Learning. In SIGMOD, Vol. 3. 71:1--71:26.","journal-title":"SIGMOD"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.3141\/2645-08"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725346","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:50:10Z","timestamp":1774983010000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725346"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,17]]},"references-count":55,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,17]]}},"alternative-id":["10.1145\/3725346"],"URL":"https:\/\/doi.org\/10.1145\/3725346","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,17]]}}}