Traffic graph convolutional network for dynamic urban travel speed estimation. (English) Zbl 07797529
Summary: The dynamic urban link travel speed estimation (DU-LSE) problem has been studied extensively with approaches ranging from model to data driven since it benefits multiple applications in transport mobility, especially in dense cities. However, with drawbacks such as heavy assumption in model-driven and not being capable for big city network in data-driven, there has not been a consensus on the most effective method. This study aims to develop a Sequential Three Step framework to solve the DU-LSE problem using only the passively collected taxi trip data. The framework makes use of two deep learning models namely Traffic Graph Convolution (TGCN) and its recurrent variant \(\mathrm{TGCN_{lstm}}\) to capture both spatial and temporal correlation between road segments. The proposed framework has three advantages over similar approaches: (1) it uses only the affordable taxi data and overcomes the data’s incompleteness both in spatial (full GPS trajectory is not available) and temporal (incomplete historic time-series) domain, (2) it is specifically designed to preserve the directionality nature of traffic flow, and (3) it is capable for large networks. The model results and validations suggest the framework can achieve high enough accuracy and will provide valuable mobility data for cities especially those without traffic sensing infrastructure already in place.
MSC:
| 90Cxx | Mathematical programming |
| 05Cxx | Graph theory |
| 90Bxx | Operations research and management science |
References:
| [1] | Biem A, Bouillet E, Feng H (2010) IBM infosphere streams for scalable, real-time, intelligent transportation services. Proc 2010 ACM SIGMOD Int Conf Manag Data [WWW Document]. doi:10.1145/1807167.1807291. (Accessed 20 Jul 2020) |
| [2] | Chondrogiannis, T.; Bouros, P.; Gamper, J.; Leser, U.; Blumenthal, DB, Finding k-shortest paths with limited overlap, VLDB J, 29, 1023-1047 (2020) · doi:10.1007/s00778-020-00604-x |
| [3] | City of New York (2019) Taxi Trips Record from the New York City Taxi & Limousine Commission [WWW Document]. https://www1.nyc.gov/site/tlc/about/tlc-trip-record-data.page. (Accessed 20 Jul 2020) |
| [4] | Cui Z, Henrickson K, Ke R, Wang Y (2019) Traffic graph convolutional recurrent neural network: A deep learning framework for network-scale traffic learning and forecasting. IEEE Trans Intell Transp Syst 21(11):4883-4894 |
| [5] | Diao, Z.; Wang, X.; Zhang, D.; Liu, Y.; Xie, K.; He, S., Dynamic Spatial-Temporal Graph Convolutional Neural Networks for Traffic Forecasting, Proc AAAI Confer Artif Intel, 33, 890-897 (2019) · doi:10.1609/aaai.v33i01.3301890 |
| [6] | DOT (2019) Intelligent Transportation Systems - Benefits of Intelligent Transportation Systems Fact Sheet [WWW Document]. https://www.its.dot.gov/factsheets/benefits_factsheet.htm. (Accessed 20 Jul 2020) |
| [7] | Duan, Y.; Lv, Y.; Liu, Y-L; Wang, F-Y, An efficient realization of deep learning for traffic data imputation, Transport Res C: Emerg Technol, 72, 168-181 (2016) · doi:10.1016/j.trc.2016.09.015 |
| [8] | Ermagun, A.; Levinson, D., Spatiotemporal traffic forecasting: review and proposed directions, Transp Rev, 38, 786-814 (2018) · doi:10.1080/01441647.2018.1442887 |
| [9] | Fountoulakis, M.; Bekiaris-Liberis, N.; Roncoli, C.; Papamichail, I.; Papageorgiou, M., Highway traffic state estimation with mixed connected and conventional vehicles: Microscopic simulation-based testing, Transport Res C: Emerg Technol, 78, 13-33 (2017) · doi:10.1016/j.trc.2017.02.015 |
| [10] | Frank, M., The Braess paradox, Math Program, 20, 283-302 (1981) · Zbl 0468.90078 · doi:10.1007/BF01589354 |
| [11] | Geng, X.; Li, Y.; Wang, L.; Zhang, L.; Yang, Q.; Ye, J.; Liu, Y., Spatiotemporal Multi-Graph Convolution Network for Ride-Hailing Demand Forecasting, Proc AAAI Confer Artif Intell, 33, 3656-3663 (2019) · doi:10.1609/aaai.v33i01.33013656 |
| [12] | Google (2020) TensorFlow [WWW Document]. TensorFlow. https://www.tensorflow.org/. (Accessed 23 Sept 2020) |
| [13] | Hochreiter, S.; Schmidhuber, J.; Mozer, MC; Jordan, MI; Petsche, T., LSTM can Solve Hard Long Time Lag Problems, Advances in Neural Information Processing Systems 9, 473-479 (1997), MIT Press |
| [14] | Hoffman, W.; Pavley, R., A Method for the Solution of the Nth Best Path Problem, J ACM, 6, 506-514 (1959) · Zbl 0100.13103 · doi:10.1145/320998.321004 |
| [15] | Hu, X.; Chiu, Y-C, A Constrained Time-Dependent K Shortest Paths Algorithm Addressing Overlap and Travel Time Deviation, Int J Transport Sci Technol, 4, 371-394 (2015) · doi:10.1016/S2046-0430(16)30169-1 |
| [16] | Jenelius, E.; Koutsopoulos, HN, Travel time estimation for urban road networks using low frequency probe vehicle data, Transport Res B: Methodol, 53, 64-81 (2013) · doi:10.1016/j.trb.2013.03.008 |
| [17] | Kawasaki, Y.; Hara, Y.; Kuwahara, M., Traffic State Estimation on a Two-Dimensional Network by a State-Space Model, Transport Res Proc, 38, 299-319 (2019) · doi:10.1016/j.trpro.2019.05.017 |
| [18] | Ke, J.; Zheng, H.; Yang, H.; Chen, X(, Short-term forecasting of passenger demand under on-demand ride services: A spatio-temporal deep learning approach, Transport Res C: Emerg Technol, 85, 591-608 (2017) · doi:10.1016/j.trc.2017.10.016 |
| [19] | Khan, SM; Dey, KC; Chowdhury, M., Real-Time Traffic State Estimation With Connected Vehicles, IEEE Trans Intell Transp Syst, 18, 1687-1699 (2017) · doi:10.1109/TITS.2017.2658664 |
| [20] | Kipf TN, Welling M (2017) Semi-Supervised Classification with Graph Convolutional Networks. https://arxiv.org/abs/1609.02907 |
| [21] | Kumar, A.; Haque, K.; Mishra, S.; Golias, MM, Multi-criteria based approach to identify critical links in a transportation network, Case Stud Transport Pol, 7, 3, 519-530 (2019) · doi:10.1016/j.cstp.2019.07.006 |
| [22] | Lin, L.; He, Z.; Peeta, S., Predicting station-level hourly demand in a large-scale bike-sharing network: A graph convolutional neural network approach, Transport Res C: Emerg Technol, 97, 258-276 (2018) · doi:10.1016/j.trc.2018.10.011 |
| [23] | Liu, H.; Jin, C.; Yang, B.; Zhou, A., Finding Top-k Shortest Paths with Diversity, IEEE Trans Knowl Data Eng, 30, 488-502 (2018) · doi:10.1109/TKDE.2017.2773492 |
| [24] | Liu, Z.; Liu, Y.; Meng, Q.; Cheng, Q., A tailored machine learning approach for urban transport network flow estimation, Transport Res C: Emerg Technol, 108, 130-150 (2019) · doi:10.1016/j.trc.2019.09.006 |
| [25] | Nantes, A.; Ngoduy, D.; Bhaskar, A.; Miska, M.; Chung, E., Real-time traffic state estimation in urban corridors from heterogeneous data, Transport Res C: Emerg Technol, Adv Network Traffic Manag: from Dynamic State Estimation Traffic Control, 66, 99-118 (2016) · doi:10.1016/j.trc.2015.07.005 |
| [26] | Papageorgiou, M.; Kiakaki, C.; Dinopoulou, V.; Kotsialos, A.; Wang, Y., Review of road traffic control strategies, Proc IEEE, 91, 2043-2067 (2003) · doi:10.1109/JPROC.2003.819610 |
| [27] | Polson, NG; Sokolov, VO, Deep learning for short-term traffic flow prediction, Transport Res C: Emerg Technol, 79, 1-17 (2017) · doi:10.1016/j.trc.2017.02.024 |
| [28] | Ralph J (2013) 2.5 quintillion bytes of data created every day. How does CPG & Retail manage it? [WWW Document]. IBM Consumer Products Industry Blog. https://www.ibm.com/blogs/insights-on-business/consumer-products/2-5-quintillion-bytes-of-data-created-every-day-how-does-cpg-retail-manage-it/. (Accessed 29 Dec 19) |
| [29] | Sekuła, P.; Marković, N.; Vander Laan, Z.; Sadabadi, KF, Estimating historical hourly traffic volumes via machine learning and vehicle probe data: A Maryland case study, Transport Res C: Emerg Technol, 97, 147-158 (2018) · doi:10.1016/j.trc.2018.10.012 |
| [30] | Seo, T.; Bayen, AM; Kusakabe, T.; Asakura, Y., Traffic state estimation on highway: A comprehensive survey, Annu Rev Control, 43, 128-151 (2017) · doi:10.1016/j.arcontrol.2017.03.005 |
| [31] | Sheffi Y (1975) Urban Transportation Networks | Professor Yossi Sheffi [WWW Document]. https://sheffi.mit.edu/book/urban-transportation-networks. (Accessed 2 Mar 2020) |
| [32] | Tan, H.; Feng, G.; Feng, J.; Wang, W.; Zhang, Y-J; Li, F., A tensor-based method for missing traffic data completion, Transport Res C: Emerg Technol, 28, 15-27 (2013) · doi:10.1016/j.trc.2012.12.007 |
| [33] | Thapa, D.; Paleti, R.; Mishra, S., Overcoming challenges in crash prediction modeling using discretized duration approach: An investigation of sampling approaches, Accident; Anal Prevent, 169 (2022) · doi:10.1016/j.aap.2022.106639 |
| [34] | Wang, Y.; Zhang, D.; Liu, Y.; Dai, B.; Lee, LH, Enhancing transportation systems via deep learning: A survey, Transport Res C: Emerg Technol, 99, 144-163 (2019) · doi:10.1016/j.trc.2018.12.004 |
| [35] | World Bank (2019) Urban population ( |
| [36] | Wu, C.; Thai, J.; Yadlowsky, S.; Pozdnoukhov, A.; Bayen, A., Cellpath: Fusion of cellular and traffic sensor data for route flow estimation via convex optimization, Transport Res C: Emerg Technol, 59, 111-128 (2015) · doi:10.1016/j.trc.2015.05.004 |
| [37] | Xu, D.; Wei, C.; Peng, P.; Xuan, Q.; Guo, H., GE-GAN: A novel deep learning framework for road traffic state estimation, Transportation Res C: Emerg Technol, 117 (2020) · doi:10.1016/j.trc.2020.102635 |
| [38] | Yang, S.; Ma, W.; Pi, X.; Qian, S., A deep learning approach to real-time parking occupancy prediction in transportation networks incorporating multiple spatio-temporal data sources, Transport Res C: Emerg Technol, 107, 248-265 (2019) · doi:10.1016/j.trc.2019.08.010 |
| [39] | Yao H, Wu F, Ke J, Tang X, Jia Y, Lu S, Gong P, Ye J Li Z (2018, April) Deep multi-view spatial-temporal network for taxi demand prediction. In Proceedings of the AAAI conference on artificial intelligence (Vol. 32, No. 1) |
| [40] | Yen, JY, Finding the K Shortest Loopless Paths in a Network, Manage Sci, 17, 712-716 (1971) · Zbl 0218.90063 |
| [41] | Yeon, J.; Elefteriadou, L.; Lawphongpanich, S., Travel time estimation on a freeway using Discrete Time Markov Chains, Transport Res B: Methodol, 42, 325-338 (2008) · doi:10.1016/j.trb.2007.08.005 |
| [42] | Yu B, Li M, Zhang J, Zhu Z (2019) 3D Graph Convolutional Networks with Temporal Graphs: A Spatial Information Free Framework For Traffic Forecasting. https://arxiv.org/abs/1903.00919 |
| [43] | Yu, H.; Wu, Z.; Wang, S.; Wang, Y.; Ma, X., Spatiotemporal Recurrent Convolutional Networks for Traffic Prediction in Transportation Networks, Sensors, 17, 1501 (2017) · doi:10.3390/s17071501 |
| [44] | Zhan, X.; Hasan, S.; Ukkusuri, SV; Kamga, C., Urban link travel time estimation using large-scale taxi data with partial information, Transport Res C: Emerg Technol, 33, 37-49 (2013) · doi:10.1016/j.trc.2013.04.001 |
| [45] | Zheng, F.; Van Zuylen, H., Urban link travel time estimation based on sparse probe vehicle data, Transport Res C: Emerg Technol, 31, 145-157 (2013) · doi:10.1016/j.trc.2012.04.007 |
| [46] | Zhu, L.; Guo, F.; Polak, JW; Krishnan, R., Urban link travel time estimation using traffic states-based data fusion, IET Intel Transport Syst, 12, 651-663 (2018) · doi:10.1049/iet-its.2017.0116 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
