Providing accurate and reliable travel time information to travellers is essential to improve the quality of public transit systems. With the availability of the latest technologies, it has become possible to collect a large amount of traffic data to analyze and understand these systems better. Traffic in India is characterized by lack of lane discipline and the presence of vehicles of varying static and dynamic characteristics, which makes prediction of bus travel time especially challenging. The aim of this study is to identify both a prediction algorithm that can handle high variability and suitable inputs or regressors to be used. Earlier studies performed offline manual grouping considering the patterns observed, which leads to limitations for automated field implementations. The present study explores the use of data-driven approaches, primarily clustering, to address the challenges for the prediction of bus travel time trends. Discrete wavelet transform (DWT) was used to extract trends from the travel time measurements. Three popular clustering algorithms—k-means, hierarchical, and self organizing maps (SOM)—were used to identify patterns. Travel time trends were then predicted by searching for similar cluster patterns within the historical database using pattern sequence-based forecasting (PSF). A comparison of the performance of these algorithms was carried out based on prediction errors. The clustering +prediction framework developed was also compared with the case when no clustering was done on the regressor dataset.
Get full access to this article
View all access options for this article.
References
1.
ZhangM.XiaoF.ChenD.Bus Arrival Time Prediction Based on GPS Data. Proc., 4th International Conference on Transportation Engineering, ICTE 2013, China, American Society of Civil Engineers, 2013, pp. 1470–1475.
2.
BinY.ZhongzhenY.BaozhenY.Bus Arrival Time Prediction Using Support Vector Machines. Journal of Intelligent Transportation Systems, Vol. 10, No. 4, 2006, pp. 151–158.
3.
KumarS. V.VanajakshiL.SubramanianS. C.A Model Based Approach to Predict Stream Travel Time Using Public Transit as Probes. Proc., 2011 IEEE Intelligent Vehicles Symposium (IV), Baden-Baden, Germany, IEEE, New York, 2011, pp. 101–106.
4.
KwonJ.CoifmanB.BickelP.Day-to-Day Travel-Time Trends and Travel-Time Prediction from Loop-Detector Data. Transportation Research Record: Journal of the Transportation Research Board, 2000. 1717: 120–129.
5.
VlahogianniE. I.KarlaftisM. G.GoliasJ.KourbelisN.Pattern-Based Short-Term Urban Traffic Predictor. Proc., 2006 IEEE Intelligent Transportation Systems Conference, Toronto, Ontario, Canada, IEEE, New York, 2006, pp. 389–393.
6.
KumarS. V.VanajakshiL.Pattern Identification Based Bus Arrival Time Prediction. Proc., Institution of Civil Engineers-Transport, Vol. 167, No. 3, Thomas Telford Ltd., 2014, pp. 194–203.
7.
KumarB. A.VanajakshiL.SubramanianS. C.Pattern-Based Bus Travel Time Prediction under Heterogeneous Traffic Conditions. Presented at 93rd Annual Meeting of the Transportation Research Board, Washington, D.C., 2014.
8.
Van Der VoortM.DoughertyM.WatsonS.Combining Kohonen Maps with ARIMA Time Series Models To Forecast Traffic Flow. Transportation Research, Vol. 4, No. 5, 1996, pp. 307–318.
9.
JainA. K.MurtyM. N.FlynnP. J.Data Clustering: A Review. ACM Computing Surveys (CSUR), Vol. 31, No. 3, 1999, pp. 264–323.
10.
MacqueenJ.Some Methods for Classification and Analysis of Multivariate Observations. Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, Vol. 1, No. 233, 1967, pp. 281–297.
11.
BradleyP. P. S.FayyadU.ReinaC.Scaling Clustering Algorithms to Large Databases. Proc., 4th International Conference on Knowledge Discovery and Data Mining. AAAI Press, New York, 1998, pp. 9–15.
12.
KaufmanL.RousseeuwP. J.Finding Groups in Data: An Introduction to Cluster Analysis. John Wiley & Sons, Inc., Vol. 344, New Jersey, 2009. http://dx.doi.org./10.1002/9780470316801
13.
ShavlikJ. W.DietterichT. G.Readings in Machine Learning. Morgan Kaufmann, Inc., San Mateo, California, 1990.
14.
KohonenT.The Self-Organizing Map. Proceedings of the IEEE, Vol. 78, No. 9, 1990, pp. 1464–1480.
15.
EsterM.KriegelH. P.SanderJ.XuX.A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. Knowledge Discovery and Data Mining, Vol. 96, No. 34, 1996, pp. 226–231.
16.
GrabustsP.BorisovA.Using Grid-Clustering Methods in Data Classification. Proc., International Conference on Parallel Computing in Electrical Engineering, PARELEC 2002, Warsaw, Poland, IEEE, New York, 2002, pp. 425–426.
17.
GanG.MaC.WuJ.Data Clustering: Theory, Algorithms, and Applications. ASA-SIAMSeries on Statistics and Applied Probability, Vol. 20, Philadelphia, 2007.
18.
AghabozorgiS.Seyed ShirkhorshidiA.Ying WahT.Time-Series Clustering – A Decade Review. Information Systems, Vol. 53, 2015, pp. 16–38.
19.
ChungE.Classification of Traffic Pattern. Proc., 11th World Congress on ITS, Chicago, 2003, pp. 687–694.
20.
LadinoA.KibangouA.FouratiH.De WitC. C.Travel Time Forecasting from Clustered Time Series via Optimal Fusion Strategy. Proc., 2016 European Control Conference, ECC 2016, Aalborg, Denmark, IEEE, New York, 2017, pp. 2234–2239.
21.
ParkD.RilettL.Forecasting Multiple-Period Freeway Link Travel Times Using Modular Neural Networks. Transportation Research Record: Journal of the Transportation Research Board, 1998. 1617: 163–170.
22.
WeigangL.KoendjbiharieW.de M JucaR. C.YamashitaY.MacIverA.Algorithms for Estimating Bus Arrival Times Using GPS Data. Proc., IEEE 5th International Conference on Intelligent Transportation Systems, Singapore, IEEE, New York, 2002, pp. 868–873.
23.
JeongR.RilettL.The Prediction of Bus Arrival Time Using AVL Data. Presented at 83rd Annual Meeting of the Transportation Research Board, Washington, D.C., 2004.
24.
BertiniR. L.El-GeneidyA. M.Modeling Transit Trip Time Using Archived Bus Dispatch System Data. Journal of Transportation Engineering, Vol. 130, No. 1, 2004, pp. 56–67.
25.
PatnaikJ.ChienS.BladikasA.Estimation of Bus Arrival Times Using APC Data. Journal of Public Transportation, Vol. 7, No. 1, 2004, p. 1.
26.
AbdelfattahA. M.KhanA. M.Models for Predicting Bus Delays. Transportation Research Record, Journal of the Transportation Research Board, 1998. 1623: 8–15.
27.
RajbhandariR.Bus Arrival Time Prediction Using Stochastic Time Series and Markov Chains. Ph.D. thesis, New Jersey Institute of Technology, Newark, New Jersey, 2004.
28.
SuwardoW.NapiahM.KamaruddinI.ARIMA Models for Bus Travel Time Prediction. Journal of the Institute of Engineers Malaysia, Vol. 71, No. 2, 2010, pp. 49–58.
29.
KumarS. V.VanajakshiL.Short-Term Traffic Flow Prediction Using Seasonal ARIMA Model with Limited Input Data. European Transport Research Review, Vol. 7, No. 3, 2015, pp. 1–9.
30.
VanajakshiL.SubramanianS. C.SivanandanR., R. Travel Time Prediction Under Heterogeneous Traffic Conditions Using Global Positioning System Data from Buses. IET Intelligent Transport Systems, Vol. 3, No. 1, 2009, pp. 1–9.
31.
PadmanabanR. P. S.VanajakshiL.SubramanianS. C.Estimation of Bus Travel Time Incorporating Dwell Time for APTS Applications. Proc., 2009 IEEE Intelligent Vehicles Symposium, Xi’an, China, IEEE, New York, 2009, pp. 955–959.
32.
KumarB. A.VanajakshiL.SubramanianS. C.Bus Travel Time Prediction Using a Time-Space Discretization Approach. Transportation Research Part C: Emerging Technologies, Vol. 79, 2017, pp. 308–332.
33.
ChienS. I. J.DingY.WeiC.Dynamic Bus Arrival Time Prediction with Artificial Neural Networks. Journal of Transportation Engineering, Vol. 128, No. 5, 2002, pp. 429–438.
34.
YuB.YangZ. Z.ChenK.YuB.Hybrid Model for Prediction of Bus Arrival Times at Next Station. Journal of Advanced Transportation, Vol. 44, No. 3, 2010, pp. 193–204.
35.
FanW.GurmuZ.Dynamic Travel Time Prediction Models for Buses Using only GPS Data. International Journal of Transportation Science and Technology, Vol. 4, No. 4, 2015, pp. 353–366.
36.
AlvarezF. M.TroncosoA.RiquelmeJ. C.RuizJ. S. A.Energy Time Series Forecasting Based on Pattern Sequence Similarity. IEEE Transactions on Knowledge and Data Engineering, Vol. 23, No. 8, 2011, pp. 1230–1243.
37.
JinC. H.PokG.LeeY.ParkH. W.KimK. D.YunU.RyuK. H.A SOM Clustering Pattern Sequence-Based next Symbol Prediction Method for Day-Ahead Direct Electricity Load and Price Forecasting. Energy Conversion and Management, Vol. 90, 2015, pp. 84–92.
Alvarez-RamirezJ.RodriguezE.EcheverríaJ. C.Detrending Fluctuation Analysis Based on Moving Average Filtering. Physica A: Statistical Mechanics and its Applications, Vol. 354, 2005, pp. 199–219.
40.
FriedR.EinbeckJ.GatherU.Weighted Repeated Median Smoothing and Filtering. Journal of the American Statistical Association, Vol. 102, No. 480, 2007, pp. 1300–1308.
41.
DashS.MauryaM. R.VenkatasubramanianV.RengaswamyR.A Novel Interval-Halving Framework for Automated Identification of Process Trends. American Institute of Chemical Engineers Journal, Vol. 50, No. 1, 2004, pp. 149–162.
42.
NeuristiqueL. B.BengioY.Convergence Properties of the K-Means Algorithms. Proc., 7th International Conference on Neural Information Processing Systems, Denver, Colo., MIT Press, Cambridge, Mass., 1995, pp. 585–592.
43.
ThorndikeR. L.Who Belongs in the Family?Psychometrika, Vol. 18, No. 4, 1953, pp. 267–276.
44.
DunnJ. C.Well-Separated Clusters and Optimal Fuzzy Partitions. Journal of Cybernetics, Vol. 4, No. 1, 1974, pp. 95–104.
45.
UltschA.Self-Organizing Neural Networks for Visualization and Classification. In Information and Classification (OpitzO.LausenB.KlarR., eds.), Springer-Verlag, Berlin, 1993, pp. 307–313.
46.
KohaviR.A Study of Cross-Validation and Bootstrap for Accuracy Estimation and Model Selection. Proc., International Joint Conference on Artificial Intelligence (IJCAI), Canada, Morgan Kaufmann, Inc., California, Vol. 5, 1995, pp. 1–7.
47.
ArlotS.CelisseA.A Survey of Cross-Validation Procedures for Model Selection. Statistics Surveys, Vol. 4, 2010, pp. 40–79.
