Journal of Industrial Engineering and Management

Intelligent transportation system real time traffic speed prediction with minimal data

 

Luana Georgescu¹, David Zeitler², Charles Robert Standridge²

¹Dematic North America, ²Grand Valley State University (USA)

 

Received: September 2012

Accepted: November 2012

 

 

Georgescu, L., Zeitler, D., & Standirdge, C.R. (2012). Intelligent transportation system real time traffic speed prediction with minimal data. Journal of Industrial Engineering and Management, 5(2), 431-441. http://dx.doi.org/10.3926/jiem.542

 

---------------------

 

Abstract:

Purpose: An Intelligent Transportation System (ITS) must be able to predict traffic speed for short time intervals into the future along the branches between the many nodes in a traffic network in near real time using as few observed and stored speed values as possible. Such predictions support timely ITS reactions to changing traffic conditions such as accidents or volume-induced slowdowns and include re-routing advice and time-to-destination estimations.

Design/methodology/approach: Traffic sensors are embedded in the interstate highway system in Detroit, Michigan, USA, and metropolitan area. The set of sensors used in this project is along interstate highway 75 (I-75) southbound from the intersection with interstate highway 696 (I-696). Data from the sensors including speed, volume, and percent of sensor occupancy, were supplied in one minute intervals by the Michigan Intelligent Transportation Systems Center (MITSC). Hierarchical linear regression was used to develop a speed prediction model that requires only the current and one previous speed value to predict speed up to 30 minutes in the future. The model was validated by comparison to collected data with the mean relative error and the median error as the primary metrics.

Findings and Originality/value: The model was a better predicator of speed than the minute by minute averages alone. The relative error between the observed and predicted values was found to range from 5.9% for 1 minute into the future predictions to 10.9% for 30 minutes into the future predictions for the 2006 data set. The corresponding median errors were 4.0% to 5.4%. Thus, the predictive capability of the model was deemed sufficient for application.

Research limitations/implications: The model has not yet been embedded in an ITS, so a final test of its effectiveness has not been accomplished.

Social implications: Travel delays due to traffic incidents, volume induced congestion or other reasons are annoying to vehicle occupants as well as costly in term of fuel waste and unneeded emissions among other items. One goal of an ITS is to improve the social impact of transportation by reducing such negative consequences. Traffic speed prediction is one factor in enabling an ITS to accomplish such goals.

Originality/value: Numerous data intensive and very sophisticated approaches have been used to develop traffic flow models. As such, these models aren’t designed or well suited for embedding in an ITS for near real-time computations. Such an application requires a model capable of quickly forecasting traffic speed for numerous branches of a traffic network using only a few data points captured and stored in real time per branch. The model developed and validated in this study meets these requirements.

Keywords: Traffic speed prediction, Intelligent transportation systems, Hierarchical regression

---------------------

 

1. Introduction

As investment in construction and expansion decreases, making better use of urban traffic infrastructure is necessary. Intelligent Transportation Systems (ITS), an assembly of advanced components that collect, store, process and transmit traffic information for assisting traffic management, has emerged as one way of dealing with this change in approach. An Advanced Traffic Information System (ATIS) is a core component of ITS which relies on modern technology (e.g., wireless communication) to disseminate real-time traffic information to drivers. Several ATIS systems have been developed, such as Visteon's Navmate System (Visteon, 2000), to provide road users with updated information and guide them in selecting the shortest or fastest routes.

Historical and real-time information are collected and applied in meeting vehicle routing objectives. Historical information presents the state of the transportation system during previous time periods. Such information can be used for long-term traffic volume prediction needed for transportation infrastructure planning. Real-time information contains the most up-to-date traffic conditions suitable as the basis for short term predictions ranging from a few minutes to a couple of hours in support of operational traffic management. In the absence of this predictive information, drivers are implicitly projecting future conditions based on historical (if they experienced it before) and current traffic information. Therefore, short-term predictions of traffic conditions are needed for traffic management and travelers information systems.

