AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Journal of Computer Science and Technology Article
Article Link
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Regular Paper

Spatio-Temporal Learning for Route-Based Travel Time Estimation

School of Software Technology, Zhejiang University, Ningbo 315048, China
College of Computer Science, Zhejiang University, Hangzhou 310027, China
Show Author Information

Abstract

Travel time estimation (TTE) is a fundamental task to build intelligent transportation systems. However, most existing TTE solutions design models upon simple homogeneous graphs and ignore the heterogeneity of traffic networks, where, e.g., main roads typically contribute differently from side roads. In terms of spatial dimension, few studies consider the dynamic spatial correlations across road segments, e.g., the traffic speed/volume on road segment A may correlate with the traffic speed/volume on road segment B, where A and B could be adjacent or non-adjacent, and such correlations may vary across time. In terms of temporal dimension, even fewer studies consider the dynamic temporal dependences, where, e.g., the historical states of road A may directly correlate with the recent state of A, and may also indirectly correlate with the recent state of road B. To track all aforementioned issues of existing TTE approaches, we provide HDTTE, a solution that employs heterogeneous and dynamic spatio-temporal predictive learning. Specifically, we first design a general multi-relational graph constructor that extracts hidden heterogeneous information of road segments, where we model road segments as nodes and model correlations as edges in the multi-relational graph. Next, we propose a dynamic graph attention convolution module that aggregates dynamic spatial dependence of neighbor roads to focal roads. We also present a novel correlation-augmented temporal convolution module to capture the influence of states at past time steps on current traffic states. Finally, in view of the periodic dependence of traffic, we develop a multi-scale adaptive fusion layer to enable HDTTE to exploit periodic patterns from recent, daily, and weekly traffic states. An experimental study using real-life highway and urban datasets demonstrates the validity of the approach and its advantage over others.

Keywords

heterogeneous traffic modelingspatio-temporal learningtravel time estimationtraffic speed prediction

Electronic Supplementary Material

Download File(s)
JCST-2209-12828-Highlights.pdf (615.4 KB)

References

[1]
Cheng R, Chen C, Xu L F, Li S, Wang W, Cui H B, Liu K K, Li X L. R4: A framework for route representation and route recommendation. arXiv: 2110.10474, 2021. https://arxiv.org/abs/2110.10474, Jul. 2024.
[2]
Singh A, Alabbasi A, Aggarwal V. A reinforcement learning based algorithm for multi-hop ride-sharing: Model-free approach. In Proc. the 33rd Conference on Neural Information Processing Systems Workshop, Dec. 2019.
[3]

Yuan N J, Zheng Y, Zhang L H, Xie X. T-finder: A recommender system for finding passengers and vacant taxis. IEEE Trans. Knowledge and Data Engineering, 2013, 25(10): 2390–2403. DOI: 10.1109/TKDE.2012.153.
Crossref Google Scholar
[4]
Maiti S, Pal A, Pal A, Chattopadhyay T, Mukherjee A. Historical data based real time prediction of vehicle arrival time. In Proc. the 17th International IEEE Conference on Intelligent Transportation Systems, Oct. 2014, pp.1837–1842. DOI: 10.1109/ITSC.2014.6957960.
Crossref
[5]

Wang H J, Tang X F, Kuo Y H, Kifer D, Li Z H. A simple baseline for travel time estimation using large-scale trip data. ACM Trans. Intelligent Systems and Technology, 2019, 10(2): Article No. 19. DOI: 10.1145/3293317.
Crossref Google Scholar
[6]

