{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T18:23:07Z","timestamp":1771698187503,"version":"3.50.1"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T00:00:00Z","timestamp":1727654400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2024,9,30]]},"abstract":"<jats:p>Travel time estimation is one of the core tasks for the development of intelligent transportation systems. Most previous works model the road segments or intersections separately by learning their spatio-temporal characteristics to estimate travel time. However, due to the continuous alternations of the road segments and intersections in a path, the dynamic features are supposed to be coupled and interactive. Therefore, modeling one of them limits further improvement in accuracy of estimating travel time. To address the above problems, a novel graph-based deep learning framework for travel time estimation is proposed in this article, namely, Spatio-temporal Dual Graph Neural Networks (STDGNN). Specifically, we first establish the node-wise and edge-wise graphs to, respectively, characterize the adjacency relations of intersections and that of road segments. To extract the joint spatio-temporal correlations of the intersections and road segments, we adopt the spatio-temporal dual graph learning approach that incorporates multiple spatial-temporal dual graph learning modules with multi-scale network architectures for capturing multi-level spatial-temporal information from the dual graph. Finally, we employ the multi-task learning approach to estimate the travel time of a given whole route, each road segment and intersection simultaneously. We conduct extensive experiments to evaluate our proposed model on three real-world trajectory datasets, and the experimental results show that STDGNN significantly outperforms several state-of-art baselines.<\/jats:p>","DOI":"10.1145\/3627819","type":"journal-article","created":{"date-parts":[[2023,10,28]],"date-time":"2023-10-28T18:26:51Z","timestamp":1698517611000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Spatio-temporal Dual Graph Neural Networks for Travel Time Estimation"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9837-6836","authenticated-orcid":false,"given":"Guangyin","family":"Jin","sequence":"first","affiliation":[{"name":"National Innovative Institute of Defense Technology, Beijing, China and College of Systems Engineering, National University of Defense Technology, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7546-8087","authenticated-orcid":false,"given":"Huan","family":"Yan","sequence":"additional","affiliation":[{"name":"Beijing National Research Center for Information Science and Technology (BNRist), Department of Electronic Engineering, Tsinghua University, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8410-9393","authenticated-orcid":false,"given":"Fuxian","family":"Li","sequence":"additional","affiliation":[{"name":"Beijing National Research Center for Information Science and Technology (BNRist), Department of Electronic Engineering, Tsinghua University, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2902-9272","authenticated-orcid":false,"given":"Jincai","family":"Huang","sequence":"additional","affiliation":[{"name":"College of Systems Engineering, National University of Defense Technology, Changsha, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4166-3575","authenticated-orcid":false,"given":"Yong","family":"Li","sequence":"additional","affiliation":[{"name":"Beijing National Research Center for Information Science and Technology (BNRist), Department of Electronic Engineering, Tsinghua University, Beijing, China"}]}],"member":"320","published-online":{"date-parts":[[2024,10,4]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"Data Castle. 2016. Taxi Travel Time Prediction Challenge. Retrieved from http:\/\/www.dcjingsai.com"},{"key":"e_1_3_1_3_2","unstructured":"Kaggle. 2020. Taxi Trajectory Data. Retrieved from https:\/\/www.kaggle.com\/crailtap\/taxi-trajectory"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i04.5758"},{"key":"e_1_3_1_5_2","unstructured":"Junyoung Chung Caglar Gulcehre KyungHyun Cho and Yoshua Bengio. 2014. Empirical evaluation of gated recurrent neural networks on sequence modeling. Retrieved from https:\/\/arXiv:1412.3555"},{"key":"e_1_3_1_6_2","unstructured":"Steve Coast. 2004. OpenStreetMap. Retrieved from https:\/\/www.openstreetmap.org\/"},{"key":"e_1_3_1_7_2","doi-asserted-by":"crossref","first-page":"2697","DOI":"10.1145\/3394486.3403320","volume-title":"Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Fang Xiaomin","year":"2020","unstructured":"Xiaomin Fang, Jizhou Huang, Fan Wang, Lingke Zeng, Haijin Liang, and Haifeng Wang. 2020. ConSTGAT: Contextual spatial-temporal graph attention network for travel time estimation at baidu maps. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2697\u20132705."},{"key":"e_1_3_1_8_2","volume-title":"The Elements of Statistical Learning","author":"Friedman Jerome","year":"2001","unstructured":"Jerome Friedman, Trevor Hastie, Robert Tibshirani et\u00a0al. 2001. The Elements of Statistical Learning. Vol. 1. Springer, New York, NY."},{"key":"e_1_3_1_9_2","first-page":"3337","volume-title":"Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Fu Kun","year":"2020","unstructured":"Kun Fu, Fanlin Meng, Jieping Ye, and Zheng Wang. 2020. Compacteta: A fast inference system for travel time prediction. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 3337\u20133345."},{"key":"e_1_3_1_10_2","first-page":"69","volume-title":"Proceedings of the Conference on Information and Knowledge Management (CIKM\u201919)","author":"Fu Tao-yang","year":"2019","unstructured":"Tao-yang Fu and Wang-Chien Lee. 2019. DeepIST: Deep image-based spatio-temporal network for travel time estimation. In Proceedings of the Conference on Information and Knowledge Management (CIKM\u201919). 69\u201378."},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33013656"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.3301922"},{"key":"e_1_3_1_13_2","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/978-981-10-7200-0_6","volume-title":"Advances in Big Data and Cloud Computing","author":"Gupta Bharat","year":"2018","unstructured":"Bharat Gupta, Shivam Awasthi, Rudraksha Gupta, Likhama Ram, Pramod Kumar, Bakshi Rohit Prasad, and Sonali Agarwal. 2018. Taxi travel time prediction using ensemble-based random forest and gradient boosting model. In Advances in Big Data and Cloud Computing. Springer, 63\u201378."},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.trb.2013.03.008"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.trc.2020.102665"},{"key":"e_1_3_1_16_2","article-title":"Automated dilated spatio-temporal synchronous graph modeling for traffic prediction","author":"Jin Guangyin","year":"2022","unstructured":"Guangyin Jin, Fuxian Li, Jinlei Zhang, Mudan Wang, and Jincai Huang. 2022. Automated dilated spatio-temporal synchronous graph modeling for traffic prediction. IEEE Trans. Intell. Transport. Syst. 24, 8 (2022), 8820\u20138830.","journal-title":"IEEE Trans. Intell. Transport. Syst."},{"key":"e_1_3_1_17_2","unstructured":"Guangyin Jin Yuxuan Liang Yuchen Fang Jincai Huang Junbo Zhang and Yu Zheng. 2023. Spatio-temporal graph neural networks for predictive learning in urban computing: A survey. Retrieved from https:\/\/arXiv:2303.14483"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2021.12.085"},{"key":"e_1_3_1_19_2","first-page":"14268","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence","volume":"37","author":"Jin Guangyin","year":"2023","unstructured":"Guangyin Jin, Lingbo Liu, Fuxian Li, and Jincai Huang. 2023. Spatio-temporal graph neural point process for traffic congestion event prediction. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 37. 14268\u201314276."},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.neucom.2021.05.008"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.neucom.2022.09.010"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3474717.3483913"},{"key":"e_1_3_1_23_2","unstructured":"Thomas N. Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. Retrieved from https:\/\/arXiv:1609.02907"},{"key":"e_1_3_1_24_2","unstructured":"Yaguang Li Rose Yu Cyrus Shahabi and Yan Liu. 2017. Diffusion convolutional recurrent neural network: Data-driven traffic forecasting. Retrieved from https:\/\/arXiv:1707.01926"},{"key":"e_1_3_1_25_2","first-page":"10945","volume-title":"Advances in Neural Information Processing Systems","author":"Luan Sitao","year":"2019","unstructured":"Sitao Luan, Mingde Zhao, Xiao-Wen Chang, and Doina Precup. 2019. Break the ceiling: Stronger multi-scale deep graph convolutional networks. In Advances in Neural Information Processing Systems. 10945\u201310955."},{"key":"e_1_3_1_26_2","first-page":"713","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Luo Wuman","year":"2013","unstructured":"Wuman Luo, Haoyu Tan, Lei Chen, and Lionel M. Ni. 2013. Finding time period-based most frequent path in big trajectory data. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 713\u2013724."},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.5555\/3157382.3157412"},{"key":"e_1_3_1_28_2","first-page":"511","volume-title":"Proceedings of the International Conference on Knowledge-based and Intelligent Information and Engineering Systems","author":"Nath Rudra Pratap Deb","year":"2010","unstructured":"Rudra Pratap Deb Nath, Hyun-Jo Lee, Nihad Karim Chowdhury, and Jae-Woo Chang. 2010. Modified K-means clustering for travel time prediction based on historical traffic data. In Proceedings of the International Conference on Knowledge-based and Intelligent Information and Engineering Systems. Springer, 511\u2013521."},{"key":"e_1_3_1_29_2","first-page":"2292","volume-title":"Proceedings of the IEEE International Conference on Intelligent Transportation Systems","author":"Rahmani Mahmood","year":"2013","unstructured":"Mahmood Rahmani, Erik Jenelius, and Haris N. Koutsopoulos. 2013. Route travel time estimation using low-frequency floating car data. In Proceedings of the IEEE International Conference on Intelligent Transportation Systems. 2292\u20132297."},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2004.833765"},{"key":"e_1_3_1_31_2","unstructured":"Raffi Sevlian and Ram Rajagopal. 2010. Travel time estimation using floating car data. Retrieved from https:\/\/arXiv:1012.4249"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2016.2646371"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v31i1.11231"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.trc.2011.11.007"},{"key":"e_1_3_1_35_2","first-page":"2500","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence","author":"Wang Dong","year":"2018","unstructured":"Dong Wang, Junbo Zhang, Wei Cao, Jian Li, and Yu Zheng. 2018. When will you arrive? Estimating travel time based on deep neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence. 2500\u20132507."},{"issue":"2","key":"e_1_3_1_36_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3293317","article-title":"A simple baseline for travel time estimation using large-scale trip data","volume":"10","author":"Wang Hongjian","year":"2019","unstructured":"Hongjian Wang, Xianfeng Tang, Yu-Hsuan Kuo, Daniel Kifer, and Zhenhui Li. 2019. A simple baseline for travel time estimation using large-scale trip data. ACM Trans. Intell. Syst. Technol. 10, 2 (2019), 1\u201322.","journal-title":"ACM Trans. Intell. Syst. Technol."},{"key":"e_1_3_1_37_2","first-page":"309","volume-title":"Proceedings of the ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems","author":"Wang Meng-xiang","year":"2019","unstructured":"Meng-xiang Wang, Wang-Chien Lee, Tao-yang Fu, and Ge Yu. 2019. Learning embeddings of intersections on road networks. In Proceedings of the ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. 309\u2013318."},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3025580"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3397536.3422208"},{"key":"e_1_3_1_40_2","first-page":"1082","volume-title":"Proceedings of the World Wide Web Conference (WWW\u201920)","author":"Wang Xiaoyang","year":"2020","unstructured":"Xiaoyang Wang, Yao Ma, Yiqi Wang, Wei Jin, Xin Wang, Jiliang Tang, Caiyan Jia, and Jian Yu. 2020. Traffic flow prediction via spatial temporal graph neural network. In Proceedings of the World Wide Web Conference (WWW\u201920). 1082\u20131092."},{"key":"e_1_3_1_41_2","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1145\/2623330.2623656","volume-title":"Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery & Data Mining","author":"Wang Yilun","year":"2014","unstructured":"Yilun Wang, Yu Zheng, and Yexiang Xue. 2014. Travel time estimation of a path using sparse trajectories. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 25\u201334."},{"key":"e_1_3_1_42_2","first-page":"858","volume-title":"Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery & Data Mining","author":"Wang Zheng","year":"2018","unstructured":"Zheng Wang, Kun Fu, and Jieping Ye. 2018. Learning to estimate the travel time. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 858\u2013866."},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2004.837813"},{"key":"e_1_3_1_44_2","first-page":"4","article-title":"A comprehensive survey on graph neural networks","author":"Wu Zonghan","year":"2020","unstructured":"Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S. Yu Philip. 2020. A comprehensive survey on graph neural networks. IEEE Trans. Neural Netw. Learn. Syst. 32, 1 (2020), 4\u201324.","journal-title":"IEEE Trans. Neural Netw. Learn. Syst."},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403118"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.5555\/3367243.3367303"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0491-4"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1080\/13658816.2017.1400548"},{"key":"e_1_3_1_49_2","unstructured":"Bing Yu Haoteng Yin and Zhanxing Zhu. 2017. Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting. Retrieved from https:\/\/arXiv:1709.04875"},{"key":"e_1_3_1_50_2","first-page":"507","volume-title":"Proceedings of the European Conference on Computer Vision","author":"Yu Cunjun","year":"2020","unstructured":"Cunjun Yu, Xiao Ma, Jiawei Ren, Haiyu Zhao, and Shuai Yi. 2020. Spatio-temporal graph transformer networks for pedestrian trajectory prediction. In Proceedings of the European Conference on Computer Vision. Springer, 507\u2013523."},{"key":"e_1_3_1_51_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.200"},{"key":"e_1_3_1_52_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.trc.2020.102660"},{"key":"e_1_3_1_53_2","doi-asserted-by":"crossref","unstructured":"Hanyuan Zhang Hao Wu Weiwei Sun and Baihua Zheng. 2018. Deeptravel: A neural network based travel time estimation model with auxiliary supervision. Retrieved from https:\/\/arXiv:1802.02147","DOI":"10.24963\/ijcai.2018\/508"},{"key":"e_1_3_1_54_2","unstructured":"Jiani Zhang Xingjian Shi Junyuan Xie Hao Ma Irwin King and Dit-Yan Yeung. 2018. Gaan: Gated attention networks for learning on large and spatiotemporal graphs. Retrieved from https:\/\/arXiv:1803.07294"},{"key":"e_1_3_1_55_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.trc.2015.02.019"},{"key":"e_1_3_1_56_2","article-title":"T-GCN: A temporal graph convolutional network for traffic prediction","author":"Zhao Ling","year":"2019","unstructured":"Ling Zhao, Yujiao Song, Chao Zhang, Yu Liu, Pu Wang, Tao Lin, Min Deng, and Haifeng Li. 2019. T-GCN: A temporal graph convolutional network for traffic prediction. IEEE Trans Intell. Transport. Syst. 21, 9 (2019), 3848\u20133858.","journal-title":"IEEE Trans Intell. Transport. Syst."}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3627819","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3627819","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:36:09Z","timestamp":1750178169000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3627819"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,30]]},"references-count":55,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,9,30]]}},"alternative-id":["10.1145\/3627819"],"URL":"https:\/\/doi.org\/10.1145\/3627819","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"value":"2374-0353","type":"print"},{"value":"2374-0361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,30]]},"assertion":[{"value":"2022-12-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-10-10","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-10-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}