1. Introduction

Dynamic Route Guidance (DRG) as a part of Advance Traveller Information Systems (ATIS) aims to provide travelers with real-time information about traffic condition on routes. Due to the continuous change of traffic conditions in urban areas, travellers may select routes that will be congested during their trips. This problem can be overcomed by predicting traffic flow for a short time ahead to determine the status of all roads on routes during trips. Prediction makes DRG adaptive to the traffic changes on roads and enables travellers to choose the best routes which has the shortest travel time.

Traffic flow is time series data consisting of sequences of values that are measured at equal or unequal time intervals. It has complex characteristics due to the complexity of trans-portation network particularly in urban cities which contain many intersections with traffic lights controlling traffic flow on upstream and downstream roads. These characteristics include autocorrelation as the flow time series is correlated with its values in the past and the future [1-3]. The flow may also have a trend which describes the general direction of the time series [3], [4]. Further, the flow has seasonal patterns that are repeated every week and every day [5]. Furthermore, the flow exhibits overdispersion which indicates that its variance ex-ceeds its mean [5]. Addressing these characteristics increases the accuracy of traffic flow modeling.

Several data mining methods have been proposed to model traffic flow. These methods include the exponential smoothing methods such as the Holt-Winters (HW) method [4], the Autoregressive Integrated Moving Average (ARIMA) [2], [4], [6], and the Multivariate Structural Time Series (MST) [3]. Although these methods can properly model autocorrelated data with trends and the seasonality, they are sensitive to the high variation. Therefore, the accuracy of these methods may deteriorate when data become overdispersed. Furthermore, a space-time Negative Binomial regression has been proposed to model overdispersed traffic flow [5]. However, this model does not account for trends and seasonal patterns.

The only forecasting method that handles time series trend and seasonality characteristics as well as overdispersion is the Holt-Winters method for count data proposed by Taylor and known as HWT count data method [7]. This method combines the double seasonal Holt-Winters with the Negative Binomial distribution. The double seasonal Holt-Winters method allows for the simultaneous capturing of small seasons that exist in large seasons such as the daily season within the weekly season. The Negative Binomial distribution allows the variance to exceed the mean during the modeling process by involving an overdispersion coefficient. The HWT count data method was shown more accurate than other smoothing methods which do not handle overdispersion [7].

In this research, we propose a data mining method for modeling and forecasting traffic flow accurately. The proposed method utilizes the HWT count data method since the data used in this research are traffic flows lected from Taipei city and have all of the aforementioned characteristics. We model the weekly season as a large season and the daily season as a small season. The coefficients of overdispersion, trend, and seasonality are estimated during the training process using a likelihood function derived by Taylor [7].

The contribution of this research is firstly we propose a predictive DRG system by integrating an existing ATIS with prediction. We secondly propose a method that can be used to model and forecast the autocorrelated and overdispersed traffic flows. We thirdly compare the proposed method with the HW and the space-time NB regression methods, and we show that the proposed method outperforms the other two methods because it has smaller root mean square errors. This research also defines the temporal characteristics of traffic flow as seasonal patterns and categorizes these patterns into a weekly traffic season and a daily traffic season.

2. Related Work

As shown earlier, prediction is necessary for DRG. This sections reviews the most relevant methods that have been used for traffic flow forecasting in urban areas.

The field of data mining consists of variety of methods that are used to model or forecast time series [8], [9]. In traffic context, the accuracy of data mining methods that are used to model and forecast traffic flow time series depends on how these methods deal with its various characteristics. Here, we give a brief review of these methods in terms of which method can properly traffic flow temporal autocorrelation, trends, seasonal patterns, and overdispersion.

Several ARIMA based methods were used in the traffic context as in [2], [4], [6]. These methods were used to model different traffic variables such as speed, flow, or travel time. The strength of these methods is their ability to model autocorrelated data and capture the trends in the data. Also, these methods can be formulated as multivariate models to address the traffic conditions in several locations. However, the ARIMA based methods are usually sensitive to high variations and they become less accurate when data is overdispersed [7]. In traffic context, these methods were shown less accurate and more complex than the HW method [3], [4].