Zhang Y R, Haghani A. A gradient boosting method to improve travel time prediction. Transportation Research Part C: Emerging Technologies, 2015, 58: 308–324. DOI: 10.1016/j.trc.2015.02.019.
Crossref Google Scholar
[7]
Li Y G, Fu K, Wang Z, Shahabi C, Ye J P, Liu Y. Multi-task representation learning for travel time estimation. In Proc. the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Aug. 2018, pp.1695–1704. DOI: 10.1145/3219819.3220033.
Crossref
[8]
Wang Z, Fu K, Ye J P. Learning to estimate the travel time. In Proc. the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Aug. 2018, pp.858–866. DOI: 10.1145/3219819.3219900.
Crossref
[9]
Yuan H T, Li G L, Bao Z F, Feng L. Effective travel time estimation: When historical trajectories over road networks matter. In Proc. the 2020 ACM SIGMOD International Conference on Management of Data, Jun. 2020, pp.2135–2149. DOI: 10.1145/3318464.3389771.
Crossref
[10]
Zhang H Y, Wu H, Sun W W, Zheng B H. DeepTravel: A neural network based travel time estimation model with auxiliary supervision. In Proc. the 27th International Joint Conference on Artificial Intelligence, Jul. 2018, pp.3655–3661. DOI: 10.24963/ijcai.2018/508.
Crossref
[11]
Hong H T, Lin Y C, Yang X Q, Li Z, Fu K, Wang Z, Qie X H, Ye J P. HetETA: Heterogeneous information network embedding for estimating time of arrival. In Proc. the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Aug. 2020, pp.2444–2454. DOI: 10.1145/3394486.3403294.
Crossref
[12]

Yin X Y, Wu G Z, Wei J Z, Shen Y M, Qi H, Yin B C. Deep learning on traffic prediction: Methods, analysis, and future directions. IEEE Trans. Intelligent Transportation Systems, 2022, 23(6): 4927–4943. DOI: 10.1109/TITS.2021.3054840.
Crossref Google Scholar
[13]
Fu K, Meng F L, Ye J P, Wang Z. CompactETA: A fast inference system for travel time prediction. In Proc. the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Aug. 2020, pp.3337–3345. DOI: 10.1145/3394486.3403386.
Crossref
[14]
Defferrard M, Bresson X, Vandergheynst P. Convolutional neural networks on graphs with fast localized spectral filtering. In Proc. the 30th International Conference on Neural Information Processing Systems, Dec. 2016, pp.3844–3852. DOI: 10.5555/3157382.3157527.
[15]