Thus, developing an understanding of the movement of traffic in time and space is essential for implementing ITS capabilities to relieve or avoid congestion resulting from high traffic volume, a traffic incident, or other causes. Traffic flow models capable of short-term predictions, up to 30 minutes, of traffic speed are required to address this issue. These models must be able to compute results in near-real time for each of the numerous branches in a traffic network. Data to support the models must be collected in near-real time and stored. These requirements imply the use of models requiring little data, from which results can be quickly computed and that are effective in predicting traffic speed up to 30 minutes in the future.

Towards this end, data from sensors built into various freeways in Detroit, Michigan and the surrounding metropolitan area was obtained from the Michigan Intelligent Transportation Systems Center (MITSC) to support traffic flow model building. The most complete data came from a set of sensors on the south bound interstate highway 75 (I-75) corridor from the interstate highway 96 (I-96) interchange into the city of Detroit. Work focused on a single year of weekday data (November 1, 2005-November 1, 2006) from sensor number 66305 (south bound I-75 south of Clay Street) located on the south end of the corridor. Multi-level linear regression modeling was used to develop equations predicting freeway speed for time ranges from one to thirty minutes into the future. Only the current speed and the speed at one time preceding were required, equivalent to the use of speed and current acceleration alone. Based on the use of the mean relative error and the median error as the primary validation metrics, this approach was found to be effective.

2. Background

Numerous data intensive and/or very sophisticated approaches have been used to develop traffic flow models, for example by Min, Wynter and Amemiya (2007). Zhu and Yang (2011) present a visco-elastic model based on mass and momentum conservation in which the elastic effect provides for a higher-order model. Romero and Benitez (2010) point out the voluminous nature of the data needed to model urban traffic networks and the data management challenges presented by this data and model results. They propose the use of continuous equation models to address such difficulties.

Several different methods have been used to predict and to help mitigate traffic congestion. One prediction method is based on the Kalman filter algorithm and was first applied by Okutani and Stephanedes (1984) to predict traffic volumes in an urban network. The Kalman filter uses adaptive parameters sensitive to dynamic conditions. The main advantage of this method is that it can update the adaptive parameter to make the predictor reflect the traffic fluctuation promptly.

Innamaa (2001) studied the influence of various factors on the results of the short-time prediction of traffic situation on highways. He used prediction models as feed forward multilayer perceptron (MLP) neural networks. The proposed model predicted correct travel times over 80 percent of the time in congested conditions. The results improved if the arcs between the nodes in the traffic network were divided into sub-arc with additional detectors. Forecasts were better for long links with sub-links than for short links.

Nagatani (1993) used a cellular automaton model to study traffic jams induced by an incident which separated traffic flow from traffic stoppages. Computer simulation was used to analyze the model. Arnaout and Bowling (2011) studied the use of vehicle-based adaptive cruise control to avoid traffic jams on a highway using computer simulation.

The issue of routing individual vehicles has been well studied and can be formulated as a short path problem with solution using efficient labeling algorithms (Gallo & Pallottino, 1988; Dijkstra, 1959; Moore, 1959). The labeling algorithm has been improved to solve the shortest path problem with time-dependent link travel times assuming first-in-first-out (FIFO) vehicle movement (Chabini, 1997).

The assumption of the basic model for searching the optimal path is that the link travel times are constant (e.g., deterministic and time-independent). Real-time traffic routing has emerged as a promising approach for ATIS with the latest progress in information technology and telecommunication. For these systems, as soon as traffic conditions change, a reliable routing plan can be generated with the consideration of predicted travel time information rather than purely current condition.

The studies discussed above all used sophisticated, computationally intensive methods that may not be consistent with needs of an ITS to make near-real time speed forecasts using little data. One way of doing this is discussed in the next section.

3. Model Building and Validation

Model building involved three types of models:

• A descriptive model in the form of graphs to identify sources of variation in traffic speed. Data from November of 2005 through October 2006 were used to build these models.
• An explanatory multi-level model developed using regression techniques. Data from calendar year 2006 was used to build this model.
• A predictive model for traffic speed developed by validating the explanatory model for this purpose. Data from both calendar years 2006 and 2007 were used.

Descriptive Models

A graph of speed for each day of the 12-month period November 2005 through October 2006 was created. The graphs were examined for traffic speed patterns.

