Jinglin Li, Jie Gao, Yu Yang, Heran Wei

State Key Laboratory of Network and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China

* The corresponding author, email:jlli@bupt.edu.cn

I. INTRODUCTION

Internet of Vehicle (IoV) [1] is an open converged network system with high manageability, controllability, operability and trustworthiness. It is composed of multiple users, vehicles, things and networks. IoV improves the computability, extensibility and sustainability of complex network systems and information services by means of obtaining, managing and computing the large scale complex and dynamic data of humans, vehicles, things, and environments [2][3].

How to predict the bus arrival time accurately is an important services in IoV. It allows passengers to plan their trips more reasonable,and decreases their waiting time [4]. However,the precise prediction of bus arrival time is still challenging due to a number of stochastic factors (e.g., traffic congestion, weather conditions and intersection delays). A variety of methods have been adopted in the Bus Arrival Time (BAT) prediction, including the Kalman Filtering (KF), Time Series Regression (TSR),Artificial Neural Network (ANN), K Nearest Neighbor (KNN), Support Vector Machine(SVM) and Support Vector Regression (SVR),BP neural network, etc.[5] Kalman Filtering(KF) models [6] are widely used for predicting bus arrival time, since they can update the state variables with changing observation continuously. KF algorithms generate a dynamic estimation result. And the result provides higher accuracy in single-step prediction while the other models usually lack. But in multi-step prediction, the accuracy decreases significantly. Time series models and regression models [5][7] are typical statistical models.Time series models are based on the assumption that the historical pattern will remain the same in the future. They highly depend on the correspondence between the real-time and historical traffic patterns. Whereas, regression models predict bus arrival times with a mathematical function. The function is formed by a set of independent variables such as number of stops, boarding and alighting passengers and weather conditions. However, it is a tough procedure to recognize and incorporate all these related variables. Machine learning models have been gaining popularity in predicting bus arrival time recently. ANN models [8] are able to capture the complex non-linear relationship between travel time and the independent variables. SVM and SVR [9] are featured as their time-series analysis and statistical learning ability. Unlike the traditional ANN,SVM is not amenable to the over fitting problem. However, a large amount of computation time will be involved when SVM is applied for solving large size problems. Sinn [10] provides the analysis on the prediction accuracy through compassion among delay based, Linear Regression, KNN and Kernel Regression.However, the unstable traffic pattern in urban areas makes these models unreliable. Similarity exists between long-term prediction and[11]. But, the main idea of [11] is finding nearest one from historical trajectories, in contrast,it is proposed in this paper that long-term bus arrival prediction performs accurately. Chan[12] proposes a neural network based model exploiting the hybrid exponential smoothing method and the Levenberg–Marquardt algorithm for short-term traffic flow forecasting.However, the architecture is shallow and designed with one single hidden layer. Recently,with the development of machine learning,a deep-learning-based traffic flow prediction method is proposed [13], which considers the spatial and temporal correlations inherently.The prediction layer simply employs a logistic regression which is not a powerful predictor,some powerful predictors should be taken into consideration to improve the performance further.

This paper presents a method to forecast the running time based on a mixed model. The model divides BAT prediction into the single-step and multi-step which is demonstrated essentially by the experimental results.

In this paper, we discovered the pattern of traffic incident influences from historical traffic data. The influences of traffic incident are manifested as traffic delay jitter. Those similar traffic incidents would have similar relative time delay influences. Based on the content above, we propose a new mixed model supported by KNN, K-means, KF and Markov chain (KKM) for bus arrival time prediction.The KKM model uses the traffic delay fluctuation instead of absolute traffic time for evaluation and pattern training. The traffic delay fluctuation pattern then is used to adjust single-step prediction supported by Kalman filter.Besides, it is also utilized to adjust multi-step prediction supported by Markov historical transfer model.

The remaining parts of this paper are organized as follows: Section II proposes the KKM model for BAT prediction, and then introduces pattern training, single-step prediction and multi-step prediction parts. Section III describes data set and data processing. Section IV analyzes the experimental results. Section V is the conclusion and the outlook for future work.

II. PREDICTION METHODOLOGY

Lin [14] and his team proposed a BAT prediction model based on average speed of road section and instant speed. However, waiting time engendered by crossroad traffic light or intersection congestion cannot be directly calculated or recognized by real-time GPS data. Thus, it is not comprehensive to forecast simply according to the real-time data. Specifically, we analyzed the distribution of the bus section travel time in Hefei, China, as shown in Fig. 1, where the horizontal axis denotes the normalized moment and the vertical axis denotes the travel time. We could deduce that,evidently, BAT has some distribution regularities and the results are in accordance with the theory.

The flow chart of the KKM algorithm is shown in Fig. 2. In this paper, we proposed a KKM algorithm which contains three parts,which are pattern training, single step prediction and multistep prediction.