The HW method was used to model autocorrelated traffic flows measured from a single site since it is a univariate method [4]. The HW can capture trends and seasonal patterns in a single time series. For more accurate results, trends and seasonal patterns from different sites were treated with a multivariate structural time series (MST) [3]. However, these methods did not address the high variation or the overdis-persion of traffic flow. Ignoring the overdispersion may cause inaccurate forecast results [10].

To overcome overdispersion, a negative binomial regression that allows the variance to be greater than the mean was used to model traffic flows in Taipei city [5]. This method is called the space-time multivariate NB regression and models traffic flows from a set of correlated roads N. The multivariate space-time NB regression model can be written compactly as

(1)

where is the traffic flow value of the dependent road at time t, 1 ≤ d ≤ N, α is the intercept, β_i,j is the regression coefficient corresponding to road i at time j, n is the size of data, and η is the regression error vector where the error is independent of all covariates and distributed with mean = 1 and a variance= 1/φ. The results of this method were more accurate than the HW method and the MST method.

The main shortcoming of the space-time multivariate NB regression method is its ability to model limited autocorrelated data and consequently being incapable of addressing trends or seasonal patterns in the data. A better option is a method that can capture trends, seasonality, and overdispersion. To achieve this, we adopted the HWT count data method derived by Taylor [7] by combining the HW with the Negative Bino-mial distribution which is popular for modeling overdispersed counts.

3. The Proposed DRG System

We adopt an existing ATIS from Taipei city and add a prediction server so that the ATIS can provide predictive DRG services. The Traffic Control Center of Taipei city provides ATIS services as well as Intelligent Transportation Systems (ITS) services. The current ATIS consists of three blocks that are collecting data, processing data into information related to ITS and ATIS, and providing information to travellers [11]. The Taipei-ATIS relies on historical data and real time data of traffic flow and speed, which are stored in databases, to provide a web-based route planning service and information regarding traffic conditions. Traffic conditions of each road are displayed as coloured lines on the road network map.

The availability of future values of traffic flow enables the ATIS to provide better route choices and more realistic traffic condition. Such future values can be obtained by the prediction server which is added to the processing data block in the traffic control center servers. The ATIS can capture the high variations of traffic and adapt its output to the new traffic condition. Fig. 1 shows the overview architecture of the proposed ATIS.

Figure 1. The overview architecture of the ATIS that includes the proposed prediction model within the prediction server

A. ATIS Components

The main components of the ATIS are:

• Traffic data collection: The traffic control center in Taipei uses different techniques such as microwave radar, inductive loops and video camera to collect traffic data mainly flow, flow and speed. Traffic flow measured on each road segment can be available to ATIS servers after a short time. These flows are considered as real time data because they describe the current traffic condition. The data are stored in a database and after sometime these data become historical data which can be represented by time series. Other information related to incidents can be also fed to the ATIS.

• Traffic data Processing: The historical and real time traffic data are processed by the ATIS servers to information that is useful to travellers and traffic control staff. Information includes traffic conditions on roads, travel time of routes, events on roads, traffic density, traffic speed and real time video of roads. This component also contains the prediction sever. It also contains the ITS servers which participate in data processing and provide information for congestion control, traffic light control and other ITS services.

• ATIS information delivery: Travellers can obtain traffic information such as route plan, travel time, and traffic conditions on demand via web. We initially tested the web-based ATIS although a large scale ATIS employs other means of communication to provide its services. The ATIS servers handle the information to web servers which is responsible for communicating with travellers. Travellers can access the ATIS website by desktops or ubiquitously by mobile devices such as smart phones and navigational devices.

B. The prediction method