The graphs of speed versus time of day for November 12 through 15, 2005 (Saturday through Tuesday) are shown in Figure 1. The graphs for Saturday and Sunday show near constant speeds around the 70mph speed limit throughout the day. The graphs for Monday and Tuesday show significant speed reductions during the morning rush hour period but otherwise near constant speed around the speed limit. The same was found to be true for Wednesday through Friday, except for holidays for which the observed speed was like a Saturday or a Sunday. This pattern repeated throughout the year with no variation by time of year observed. Thus only the non-holiday, weekday (Monday through Friday) data was further considered.

Explanatory Models

Data from calendar year 2006 was used to estimate the parameters of a multi-level explanatory model (MTM) built as follows.

• The average speed for each minute of the day was computed across the weekdays of the year. These one-minute averages were subtracted from the original data to remove time of day effects seen in Figure 1.
• The resulting residuals (actual value minus one-minute average) of the speeds were analyzed further using the mathematical form shown in Equation 1.

November 12

November 13

November 14

November 15

Figure 1. Speed Graphs for November 12-15, 2005

where

          n is the prediction horizon (0, 30] minutes, n a real positive number. 

S_t+n is the future speed at time t+n

is the average speed calculated at t+n

r_s is the residual of the speed with respect tocalculated at the current time t

r_s(t-1) is the residual of the speed calculated at the past time t-1

_b0n, b_1n and b_2n are regression coefficients

Thus, the prediction of the future speed at a time n units in the future is the historical average speed at that time of day, 1^st level of the MTM, plus a function of the residuals of the current speed and the speed one time unit in the past, the 2^nd level of the MTM. In other words, the second level of the MTM is a function of the current speed and acceleration over the last time unit.

Equation 1 is derived as follows. A more direct use of the available data could be accomplished by using equation 2.

S_t is the current speed at time t.

Equation 3 results from the definition of the residuals:

where r_s(t-1) is the residual of the speed calculated at time t+n.  

Combining equations 2 and 3 as well as expressing the result in a form that is useful for regression modeling yields equation 4:

for any n in (0, 30] minutes, n a real positive number.

where r_s(t) is the residual of the speed calculated at the current time t.

 
r_St-1 is the residual of the speed calculated at the past time t-1.        

Next, the values of the coefficients b₀, b_1n and b_2n must be estimated. The coefficient b₀ is the average of the residuals which by the definition of residuals is zero.

Coefficients b_1n and b_2n were estimated as follows. Twelve values of the prediction horizon n were considered: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 15, and 30 minutes. For each value of n, b_1n and b_2n were estimated using standard linear regression techniques. For each coefficient b_1n and b_2n, a second-degree polynomial was fit to all twelve points, equations 5 and 6. The correlation coefficients were very good: 0.9545 for b_1n and 0.9736 for b_2n.

Equations 5 and 6 support any prediction horizon for any real positive time up to 30 minutes in the future. Making a prediction requires only the residuals of the speed at current time (at time t) and at the past time (at time t-1) as well as the average speed at time t+n.

The model for sensor 66305 is given by equation 7:

Predictive Models

The model given in equation 7 can be used for speed prediction at the sensor 66305 upon validation that the predicted speeds match the actual speeds well. This was addressed in several ways.

Ideally, a simple linear regression between the predicted speeds and the actual speeds should produce a fit with a zero intercept and a slope of exactly 1.0. The closer the regression results to this ideal the more valid the prediction model. Figure 2 shows the fit results using JMP software giving an intercept off by only 1/2 MPH (0.8 km/h) and a slope of almost exactly 1.0.

The relative errors between the observed and predicted values, equation 8, assist in validating the model:

where e_i is the relative speed prediction error for observation i

         S_i is the actual (observed) speed for observation i

         S_ip is the predicted speed for observation i

An examination of the relative mean errors showed a strong skewness. Thus, the relative median error was calculated as well. The relative median error values are better (smaller) than relative mean error values for the same prediction horizon n. In addition, the parameters of the model were re-estimated using calendar year 2007 data and the median relative errors estimated. The relative mean errors and relative median errors are summarized in Table 1.

