A two-stage short-term traffic flow prediction method based on AVL and AKNN techniques

Abstract

Short-term traffic flow prediction is one of the essential issues in intelligent transportation systems (ITS). A new two-stage traffic flow prediction method named AKNN-AVL method is presented, which combines an advanced k-nearest neighbor (AKNN) method and balanced binary tree (AVL) data structure to improve the prediction accuracy. The AKNN method uses pattern recognition two times in the searching process, which considers the previous sequences of traffic flow to forecast the future traffic state. Clustering method and balanced binary tree technique are introduced to build case database to reduce the searching time. To illustrate the effects of these developments, the accuracies performance of AKNN-AVL method, k-nearest neighbor (KNN) method and the auto-regressive and moving average (ARMA) method are compared. These methods are calibrated and evaluated by the real-time data from a freeway traffic detector near North 3rd Ring Road in Beijing under both normal and incident traffic conditions. The comparisons show that the AKNN-AVL method with the optimal neighbor and pattern size outperforms both KNN method and ARMA method under both normal and incident traffic conditions. In addition, the combinations of clustering method and balanced binary tree technique to the prediction method can increase the searching speed and respond rapidly to case database fluctuations.

Keywords

engineering of communication and transportation system / short-term traffic flow prediction / advanced k-nearest neighbor method / pattern recognition / balanced binary tree technique

References

[1] ShenW, WynterL. Real-time traffic prediction using GPS data with low sampling rates: A hybrid approach [C]. 91st Annual Meeting of the Transportation Research Board, 2012, Washington, D.C, TRB

[2] GuoF, KrishnanR, PolakJ W. Short-term traffic prediction under normal and abnormal traffic conditions on urban roads [C]. 91st Annual Meeting of the Transportation Research Board, 2012, Washington, D.C, TRB

[3] WuY J, ChenF, LuC T, SmithB L, ChenY. Traffic flow prediction for urban network using spatiotemporal random effects model [C]. 91st Annual Meeting of the Transportation Research Board, 2012, Washington, D.C, TRB

[4] XiaJ X, NieQ H, HuangW, QianZ D. Reliable short-term traffic flow forecasting for urban roads using multivariate GARCH model [C]. 92nd Annual Meeting of the Transportation Research Board, 2013, Washington, D.C, TRB

[5] SmithB L, WilliiamsB M, OswaldR K. Comparison of parametric and nonparametric models for traffic flow forecasting [J]. Transportation Research Part C, 2002, 10(4): 303-321

[6] GuoF, KrishnanR, PolakJ. A computationally efficient two-stage method for short-term traffic prediction on urban roads [J]. Transportation Planning and Technology, 2013, 36(1): 62-75

[7] WangY B, PapageorgiouM, MessmerA. Renaissance-a unified macroscopic model-based approach to real-time freeway network traffic surveillance [J]. Transportation Research Part C, 2006, 14(3): 190-212

[8] van LintJ W C, HoogendoornS P, van ZuylenH J. Accurate freeway travel time prediction with state-space neural networks under missing data [J]. Transportation Research Part C, 2005, 13(5/6): 347-369

[9] StathopoulosA, KarlaftisM G. A multivariate state space approach for urban traffic flow modeling and prediction [J]. Transportation Research Part C, 2003, 11(2): 121-135

[10] SunJ, ZhangL. Vehicle actuation based short-term traffic flow prediction model for signalized intersections [J]. Journal of Central South University of Technology, 2012, 19(1): 287-298

[11] SunH, LiuH X, XiaoH, HeR R, RanB. Short-term traffic forecasting using the local linear regression model [C]. 82nd Annual Meeting of the Transportation Research Board, 2003, Washington, D.C, TRB

[12] HuangD, SongJ, WangD, CaoJ, LiW. Forecasting model of traffic flow based on ARMA and wavelet transform [J]. Computer Engineering and Applications, 2006, 42(36): 191-194

[13] WilliamsB M, HoelL A. Modeling and forecasting vehicular traffic flow as a seasonal ARIMA process: theoretical basis and empirical results [J]. Journal of Transportation Engineering-ASCE, 2003, 129(6): 664-672

[14] CoolsM, MoonsE, WetsG. Investigating the variability in daily traffic counts through use of ARIMAX and SARIMAX models [J]. Transportation Research Record, 200957-66

[15] ZhangN, ZhangY L, LuH T. Seasonal autoregressive integrated moving average and support vector machine models prediction of short-term traffic flow on freeways [J]. Transportation Research Record, 201185-92

[16] ChandraS R, Al-deekH. Predictions of freeway traffic speeds and volumes using vector autoregressive models [J]. Journal of Intelligent Transportation Systems, 2009, 13(2): 53-72

[17] WuC H, HoJ M, LeeD T. Travel-time prediction with support vector regression [J]. IEEE Transactions on Intelligent Transportation Systems, 2004, 15(4): 276-281

[18] WangJ, ShangP J, ZhaoX J. A new traffic speed forecasting method based on bi-pattern recognition [J]. Fluctuation and Noise Letters, 2010, 10(1): 59-75

[19] ChangH, LeeY, YoonB, BaekS. Dynamic near-term traffic flow prediction: System-oriented approach based on past experiences [J]. IEEE Transactions on Intelligent Transportation Systems, 2012, 6(3): 292-305

[20] van LintJ W C, Hoogendoorn, van ZuylenH J. Freeway travel time prediction with state-space neural networks: Modeling state-space dynamics with recurrent neural networks [J]. Transportation Research Record, 200230-39

[21] JiangX M, AdeliH. Dynamic wavelet neural network model for traffic flow forecasting [J]. Journal of Transportation Engineering-ASCE, 2005, 131(10): 771-779

[22] ZhengW, LeeD H, ShiQ. Short-term freeway traffic flow prediction: Bayesian combined neural network approach [J]. Journal of Transportation Engineering-ASCE, 2006, 132(42): 114-121

[23] SmithB L, OswaldR K. Effects of parameter selection on forecast accuracy and execution time in non-paramedic regression [C]. Proceeding of 2000 IEEE Intelligent Transportation Systems Conference, 2000, Dearborn, USA, IEEE: 252-257

[24] BoiF, GagliardiniL. A Support vector machines network for traffic sign recognition [C]. Proceeding of 2011 International Joint Conference on Neural Networks, 2011, San Jose, USA, IEEE: 2210-2216

[25] WangY, XiangY, ZhouW L, YuS Z. Generating regular expression signatures for network traffic classification in trusted network management [J]. Journal of Network and Computer Applications, 2012, 35(3): 992-1000

[26] AbdiJ, MoshiriB, AbdulhaiB, SedighA K. Forecasting of short-term traffic-flow based on improved neurofuzzy models via emotional temporal difference learning algorithm [J]. Engineering Applications of Artificial Intelligence, 2012, 25(5): 1022/042

[27] GuoJ H, WilliamsB M. Real-time short-term traffic speed level forecasting and uncertainty quantification using layered kalman filters [J]. Transportation Research Record, 201028-37

[28] LanL W, SheuJ B, HuangY S. Investigation of temporal freeway traffic patterns in reconstructed state spaces [J]. Transportation Research Part C, 2008, 16(1): 116-136

[29] GuinA. Travel time prediction using a seasonal autoregressive integrated moving average time series model [C]. Proceeding of 2006 IEEE Intelligent Transportation Systems Conference, 2006, Toronto, Canada, IEEE: 493-498