The prediction method used in the proposed DRG shown in Fig. 1 is derived from the standard Holt-Winters (HW) which is also known as the triple exponential smoothing method. The HW method is the most commonly employed approach for modeling autocorrelated time series and seasonal patterns. It was introduced as a forecasting method in 1960 [12]. The HW method uses a time series model to make predictions assuming that the future will follow the same pattern as the past. Its mathematical forms include a model for additive seasonal patterns where the size of the seasonal variation is not affected by the value of the observation, and a model for multiplicative seasonal patterns where higher values of observations cause larger seasonal variations [13]. We focus on the multiplicative HW model only because the data in the research exhibit a multiplicative seasonal pattern.

In the HW method, a series value, Y_t, is decomposed into three components: the level (L_t), the trend (T_t) which de-scribes the long term direction of the series, and the seasonality (S_t) [13]. The multiplicative HW method is formulated as follows

(2)

where µ_t is the mean value that is used to estimate the series, and the transition equations are

(3)

where t is the time, α, β, γ are the HW smoothing coefficients and m is the number of periods in one seasonal cycle which is defined as any periodic pattern of fixed length [13]. The smoothing model error, , is assumed to be independent and identically distributed following a Gaussian distribution with mean = 0 and variance= σ², i.e., ∼ NID (0, σ²) [13]. The smoothing coefficients α, β and γ are usually restricted between zero and one, and they should be selected carefully to minimize residual errors. The equation to forecast future values, , is given by

(4)

where q is the forecast horizon [13].

Usually data contain more than one cycle, hence Taylor developed a double seasonal Holt-Winters method that is called the HWT [14]. The developed method (HWT) improves the accuracy of the standard HW method [15]. The transition equations of the standard HW are modified to involve two seasonal indices, D_t and W_t instead of one seasonal index, S_t. The transition equations become

(5)

where m₁ represent the number of periods in the daily season D_t and m₂ represent the number of periods in the weekly season W_t. Future values can be forecasted as follows

(6)

where q is the forecast horizon.

The HW and the HWT methods do not handle overdis-persion. An improvement was proposed in [7] by combining the HWT with the NB distribution to allow the HW to model overdispersed count data. Overdispersed count data means that the variance is greater than the mean as σ² = µ + φµ² where µ is the mean, σ² is the variance, and φ is the overdispersion parameter [10]. In this case, Taylor showed that the smoothing coefficients α, β, γ and ω as well as the overdispersion parameters φ and ψ can be estimated by maximizing a likelihood function given by

(7)

where n is the size of data and Γ is the gamma function [7]. The parameter ψ controls the degree of overdispersion where such that .

The resulting method is referred to as HWT count data method, and it improves the accuracy of the HW method [7]. The HWT count data method also outperforms other smoothing methods which do not account for overdispersion [7].

4. Methodology

In this section, we show how we apply the HWT count data method to the data used in this research. We also present and discuss the results of the forecasting.

A. Data

1) Data set: The data consists of traffic flows of 13 sig- nalized arterial road segments in Taipei city. Fig. 2 shows the traffic flow direction and the road segments. Microwave Radar Vehicle Detectors were used to record the data for 19 days from January 21, 2008 at 00:00 to February 8, 2008 at 11:58 including four weekend days. The collection of dense data with short distance between two measuring sites, 200m to 400m, and short time interval between two successive observations, two minutes, is necessary to capture all flow patterns and variations.

Initially, the data were inspected and invalid records were found including missing flow values, negative flow values and zero flow values when speed is greater than zero. The invalid data resulted from detector malfunction or failure. The number of the invalid records of each road is less than 20 records per day which is not large and does not affect the accuracy of the modeling. To replace an invalid data record, we used an interpolation function that calculates the average of the preceding value and the following value of that record.