Firstly, in order to analyze the distribution regularities, we trained the bus travel time in the historical database into fluctuation patterns. After that a non-parametric approach using K-Nearest Neighbor was taken into consideration. Secondly, since the short distance bus arrival time and the current bus travel time which passed the trajectory within 5 minutes have a close connection [15]. We combined a dynamic Kalman filter that adaptively adjusts live data with KNN modification for single-step prediction. Thirdly, when the distance from the bus location to the target stop exceed 3km, the historical law is more obvious than the real-time traffic in long prediction. In this way, the leading single-step prediction model fails to conduct an accurate prediction. On the basis of this, the single-step prediction results are dynamically adjusted with the Markov transfer model to predict the multistep BAT.And the Markov transfer model is based on the abundant historical data to predict the multistep BAT.

2.1 Pattern training

As the impact of high-rise buildings, some GPS data we collected are biased or incorrect,the GPS data cannot be used as input data for prediction model directly. The data should be processed before it is applied [16]. After noise correction, backward error modification and measurement error amendment, the processed data are stored in the database. Then it could be used as input data for KNN training or K-means clustering.

The essence of KNN approach is to identify, in the time series, the past sequences which are the most similar to the current one, and to combine their future values to predict the next value of the current sequence. In this paper,we adopt the time fluctuation instead of direct time value as the KNN state vector. So we can get the prediction of fluctuation pattern in time distribution. Therefore, state vector is defined as follows:

Fig. 1 Normalized distribution of section travel time

Fig. 2 Flow chart of proposed KKM algorithm

For Markov transfer database that is applied in multi-step prediction, the main idea is to calculate the transition probability of each time period from the history data. The method of extraction influences the accuracy of the prediction. In data mining area, K-means clustering is a popular cluster analysis method of vector quantization. It aims to partitionobservations intoclusters in which each observation belongs to the cluster with the nearest mean, serving as a prototype of the cluster.Meanwhile, distribution of the bus arrival time, which is illustrated in Fig. 1, indicates that there are three major time patterns, including no delay, mild delay and severe delay.Therefore, for each period, arrival time ratios of each neighbor section are clustered into 3 centroids, which meansThe transition possibilities to each centroid in every time period are calculated afterwards. In multi-step prediction, after classifying the arrival time into corresponding time interval, it can transfer to a certain centroid with maximum probability.

2.2 Single-step prediction

The idea of single-step prediction model is to calculate the bus travel time on the basis of real-time traffic flow and the historical fluctuation pattern. After taking these two factors into account, the bus travel time for single step prediction is defined as:

As for the correlation [4] in time series, a modified Kalman filter for real-time prediction is considered to serve as real-time predictionOn the other side, as for the fluctuation distribution rule in time series, we retrievenearest neighbor trajectories from historical trajectories, using the available, partial real-time trajectory. Thus, historical fluctuation pattern modificationcan be denoted by KNN prediction.

1) Dynamic Kalman filtering prediction

The Kalman filter is a linear recursive predictive update algorithm. It is used to estimate the parameters of a process model. Starting with initial estimates, the Kalman filter is adjusted with each new measurement. Thus,travel time collected by buses on the same way ahead can be used as the real-time observation. And the observation could amend the Kalman filter prediction for the buses behind from time to time.

The fundamental Kalman filter can be formulated as follows:

For Kalman filter with dynamic adjustment,the Kalman gainis calculated for each prediction. And the state variableas well as the covarianceis updated timely.denotes the covariance of prior probability. The status update equation of Kalman filtering is given by:

In the update phase, the prediction is integrated with the current observation value to refine the state estimate, and adjust the predicted single-step travel time.

2) K-Nearest Neighbor modification

In this paper, we measure the similarity by using Euclidean distance [17]. The distance between the input new state vectorand all the past state vectoris calculated as

where

2.3 Multi-step prediction

The idea of multi-step prediction is to combine the proposed single-step prediction with Markov chains to dynamically conduct a multistep prediction. The Markov chains is based on historical transfer possibility.

The defining feature of Markov chain is that the probability distribution of the next state depends only on the current state. It is not depends on the sequence of events that preceded it [17]. Because of the independency of each period traffic flow at different bus stop,Markov chain is applied to predict the arrival time. To achieve that, the Markov chain uses the history transfer database. The multi-step prediction progress is outlined as four steps.

Step 1: Find the maximum Markov transition probabilitywhich the bus arrival timebelongs to. Then the predicted arrival time of the next stopcan be expressed as:

Step 2: Calculate the bus travel time predicted by historical data from stop towhich can be illustrated as:

Step 3: Integrate the historical pattern and single-step prediction with a dynamically adjusted method, thus the multi-step prediction algorithm is defined as:

After that, we get the predicted arrival time at stop

Step 4: Repeat step 1, 2, and 3. It stops until achieving the given steps provided by the multistep prediction.

III. DATA SET AND PROCESSING

To verify the effectiveness of our prediction approach, we experimented on a real world dataset. The GPS data of this study is collected from public buses in the city of Hefei, China.The complete data set contains about more than 57 million GPS data points. Each GPS data point contains information of the position of the bus (i.e., longitude and latitude), date and time stamp, bus ID, speed and direction.We choose bus line 149 (Andaxingqu to west of Zhonglv Square) as test bed line. The exact route of bus line 149 is shown in Fig.3. There are 35 stops in total, and the dots are corresponding to the locations of bus stops.

Fig. 3 Route of the Hefei bus line 149

Fig. 4 KKM Single Step Prediction in the peak hour

We process the real world GPS data according to “probe bus fleet (PBF)” [4] method. The PBF method forecasts the running time of the bus in the next section based on the running times of its previous buses. The running time here means the time spent by a bus travelling from the start to the end of a section. PBF refers to those road sections divided by different running method, average speed, running time and transportation flow. Since there are numerous bus routes in a city, the overlaps occurs among different bus routes in the same road sections while the bus lines maybe different. All the public vehicles in the same road sections are called one “dynamic bus fleet(DBF)”. The running time of the buses ahead in DBF can be used as the basis to forecast the running time of the afterward vehicles [19].

Typically, instead of limiting the test data for bus line 149, we use the test data collected from the buses based on dynamically establishing and disassembling of the DBF. As a result, this test bed line can obtain enough test data and cover most of algorithm scenarios. It is capable of verifying the proposed algorithm.

IV. RESULT AND ANALYSIS

4.1 Performance measurement

We compare our method with other typical methods by using the Mean Absolute Percentage Error (MAPE) which is defined as follows:

4.2 Prediction results and analysis

Our method has been implemented by Matlab and Libsvm tool. To verify the feasibility and suitability of the calculation method presented in this paper, the bus line 149 of Hefei in China is selected to do the analysis of the data of running time. In single-step prediction,presents the weighting of dynamic Kalman filter prediction andpresents the KNN fluctuation modification. The coefficients are very important to forecasting results. In this research,is set to 0.9 whileis set to 0.8 which are the best value found by the simula-tion results.

1) Evaluation of Single Step Prediction

As shown in Fig. 4 and Fig. 5, single-step prediction conducts on certain stops. The prediction algorithm based on short-term traffic flow and dynamic Kalman filter is efficient in a traffic jam, however performing not well in off-peak hour. The main reason is these two algorithms have not considered the distribution in time series. The experimental result shows that the single step prediction algorithm promoted in this paper is less affected by the high or low peaks. The algorithm has higher more stability and consistency.

In the event of an accident, as shown in Fig. 6, it is found that single-step prediction and short-term traffic flow perform better than KNN alone, indicating the proposed algorithm supports real-time adjustment. Besides, the single-step prediction has a less volatility than the short-term traffic flow to obtain more accurate and stable BAT.

2) Evaluation of multi-step prediction

The experiments in Fig.7 and Fig.8 are set as the bus travel time prediction between the 13th stop and 18th stop, aiming at evaluating the performance of the three algorithms in multistep prediction. From the results, multistep prediction proposed in this paper outperforms in accuracy and stability among the three algorithms. The algorithm based on historical pattern model performs well in off-peak hour making use of abundant history data,behaving badly in the peak hour, while the algorithm based on KNN is in reverse. The error of multi-step prediction is 10% in average and not greater than 25% in worst case in off-peak hour which has better performance than the other two algorithms, which also works with peak hour.

Fig. 5 KKM Single Step Prediction in the off-peak hour

Fig. 6 KKM Single Step Prediction in the accident

Fig. 7 KMM Multi-Step Prediction in the peak hour

From Fig.9, we can see that either historical pattern model or KNN is not sensitive when accident happens, because both of them merely using historical data. The MAPE of short –term traffic flow fluctuates wildly. The peak value of multi-step prediction’s MAPE is around 0.5, mainly because of the decreasing of actual travel time. It makes the MAPE whose denominator is just the actual travel time increased a lot.

The experiment in Fig.10 is set as the bus travel time prediction for different bus stops starting from the 13th stop. As we can see from the results, with the stops of prediction increasing, the MAPE of multi-step algorithm increases as well, while the MAPE of KNN and historical pattern is fluctuant. Experimental results show that the MAPE of multi-step prediction is less than the other algorithm in both peak and off-peak hours and in the accident. Our proposed method has relatively high precision and stability for predicting bus arrival time. Thus it can be applied to the intelligent transport system.

V. CONCLUSION AND FUTURE STUDY