Hochreiter S, Schmidhuber J. Long short-term memory. Neural Computation, 1997, 9(8): 1735–1780. DOI: 10.1162/neco.1997.9.8.1735.
Crossref Google Scholar
[16]
Cho K, Van Merriënboer B, Gulcehre C, Bahdanau D, Bougares F, Schwenk H, Bengio Y. Learning phrase representations using RNN encoder-decoder for statistical machine translation. In Proc. the 2014 Conference on Empirical Methods in Natural Language Processing, Oct. 2014, pp.1724–1734. DOI: 10.3115/v1/d14-1179.
Crossref
[17]
Guo S N, Lin Y F, Feng N, Song C, Wan H Y. Attention based spatial-temporal graph convolutional networks for traffic flow forecasting. In Proc. the 33rd AAAI Conference on Artificial Intelligence, Jan. 27–Feb. 1, 2019, pp.922–929. DOI: 10.1609/aaai.v33i01.3301922.
Crossref
[18]
Jin G Y, Yan H, Li F X, Huang J C, Li Y. Spatio-temporal dual graph neural networks for travel time estimation. ACM Trans. Spatial Algorithms and Systems, 2023. DOI: 10.1145/3627819. (Just accepted
Crossref
[19]
Li Y G, Yu R, Shahabi C, Liu Y. Diffusion convolutional recurrent neural network: Data-driven traffic forecasting. In Proc. the 6th International Conference on Learning Representations, Apr. 30–May 3, 2018.
[20]
Yu B, Yin H T, Zhu Z X. Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting. In Proc. the 27th International Joint Conference on Artificial Intelligence, Jul. 2018, pp.3634−3640. DOI: 10.24963/ijcai.2018/505.
Crossref
[21]
Jiang R H, Yin D, Wang Z N, Wang Y Z, Deng J W, Liu H C, Cai Z K, Deng J L, Song X, Shibasaki R. DL-Traff: Survey and benchmark of deep learning models for urban traffic prediction. In Proc. the 30th ACM International Conference on Information & Knowledge Management, Oct. 2021, pp.4515−4525. DOI: 10.1145/3459637.3482000.
Crossref
[22]

Jiang W W, Luo J Y. Graph neural network for traffic forecasting: A survey. Expert Systems with Applications, 2022, 207: 117921. DOI: 10.1016/j.eswa.2022.117921.
Crossref Google Scholar
[23]

Tedjopurnomo D A, Bao Z F, Zheng B H, Choudhury F M, Qin A K. A survey on modern deep neural network for traffic prediction: Trends, methods and challenges. IEEE Trans. Knowledge and Data Engineering, 2022, 34(4): 1544–1561. DOI: 10.1109/TKDE.2020.3001195.
Crossref Google Scholar
[24]

Yuan H T, Li G L. A survey of traffic prediction: From spatio-temporal data to intelligent transportation. Data Science and Engineering, 2021, 6(1): 63–85. DOI: 10.1007/s41019-020-00151-z.
Crossref Google Scholar
[25]
Wang D, Zhang J B, Cao W, Li J, Zheng Y. When will you arrive? Estimating travel time based on deep neural networks. In Proc. the 32nd AAAI Conference on Artificial Intelligence, Feb. 2018, pp.2500–2507. DOI: 10.5555/3504035.3504340.
Crossref
[26]
Li X C, Cong G, Sun A X, Cheng Y. Learning travel time distributions with deep generative model. In Proc. the 2019 World Wide Web Conference, May 2019, pp.1017–1027. DOI: 10.1145/3308558.3313418.
Crossref
[27]
Fang X M, Huang J Z, Wang F, Zeng L K, Liang H J, Wang H F. ConSTGAT: Contextual spatial-temporal graph attention network for travel time estimation at Baidu maps. In Proc. the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Aug. 2020, pp.2697–2705. DOI: 10.1145/3394486.3403320.
Crossref
[28]

Jin G Y, Wang M, Zhang J L, Sha H Y, Huang J C. STGNN-TTE: Travel time estimation via spatial-temporal graph neural network. Future Generation Computer Systems, 2022, 126: 70–81. DOI: 10.1016/j.future.2021.07.012.
Crossref Google Scholar
[29]
Kipf T N, Welling M. Semi-supervised classification with graph convolutional networks. In Proc. the 5th International Conference on Learning Representations, Apr. 2017.
[30]

Fang Z Q, Pan L, Chen L, Du Y T, Gao Y J. MDTP: A multi-source deep traffic prediction framework over spatio-temporal trajectory data. Proceedings of the VLDB Endowment, 2021, 14(8): 1289–1297. DOI: 10.14778/3457390.3457394.
Crossref Google Scholar
[31]
Geng X, Li Y G, Wang L Y, Zhang L Y, Yang Q, Ye J P, Liu Y. Spatiotemporal multi-graph convolution network for ride-hailing demand forecasting. In Proc. the 33rd AAAI Conference on Artificial Intelligence, Jan. 2019, pp.3656−3663. DOI: 10.1609/aaai.v33i01.33013656.
Crossref
[32]
Wu Z H, Pan S R, Long G D, Jiang J, Chang X J, Zhang C Q. Connecting the dots: Multivariate time series forecasting with graph neural networks. In Proc. the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Aug. 2020, pp.753–763. DOI: 10.1145/3394486.3403118.
Crossref
[33]
Wu Z H, Pan S R, Long G D, Jiang J, Zhang C Q. Graph WaveNet for deep spatial-temporal graph modeling. In Proc. the 28th International Joint Conference on Artificial Intelligence, Aug. 2019, pp.1907–1913. DOI: 10.24963/ijcai.2019/264.
Crossref
[34]
Fu X Y, Zhang J N, Meng Z Q, King I. MAGNN: Metapath aggregated graph neural network for heterogeneous graph embedding. In Proc. the 2020 Web Conference, Apr. 2020, pp.2331–2341. DOI: 10.1145/3366423.3380297.
Crossref
[35]
Zhang C X, Song D J, Huang C, Swami A, Chawla N V. Heterogeneous graph neural network. In Proc. the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Aug. 2019, pp.793–803. DOI: 10.1145/3292500.3330961.
Crossref
[36]
Bai L, Yao L N, Li C, Wang X Z, Wang C. Adaptive graph convolutional recurrent network for traffic forecasting. In Proc. the 34th International Conference on Neural Information Processing Systems, Dec. 2020, pp.17809–17815. DOI: 10.5555/3495724.3497218.
[37]
Veličković P, Cucurull G, Casanova A, Romero A, Liò P, Bengio Y. Graph attention networks. arXiv: 1710.10903, 2017. https://arxiv.org/abs/1710.10903, Jul. 2024.
[38]

Ye J X, Zhao J J, Ye K J, Xu C Z. How to build a graph-based deep learning architecture in traffic domain: A survey. IEEE Trans. Intelligent Transportation Systems, 2022, 23(5): 3904–3924. DOI: 10.1109/TITS.2020.3043250.
Crossref Google Scholar
[39]

Zhang Z W, Cui P, Zhu W W. Deep learning on graphs: A survey. IEEE Trans. Knowledge and Data Engineering, 2022, 34(1): 249–270. DOI: 10.1109/TKDE.2020.2981333.
Crossref Google Scholar
[40]

Guo S N, Lin Y F, Wan H Y, Li X C, Cong G. Learning dynamics and heterogeneity of spatial-temporal graph data for traffic forecasting. IEEE Trans. Knowledge and Data Engineering, 2022, 34(11): 5415–5428. DOI: 10.1109/TKDE.2021.3056502.
Crossref Google Scholar
[41]
Miller J, Hardt M. When recurrent models don't need to be recurrent. arXiv: 1805.10369, 2018. https://arxiv.org/abs/1805.10369v1, Jul. 2024.
[42]
Zhu H, Wang L, Zhang P Y, Yan Y H. Multi-accent adaptation based on gate mechanism. In Proc. the 20th Annual Conference of the International Speech Communication Association, Sept. 2019, pp.744–748.
Crossref
[43]
Lian J, Zhang L. One-month Beijing taxi GPS trajectory dataset with taxi IDs and vehicle status. In Proc. the 1st Workshop on Data Acquisition to Analysis, Nov. 2018, pp.3–4. DOI: 10.1145/3277868.3277870.
Crossref
[44]
Han L Z, Du B W, Sun L L, Fu Y J, Lv Y S, Xiong H. Dynamic and multi-faceted spatio-temporal deep learning for traffic speed forecasting. In Proc. the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, Aug. 2021, pp.547–555. DOI: 10.1145/3447548.3467275.
Crossref
Journal of Computer Science and Technology
Volume 39 Issue 5,
September 2024
Pages 1107-1122
DOI: 10.1007/s11390-024-2828-y

{{item.num}}

Comments on this article

Go to comment

< Back to all reports

Review Status: {{reviewData.commendedNum}} Commended , {{reviewData.revisionRequiredNum}} Revision Required , {{reviewData.notCommendedNum}} Not Commended Under Peer Review

Review Comment

Cite this Report
Close
Close
Cite this article:
Fang Z-Q, Sun Q-C, Chen L, et al. Spatio-Temporal Learning for Route-Based Travel Time Estimation. Journal of Computer Science and Technology, 2024, 39(5): 1107-1122. https://doi.org/10.1007/s11390-024-2828-y

193

Views

0

Crossref

0

Web of Science

0

Scopus

0

CSCD

Altmetrics
Received: 13 September 2022
Accepted: 21 May 2024
Published: 05 December 2024
© Institute of Computing Technology, Chinese Academy of Sciences 2024