2) data characteristics: The traffic flow of a selected road, e.g. R8, is represented by a time series that is plotted in Fig. 3 for 19 days and in Fig. ?? for a single day. Fig. 3 illustrates that the traffic flow has a weekly pattern which shows that the flow in workdays is different than the flow in weekends. Further, Fig. 3 illustrates that the traffic flow has daily seasonal patterns which includes intraday seasonal patterns, Fig. 4. The Intraday seasons are categorized into: a low-traffic season when the flow is less than the mean and often exists in the early morning from 00:00 to 6:00, a high-traffic season when the flow is greater than the mean and occupies time periods from 7:00 to 9:00 and 17:00 to 19:00, and an average traffic seas1on when the flow is around the mean. The flow in all roads follows the same patterns.

Figure 2. Map of selected roads in Taipei city

Figure 3. The daily patterns of the traffic flow on R8 for 19 days

Figure 4. The intraday seasonal patterns of the traffic flow on R8

Additionally, the traffic flow has overdispersion since the variance of the flow for each road is greater than the mean as shown in Table 1. The flow overdispersion is tested using the dispersion value (the Pearson statistic (χ²) divided by the degrees of freedom (df)), and data is overdispersed when the quotient is greater than one [10]. We find that all flows are overdispersed since the quotients for all roads are greater than one. The flow overdispersion is related to the flow variations within seasonal patterns and to flow fluctuation due to traffic lights. The green light phase decreases flow and the red light phase increases it, and the fluctuation is significant during rush hours, which agrees with the results in [16]. The variations may be also caused by other effects such as changing weather conditions, road work, and driving behavior.

Table 1. The mean, variance, overdispersion values of flows on selected roads

B. Modelling Process

The traffic flow contains weekly and daily seasons. Since the adopted method can model two seasons, we let D_t index represent the weekly season and W_t index represent the daily season. The data were recorded every two minutes, so the number of daily periods, m₁, is 720, and the number of weekly periods, m₂, is 5040.

The application of the adopted method includes training the models to estimate all required coefficients and then using the trained models for forecasting. We used 15-day data to train the models and four-day data to evaluate the forecast. The training process involves initializing the level and the trend indices as in [13], where the initial value of level L₀, which the overall mean, is given by

(8)

and the initial value of trend, T₀, is given by

(9)

The index of the large season (weekly season) is initialized by the ration of the observed data to the mean as

(10)

and the index of the small season (daily season) is initialized as

(11)

where A₀ is the daily mean of y [7].

The training process also involves estimating the smoothing and the overdispersion coefficients which can be estimated using the likelihood function, equation 7. The lower and upper boundaries of all coefficients were set to zero and one, respectively. A total of 10800 data records, lower and upper boundaries and initial values were used in a quasi- Newton algorithm to optimize the coefficients. The estimated coefficients are presented in Table 2. After the model was trained, we used it to forecast future values as in equation 6.

Table 2. The smoothing coefficients estimated by the standard HW and the HWT-count data methods

We compared the HWT count data method with the HW method since it also accounts for temporal autocorrelation and seasonal patterns and with the space-time Negative Binomial regression since it accounts for the overdispersion. The daily season only was used in the HW, and initial values were set as in the HWT but without using the W_t index, The HW smoothing coefficients were estimated by minimizing the mean square error, as in [13], instead of maximizing a likelihood function. The space-time NB regression coefficients were estimated by maximizing a log-likelihood function, derived in [10], using flows from correlated roads, as in [5]. The Root Mean Square Error (RMSE) was used to evaluate the forecast accuracy and compare the three methods. The RMSE is usually used to evaluate the forecast accuracy because it gives an idea about the forecast error. The RMSE is given by

(12)

C. Results

In this subsection, we firstly show the results of estimation of the HW, the HWT count data, and the space-time Negative Binomial regression methods. The values of the smoothing coefficients of the HW and the HWT count data methods for some selected roads are presented in Table 2, and the NB regression coefficients for R8 as a dependent road are presented in Table 3.

Table 3. The space-time NB regression coefficients when R8 is the dependent road