This paper presents a method to forecast the running time based on a mixed model. The model divides BAT prediction into the single-step and multi-step which is demonstrated essentially by the experimental results. In single-step prediction, we took both the real-time traffic flow and traffic delay jitter patterns into account. In this way, we could conduct a more accurate prediction than the short-term traffic flow prediction, Kalman filter and KNN separately. In addition, the multi-step prediction provides a higher level of veracity and reliability of travel time forecasting than the short-term traffic flow prediction and historical traffic patterns. Furthermore, the proposed mixed method can cope abnormal conditions such as road accident rapidly and obtain more accurate bus arrival time.

In the future, we plan to investigate further strategies to reduce the computational burden,both in terms of memory and computational time. Because the computation of KNN and Markov transfer model requires a quantity of memory space. Otherwise, further problems are how to determine and regulate the dynamic adjustment factors (e.g., more feedback mechanism are needed).

ACKNOWLEDGEMENTS

This work has been performed in the National Science and Technology Major Project(2016ZX03001025-003) and Special Found for Beijing Common Construction Project.

[1] F. C. Yang, S. G. Wang, J. L. Li, et al. An Overview of Internet of Vehicles,China Commun,11(10):1-15, 2014.

[2] N. Lu, N. Cheng, N. Zhang, et al. Connected vehicles: Solutions and challenges.IEEE Internet of Things Journal, 1(4): 289-299, 2014.

[3] G. Dimitrakopoulos. Intelligent transportation systems based on internet-connected vehicles:Fundamental research areas and challenges.IEEE 11th International Conference, pages 145-151, 2011.

[4] H. Gao, J. L. Li, F. Yang. Bus Arrival Time Prediction Based on Probe Bus Fleet. In2ndInternational Conference on Transportation Information and Safety (ICTIS), pages 773-779, 2013.

[5] J. Patnaik, S. Chien, A. Bladikas. Estimation of bus arrival times using APC data.Journal of Public Transportation, Vol. 7, 2004.

[6] L. Vanajakshi, S. C. Subramanian, R. Sivanandan.Travel time prediction under heterogeneous traffic conditions using global positioning system data from buses.IET intelligent transport systems, 3(1): 1-9, 2009.

[7] S. Ishak, H. Al-Deek. Performance evaluation of short-term time-series traffic prediction model.Journal of Transportation Engineering, 128(6):490-498, 2002.

[8] S. I. J. Chien, Y. Ding, C. Wei. Dynamic bus arrival time prediction with artificial neural networks.Journal of Transportation Engineering, 128(5):429-438, 2002.

[9] B. Yu, Z. Yang, B. Yao. Bus arrival time prediction using support vector machines.Journal of Intelligent Transportation Systems, 10(4): 151-158,2006.

[10] Sinn, Mathieu, et al. predicting arrival times of buses using real-time GPS measurements. In15th International IEEE Conference on Intelligent Transportation Systems, 2012.

Fig. 10 KMM Multi-Step Prediction in different bus stop

[11] D. Tiesyte, and C. S. Jensen. Similarity-based prediction of travel times for vehicles traveling on known routes.Proceedings of the 16th ACM SIGSPA Tl AL international conference on Advances in geographic information systems. ACM,2008.

[12] K.Y. Chan, et al. Neural-network-based models for short-term traffic flow forecasting using a hybrid exponential smoothing and Levenberg–Marquardt algorithm.IEEE Transactions on Intelligent Transportation Systems. 13(2): pages 644-654, 2012.

[13] W. Huang, et al. Deep architecture for traffic flow prediction: Deep belief networks with multitask learning.IEEE Transactions on Intelligent Transportation Systems. 15(5): pages 2191-2201,2014.

[14] W.-H. Lin, J. Zeng. Experimental study of real-time bus arrival time prediction with GPS data.Transportation Research Record: Journal of the Transportation Research Board 1666.-1, pages 101-109, 1999.

[15] J. Dong, L. Zou, Y. Zhang. Mixed model for prediction of bus arrival times.Evolutionary Computation (CEC), 2013 IEEE Congress on.IEEE,pages 2918-2923, 2013.

[16] T. Zhu, et al. The bus arrival time service based on dynamic traffic information.Application of Information and Communication Technologies(AlCT), 6th International Conference on. IEEE,2012.

[17] J. Arroyo, C. Mate. Forecasting histogram time series with k-nearest neighbor methods.International Journal of Forecasting, Vol. 25, pages 192-207, 2009.

[18] R. Rajbhandari. Bus Arrival Time Prediction Using Stochastic Time Series and Markov Chains,New Jersey Institute of Technology, 2005.

[19] K. K. Sanwal, J. Walrand. Vehicles as probes.California Partners for Advanced Transit and Highways (PATH), 1995.