{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,15]],"date-time":"2026-08-15T17:31:57Z","timestamp":1786815117520,"version":"build-2736575974"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"7","license":[{"start":{"date-parts":[[2024,6,19]],"date-time":"2024-06-19T00:00:00Z","timestamp":1718755200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"The National Key Research and Development Program of China","award":["2020YFA0711403"],"award-info":[{"award-number":["2020YFA0711403"]}]},{"DOI":"10.13039\/501100001809","name":"National Nature Science Foundation of China","doi-asserted-by":"crossref","award":["2272260, and U20B2060"],"award-info":[{"award-number":["2272260, and U20B2060"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2024,8,31]]},"abstract":"<jats:p>The fastest route search, which is to find a path with the shortest travel time when the user initiates a query, has become one of the most important services in many map applications. To enhance the user experience of travel, it is necessary to achieve accurate and real-time route search. However, traffic conditions are changing dynamically, and the frequent occurrence of traffic congestion may greatly increase travel time. Thus, it is challenging to achieve the above goal. To deal with it, we present a congestion-aware spatio-temporal graph convolutional network-based A* search algorithm for the task of fastest route search. We first identify a sequence of consecutive congested traffic conditions as a traffic congestion event. Then, we propose a spatio-temporal graph convolutional network that jointly models the congestion events and changing travel time to capture their complex spatio-temporal correlations, which can predict the future travel-time information of each road segment as the basis of route planning. Further, we design a path-aided neural network to achieve effective origin-destination (OD) shortest travel-time estimation by encoding the complex relationships between OD pairs and their corresponding fastest paths. Finally, the cost function in the A* algorithm is set by fusing the output results of the two components, which is used to guide the route search. Our experimental results on the two real-world datasets show the superior performance of the proposed method.<\/jats:p>","DOI":"10.1145\/3657640","type":"journal-article","created":{"date-parts":[[2024,4,11]],"date-time":"2024-04-11T09:55:26Z","timestamp":1712829326000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Congestion-aware Spatio-Temporal Graph Convolutional Network-based A* Search Algorithm for Fastest Route Search"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-8702-234X","authenticated-orcid":false,"given":"Hongjie","family":"Sui","sequence":"first","affiliation":[{"name":"Department of Electronic Engineering, Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9626-5676","authenticated-orcid":false,"given":"Huan","family":"Yan","sequence":"additional","affiliation":[{"name":"Department of Electronic Engineering, Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-7312-0059","authenticated-orcid":false,"given":"Tianyi","family":"Zheng","sequence":"additional","affiliation":[{"name":"Department of Electronic Engineering, Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0454-7516","authenticated-orcid":false,"given":"Wenzhen","family":"Huang","sequence":"additional","affiliation":[{"name":"Department of Electronic Engineering, Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3798-2920","authenticated-orcid":false,"given":"Yunlin","family":"Zhuang","sequence":"additional","affiliation":[{"name":"Hitachi China Research and Development Corp, Beijing China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5617-1659","authenticated-orcid":false,"given":"Yong","family":"Li","sequence":"additional","affiliation":[{"name":"Department of Electronic Engineering, Tsinghua University, Beijing China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,6,19]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"GEP Box and G. M. Jenkins. 2015. Time series analysis: Forecasting and control. John Wiley & Sons (2015)."},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3385414"},{"key":"e_1_3_2_4_2","first-page":"933","volume-title":"International Conference on Machine Learning","author":"Dauphin Yann N.","year":"2017","unstructured":"Yann N. Dauphin, Angela Fan, Michael Auli, and David Grangier. 2017. Language modeling with gated convolutional networks. In International Conference on Machine Learning. PMLR, 933\u2013941."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3459637.3481916"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/1353343.1353371"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467060"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403320"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403386"},{"key":"e_1_3_2_10_2","first-page":"794","volume-title":"Proceedings of the 33rd International Conference on Very Large Data Bases","author":"Gonzalez Hector","year":"2007","unstructured":"Hector Gonzalez, Jiawei Han, Xiaolei Li, Margaret Myslinska, and John Paul Sondag. 2007. Adaptive fastest path computation on a road network: A traffic mining approach. In Proceedings of the 33rd International Conference on Very Large Data Bases. 794\u2013805."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467275"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3412363"},{"key":"e_1_3_2_14_2","doi-asserted-by":"crossref","unstructured":"E. Jenelius and H. N. Koutsopoulos. 2013. Travel time estimation for urban road networks using low frequency probe vehicle data. Transportation Research Part B: Methodological 53 (2013) 64\u201381.","DOI":"10.1016\/j.trb.2013.03.008"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3474717.3483913"},{"key":"e_1_3_2_16_2","doi-asserted-by":"crossref","unstructured":"G. Jin H. Yan F. Li et\u00a0al. 2023. Dual graph convolution architecture search for travel time estimation. ACM Transactions on Intelligent Systems and Technology 14 4 (2023) 1\u201323.","DOI":"10.1145\/3591361"},{"key":"e_1_3_2_17_2","article-title":"A unified neural network approach for estimating travel time and distance for a taxi trip","author":"Jindal Ishan","year":"2017","unstructured":"Ishan Jindal, Xuewen Chen, Matthew Nokleby, Jieping Ye, et\u00a0al. 2017. A unified neural network approach for estimating travel time and distance for a taxi trip. arXiv:1710.04350. Retrieved from https:\/\/arxiv.org\/abs\/1710.04350","journal-title":"arXiv:1710.04350"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.71"},{"key":"e_1_3_2_19_2","doi-asserted-by":"crossref","unstructured":"F. Li J. Feng H. Yan et\u00a0al. 2023. Dynamic graph convolutional recurrent network for traffic prediction: Benchmark and solution. ACM Transactions on Knowledge Discovery from Data 17 1 (2023) 1\u201321.","DOI":"10.1145\/3532611"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3589132.3625612"},{"key":"e_1_3_2_21_2","doi-asserted-by":"crossref","unstructured":"H. Li D. Jin X. Li et\u00a0al. 2023. Dmgf-net: an efficient dynamic multi-graph fusion network for traffic prediction. ACM Transactions on Knowledge Discovery from Data 17 7 (2023) 1\u201319.","DOI":"10.1145\/3586164"},{"key":"e_1_3_2_22_2","doi-asserted-by":"crossref","unstructured":"L. Li S. Wang and X. Zhou. 2020. Fastest path query answering using time-dependent hop-labeling in road network. IEEE Transactions on Knowledge and Data Engineering 34 1 (2020) 300\u2013313.","DOI":"10.1109\/TKDE.2020.2981062"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220033"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219895"},{"key":"e_1_3_2_25_2","article-title":"Auxiliary tasks in multi-task learning","author":"Liebel Lukas","year":"2018","unstructured":"Lukas Liebel and Marco K\u00f6rner. 2018. Auxiliary tasks in multi-task learning. arXiv:1805.06334. Retrieved from https:\/\/arxiv.org\/abs\/1805.06334","journal-title":"arXiv:1805.06334"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68552-4_25"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1155\/2015\/970256"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-5757-9_11"},{"key":"e_1_3_2_29_2","doi-asserted-by":"crossref","unstructured":"J. Rice and E. Van Zwet. 2004. A simple and effective method for predicting travel times on freeways. IEEE Transactions on Intelligent Transportation Systems 5 3 (2004) 200\u2013207.","DOI":"10.1109\/TITS.2004.833765"},{"key":"e_1_3_2_30_2","article-title":"Travel time estimation using floating car data","author":"Sevlian Raffi","year":"2010","unstructured":"Raffi Sevlian and Ram Rajagopal. 2010. Travel time estimation using floating car data. arXiv:1012.4249. Retrieved from https:\/\/arxiv.org\/abs\/1012.4249","journal-title":"arXiv:1012.4249"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0331-0"},{"key":"e_1_3_2_32_2","first-page":"1","article-title":"ASNN-FRR: A traffic-aware neural network for fastest route recommendation","author":"Wang Chaoxiong","year":"2021","unstructured":"Chaoxiong Wang, Chao Li, Hai Huang, Jing Qiu, Jianfeng Qu, and Lihua Yin. 2021. ASNN-FRR: A traffic-aware neural network for fastest route recommendation. GeoInformatica (2021), 1\u201322.","journal-title":"GeoInformatica"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v32i1.11877"},{"key":"e_1_3_2_34_2","doi-asserted-by":"crossref","unstructured":"H. Wang X. Tang Y. H. Kuo et\u00a0al. 2019. A simple baseline for travel time estimation using large-scale trip data. ACM Transactions on Intelligent Systems and Technology (TIST) 10 2 (2019) 1\u201322.","DOI":"10.1145\/3293317"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3589132.3625639"},{"key":"e_1_3_2_36_2","doi-asserted-by":"crossref","unstructured":"Y. Wang and M. Papageorgiou. 2005. Real-time freeway traffic state estimation based on extended Kalman filter: A general approach. Transportation Research Part B: Methodological 39 2 (2005) 141\u2013167.","DOI":"10.1016\/j.trb.2004.03.003"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623656"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339562"},{"key":"e_1_3_2_39_2","doi-asserted-by":"crossref","unstructured":"C. H. Wu J. M. Ho and D. T. Lee. 2004. Travel-time prediction with support vector regression. IEEE Transactions on Intelligent Transportation Systems 5 4 (2004) 276\u2013281.","DOI":"10.1109\/TITS.2004.837813"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357384.3357907"},{"key":"e_1_3_2_41_2","doi-asserted-by":"crossref","unstructured":"Z. Wu S. Pan G. Long et\u00a0al. 2019. Graph wavenet for deep spatial-temporal graph modeling. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (2019) 1907\u20131913.","DOI":"10.24963\/ijcai.2019\/264"},{"key":"e_1_3_2_42_2","doi-asserted-by":"crossref","unstructured":"S. Xu R. Zhang W. Cheng et\u00a0al. 2022. Mtlm: A multi-task learning model for travel time estimation. GeoInformatica 26 2 (2022) 379\u2013395.","DOI":"10.1007\/s10707-020-00422-x"},{"key":"e_1_3_2_43_2","doi-asserted-by":"crossref","unstructured":"Y. Xu L. Han T. Zhu et\u00a0al. 2023. Generic dynamic graph convolutional network for traffic flow forecasting. Information Fusion 100 (2023) 1\u201312.","DOI":"10.1016\/j.inffus.2023.101946"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-24521-3_2"},{"key":"e_1_3_2_45_2","first-page":"19","volume-title":"Spatial Data and Intelligence: Third International Conference, SpatialDI 2022, Revised Selected Papers","author":"Yan Huan","year":"2023","unstructured":"Huan Yan, Guangyin Jin, Deng Wang, Yue Liu, and Yong Li. 2023. Jointly modeling intersections and road segments for travel time estimation via dual graph convolutional networks. In Spatial Data and Intelligence: Third International Conference, SpatialDI 2022, Revised Selected Papers. Springer, 19\u201334."},{"key":"e_1_3_2_46_2","doi-asserted-by":"crossref","unstructured":"H. Yuan G. Li and Z. Bao et\u00a0al. 2020. Effective travel time estimation: When historical trajectories over road networks matter. In Proceedings of the 2020 ACM Sigmod International Conference on Management of Data (2020) 2135\u20132149.","DOI":"10.1145\/3318464.3389771"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020462"},{"key":"e_1_3_2_48_2","doi-asserted-by":"crossref","unstructured":"J. Yuan Y. Zheng X. Xie et\u00a0al. 2011. T-drive: Enhancing driving directions with taxi drivers\u2019 intelligence. IEEE Transactions on Knowledge and Data Engineering 25 1 (2011) 220\u2013232.","DOI":"10.1109\/TKDE.2011.200"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/1869790.1869807"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i01.5477"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3657640","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3657640","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:05:53Z","timestamp":1750291553000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3657640"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,19]]},"references-count":49,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2024,8,31]]}},"alternative-id":["10.1145\/3657640"],"URL":"https:\/\/doi.org\/10.1145\/3657640","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,19]]},"assertion":[{"value":"2023-03-12","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-31","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}