We do not include β in Table 2 because it is zero that means the overall trend is zero. The values of φ in Table 2 can verify that the variance is greater than the mean (σ² = µ + φµ²), and these values are different from the overdispersion values in Table 1 as they are used to model the data while the values in Table 1 are used to test the existence of the overdispersion. The high values of γ and ω show that the variation is dominated by the seasonality while the overall trend is zero. The coefficients in the table are used to forecast future values for one cycle ahead which is one day.

The space-time Negative Binomial regression method assists in identifying the significant variables that affect the forecast results. In traffic context, several upstream and downstream roads exist, and it is important to identify which road is significant. A variable is considered significant if its P-value is smaller than the significance level and the significance increases when the P-value decreases. The spatial and temporal variables with significant coefficients are presented in Table 3, and the insignificant coefficients are represented by (-). It is shown that for a dependent road, R8, the significant spatially correlated variables (predictors) are R4, R5, R6, and R7. Also, the significant temporally correlated variables are t − 1, t − 2, and t − 3 only which indicates that the NB regression can capture limited temporal autocorrelation. The significant variables are the only ones used as predictors in a multistep forecast as in equation 1.

Secondly, we discuss the forecast results of each method. The forecast results show that the three methods can forecast for different horizons: one day for the HWT method and the HW method and 20 minutes for the space-time NB regression. As we are interested in short-term prediction only, which is less than 20 minutes ahead, because of the continuous changes in traffic, we compare the models for 20 minutes horizons. So, our goal is identifying which forecasting method is more accurate for 20 minutes ahead. We include comparison results during different traffic conditions: low, average and high traffics. The RMSE values resulting from the tests are averaged and presented in Table 4.

Table 4. Comparison between the forecast methods for different roads in different traffic seasons

The HWT count data method reduces the residual error significantly during all traffic seasons and consequently it has the lowest RMSE values for 20-minute forecasts. The HWT count data method handles the overdispersion and can capture different seasonal patterns, so it outperforms the space- time NB regression because the latter does not account for autocorrelations and seasonal patterns. It is also better than the HW because the HW does not account for the overdispersion.

To illustrate how the methods behave in different forecast horizons, we plot the RMSE values of the methods against different prediction horizons during the low, average and high traffic seasons for R8, Fig. 5. We notice that the accuracy of all methods decreases when the horizon increases. The HWT count data method has the lowest RMSE during all traffic seasons and for all time horizons. The slope of the HWT count data method curve is also the lowest which means that the RMSE increase little over time. We decided a RMSE value of four as a threshold value where smaller RMSE values can be acceptable. The accuracy of the HWT count data method starts to deteriorate (RMSE > 4) after a 36-minute horizon during the low and average traffic seasons and after 24-minute horizon during the high traffic season. Meanwhile, the other methods behave similarly but they have larger RMSE values and start to deteriorate earlier than the HWT count data method. Clearly, the HWT count data method is the most accurate one.

Figure 5. RMSE against different forecast horizons during the three traffic seasons

5. Conclusions

The success of DRG requires accurate short-term prediction with low computational demand [17]. Accurate short-term prediction models enables DRG to provide adaptive services in real-time. Travellers will be able to select the best route pre-trip or on-trip based on current and future traffic conditions. Therefore, this paper has proposed a method for short-term traffic flow prediction in urban areas where flows are autocorrelated and overdispersed. The method addresses the most important characteristics of traffic flow including autocorrelation, trend, seasonality and overdispersion by adopting the HWT count data method. The proposed method can capture the weekly season and the daily season simultaneously. The comparison between the proposed method with the HW and the space-time NB regression methods states that the proposed method outperforms the others. This paper also has presented an ATIS that incorporates the proposed prediction model into its architecture.

The limitation of the proposed method is that it only models the weekly season and the daily season. Future work will investigate the possibility of using multiple seasonal methods to model all of the intraday seasons simultaneously. Further, the proposed method needs to account for not only one road segments, but also other correlated segments. This can be achieved by deriving a multivariate HW method that can handle overdispersion and capture trends and seasonal patterns of multiple flows on different correlated roads.