Figure 2. Model Validation for 1 minute at sensor 66305

Table 1. Validation Summary

For further validation, the data from 2007 was used as input for the model with parameters estimated from the 2006 data to generate a predicated speed. The predicted speed fifteen minutes in the future and actual speeds at that time were plotted and can be seen in Figure 3. The model predictions tend to slightly lag, by 15-30 minutes, the actual values when changes in speed are abrupt and large such as during morning rush hour but the median error is an acceptable 3.1%.

The largest relative median error is in Table 1 is about 10%. A 10% error in forecast speed translates into a travel time forecast error of less than one minute (about 0.85 minute) for a distance of 10 miles with travel at the speed limit of 70mph and for a distance of 5 miles with travel at 35mph. Such forecasting errors are insignificant particularly considering that sensors on an urban freeway network are much closer than 5 miles apart.

Figure 3. Hierarchical Model Predictions Compared to Actual Speed for a 15-minute Prediction Horizon at Sensor 67333 (South Bound I-75 South of Davison Expressway)

4. Summary and Conclusions

Hierarchical linear regression has been used to develop a model that meets the requirements of an ITS for travel speed prediction: small number of data values observed and stored as well as quick computation. The model requires only two data values which consider current speed and acceleration to predict travel speeds in the range (0, 30] minutes in the future. The primary validation metrics, relative mean error and relative median error, show that the model would be effective at predicting travel speeds and thus resulting travel times. Descriptive models reveal that traffic speed is homogenous for non-holiday week days throughout the year. Thus, one year worth of data concerning such days was used to support model building and validation.

References

Arnaout, G., & Bowling, S. (2011). Towards reducing traffic congestion using cooperative adaptive cruise control on a freeway with a ramp.  Journal of Industrial Engineering and Management, 4(4), 699-717. http://dx.doi.org/10.3926/jiem.344

Chabini, I. (1997). A new algorithm for shortest paths in discrete dynamic networks. Proceedings of the IFAC Symposium on Transportation Systems. Paper presented at Chania, Greece.

Dijkstra, E.W. (1959). A note on two problems in connexion with graphs, Numerische mathematik, 1, 269-271. http://dx.doi.org/10.1007/BF01386390

Gallo, G., & Pallottino, S. (1988). Shortest path algorithms, Annals of Operations Research, 13, 3-79. http://dx.doi.org/10.1007/BF02288320

Innamaa, S. (2001). Short-term prediction of highway travel time using MLP – Neural networks. Transportation Engineering - 8th World Congress on Intelligent Transportation Systems, Paper presented at Sydney, Australia.

Min W., Wynter, L., & Amemiya, Y. (2007). IBM Research Division, Tomas J. Watson Research Center, 'Road Traffic Prediction with Spatio-Temporal Correlations', IBM Research Report R24275 (W0706-018).

Moore, E.F. (1959). The shortest path through a maze. Proceedings of an International Symposium on the Theory of Switching. Paper presented at Cambridge, Massachusetts, 2-5 April, 1957), ed. Harvard University Press, Cambridge, 285-292.

Nagatani, T. (1993). Effect of traffic accident on jamming transition in traffic-flow model. Journal of Physics. A: Mathematical and General. 26: L1015. http://dx.doi.org/10.1088/0305-4470/26/19/008

 Okutani, I., & Stephanedes, Y.J. (1984). Dynamic prediction of traffic volume through Kalman filtering theory. Transportation Research, 18B(1). http://dx.doi.org/10.1016/0191-2615(84)90002-X

Romero, L.M., & Benitez, F.G. (2010). Traffic flow continuum modeling by hypersingular boundary integral equations. International Journal for Numerical Methods in Engineering, 82, 47–63. http://dx.doi.org/10.1002/nme.2754

VISTEON OFFERS PORTABLE AUTO NAV’ (2000). Global Positioning & Navigation News, 10(17), 1. Retrieved January 10, 2012, from ABI/INFORM Trade & Industry.

Zhu, Z., & Yang, C. (2011). Visco-elastic traffic flow model. Journal of Advanced Transportation. http://dx.doi.org/10.1002/atr.186