Short-term speed predictions exploiting big data on large urban road networks

Highlights

• A consistent method for short-term speed predictions by using raw floating car data on large networks is presented.

• A Bayesian network and a neural network are compared with a seasonal ARMA model.

• A double star model reflecting time-space correlation allows for modular implementation.

• The variable accuracy of speed measures from floating car data is taken into account.

• A supervisor framework is envisaged to integrate different models.

Abstract

Big data from floating cars supply a frequent, ubiquitous sampling of traffic conditions on the road network and provide great opportunities for enhanced short-term traffic predictions based on real-time information on the whole network. Two network-based machine learning models, a Bayesian network and a neural network, are formulated with a double star framework that reflects time and space correlation among traffic variables and because of its modular structure is suitable for an automatic implementation on large road networks. Among different mono-dimensional time-series models, a seasonal autoregressive moving average model (SARMA) is selected for comparison. The time-series model is also used in a hybrid modeling framework to provide the Bayesian network with an a priori estimation of the predicted speed, which is then corrected exploiting the information collected on other links. A large floating car data set on a sub-area of the road network of Rome is used for validation. To account for the variable accuracy of the speed estimated from floating car data, a new error indicator is introduced that relates accuracy of prediction to accuracy of measure. Validation results highlighted that the spatial architecture of the Bayesian network is advantageous in standard conditions, where a priori knowledge is more significant, while mono-dimensional time series revealed to be more valuable in the few cases of non-recurrent congestion conditions observed in the data set. The results obtained suggested introducing a supervisor framework that selects the most suitable prediction depending on the detected traffic regimes.

Introduction

Fast and accurate predictions of future traffic conditions are a crucial requirement for reliable applications of Intelligent Transportation Systems (ITS) devoted to traffic management and traveler information, whose intelligence is related to their capability to foresee future states of the system and individuate the most appropriate actions to undertake. Advances in Information and Communication Technologies (ICT) are currently making available an unprecedented amount of measures of traffic variables from the road network that are a premise for introducing new models and methods for traffic predictions (Shi and Abdel-Aty, 2015). Traditional traffic monitoring systems are based on fixed measure stations where flows, occupancy and possibly speed are detected. Collected data are then transmitted to the traffic control center, where they are processed to derive short-term predictions. The relatively high cost of investment and maintenance of fixed monitoring system was one of the most relevant limiting factors for a full ITS deployment although efficient algorithms for optimizing sensor locations were developed (Cipriani et al., 2006).

Availability of Floating Car Data (FCD) obtained by tracking GPS-enabled vehicles and mobile devices opens new perspectives to develop novel predicting models. In fact, they provide a pervasive tool to explore the road network and get information related to theoretically any point of the network (Fusco et al., 2015) and, in a near future, perform self-organizing monitoring techniques (Baiocchi et al., 2015). The existence of very detailed road graphs developed for on-board navigators would require equally detailed estimations of present and future traffic conditions. However, a suitable trade-off between reliability and accuracy of traffic estimates and predictions should be investigated. The main drawback of FCD is that the information is collected from only a sample of vehicles that send their current positions and speeds. Thus, they provide ubiquitous but partial information. This requires a supplementary effort to process these data and combine measures collected at different points and different instants. Moreover, while the sampling rule is usually specified, the actual sampling rate on each road link is unknown, so that the reliability of the measures is variable and difficult to estimate, except for the few links equipped with fixed traffic counting stations. Furthermore, in links not traveled by equipped vehicles data are missed at all. In the last years, several private companies have started collecting and selling real-time speed data from different sources, including floating car data. Aggregate measures supplied by private providers are usually paired with some qualitative confidence value and so preclude performing a rigorous estimation of the statistical significance of the data. Although the accuracy appeared to be improved since the earliest independent evaluation (Kim and Coifman, 2014), the reliability of traffic measures is still a crucial issue for studies dealing with short-term prediction methods that use floating car data. The huge amount of data collected in real-time on the road network requires also efficient analysis methods to catch the most useful information embedded in such time–space big data.

A large interest for machine learning methods arose in the last years in the literature on big data analysis and many network-based approaches, such as neural networks and Bayesian networks, were proposed with the aim of exploiting existing correlations among measures collected at different time intervals and on different links of the network. Specifically, Bayesian networks, which combine graph structure and Bayes approach to posterior probability from a priori estimate seem to offer a sound methodology for formulating short-term predictions from the pervasive sampling of traffic performances provided by floating car data.

In this paper, we aim at investigating the potentials of these methods to produce accurate short-term traffic predictions by exploiting floating car data collected ubiquitously on the network from a number of probe vehicles that is indeed large in absolute but is a relatively small fraction of the traffic flow on each link of the road network.

Two main approaches can be individuated to perform short-term traffic predictions: either explicit or implicit traffic modeling. Explicit approach is based on mathematical models that represent the interactions between the physical variables that describe traffic phenomena. Traffic on freeways is usually modeled by macroscopic continuous models that discretize in time and space the partial differential equations that describe traffic dynamics. Traffic on urban road networks needs dynamic traffic assignment models that simulate the complex dynamic interactions between drivers’ trip choices, vehicular congestion and road performances on the traffic networks.

Application of traffic models for real-time short-term predictions requires recursive methods implementable online. The rolling horizon method exploits current traffic measures to update trip demand estimation at every given short time interval and runs a new traffic simulation, which covers a longer time interval and holds until a new update is available. Relevant examples are the Dynasmart-X (Mahmassani et al., 2005) and Dynamit (Ben-Akiva et al., 2012). State-space models formulate the dynamic evolution of all traffic variables on the road network based on available real-time traffic measurements under a probabilistic environment (Muñoz et al., 2003). Typical applications for short-term real-time predictions imply the linear approximation of non-linear macroscopic traffic models that leads to the extended Kalman filter formulation (Stathopoulos and Karlaftis, 2003, Wang and Papageorgiou, 2005), although other approximation methods such as particle filter (Mihaylova et al., 2007) and Newtonian relaxation (Herrera and Bayen, 2010) were developed. The switching-mode model, which can be thought of as a combination of the hidden Markov model and the linear state-space model (Sun et al., 2003), was introduced to reproduce the possible transitions from a discrete traffic state to another, namely free-flow and congestion states that characterize the cell transmission model (Daganzo, 1994). A more complex architecture implements artificial neural networks to derive density values and determine transitions between traffic states on the linearized triangular fundamental diagram (Celikoglu, 2014).

Implicit approach derives dynamic relationships directly from time series of observed data and therefore is usually called data-driven approach. Although we acknowledge that explicit models have superior interpretation capabilities with respect to implicit models and can be applied to generate control and information strategies that prevent system over-reaction (Ben-Akiva, 1985), we recognize also that they require a huge effort to achieve an adequately accurate calibration of a large urban network. On the other hand, the enormous amount of available data on urban mobility makes implicit models a valuable alternative, easier to implement and open to possible integrations with explicit models within a hybrid rolling horizon framework that applies an explicit model to forecast traffic states over a time horizon of a few hours and an implicit model that adjusts prior model forecasts on the basis of real-time measures and supplies posterior short-term predictions. Thus, in this paper we focus on studying suitable structures of data-driven models to exploit time-space information embedded in floating car big data and testing the accuracy of the short-term predictions so obtained.

Data driven methods for short term traffic forecasting are object of a huge literature, which has been the object of a recent special issue on this journal (Zhang, 2014). We refer to the papers by Vlahogianni et al., 2014, Oh et al., 2015 for a complete review of the state-of-the art and we focus here on the following issues: (i) the relevance of capturing the time-space correlation for short-term traffic forecasting in urban road networks through implicit models; (ii) the opportunities and concerns that arise from variable point traffic measures collected by sparsely sampled vehicles on the whole road network; and (iii) the generalization capability of probabilistic graphical models with respect to different congestion patterns.

Although the majority of previous studies conducted independent forecasting for each single monitored section of the road (Cai et al., 2016), several attempts were made in the past to catch spatial correlation between traffic variables on the road network by extending time-series models to multivariate form (Kamarianakis and Prastacos, 2005, Chandra and Al-Deek, 2009, Guo et al., 2014, Mai et al., 2015, Li et al., 2015a), through implicit prediction models that include a network structure, such as artificial neural networks (Fusco and Gori, 1996, Dougherty and Cobbett, 1997, Zhang, 2000, Zhu et al., 2014, Ma et al., 2015a, Ma et al., 2015b), Bayesian networks (Sun et al., 2006, Castillo et al., 2008, Hofleitner et al., 2012, Chen et al., 2015), deep architecture models (Lv et al., 2015). Several authors devised hybrid methods that combine different techniques and use multiple predictors (among others: Zhang, 2003, Zheng et al., 2006, van Hinsbergen et al., 2009, Wang et al., 2014). Chen et al. (2012) performed a systematic comparison of different methods for the short-term prediction on a single loop sensor and found that Bayesian networks and artificial neural networks be effective and efficient prediction models, although traffic breakdowns can be identified but cannot be accurately predicted. Other authors focused on the spatial-temporal correlation among traffic measures to face the complementary problem of estimating missed data, and applied either a tensor-based method (Tan et al., 2013) or a kernel probabilistic principle component analysis (Li et al., 2013). Recently, Lv et al. (2015) pointed out that traffic prediction models are still unsatisfying for many real-world applications and rethought the traffic flow prediction problem based on with big traffic data.

With reference to the second issue mentioned above, an increased interest in the opportunity of using FCD for traffic predictions arose in last years. First studies were based on data collected by special fleets like taxis (Cfr. Castro-Neto et al. (2009) for a review) or vehicles equipped with GPS specifically for the traffic experiment (Herrera et al., 2010, Bucknell and Herrera, 2014). Other studies on short-term traffic predictions from FCD used synthetic data to estimate the suitable penetration rate of vehicles to get accurate predictions (Deng et al., 2013). Feng et al. (2014) analyzed vehicle trajectories tracked in NGSIM experiment and developed a Bayesian method to estimate the probability distribution of travel times among different vehicles by taking into account synthetic GPS data and signal setting parameters to identify prevailing actual traffic conditions in real-time. Ye et al. (2012) studied a method to accommodate data recorded at irregular intervals, which exploits information from adjacent links. Among the studies based on-the-field data, Kim and Coifman (2014) analyzed aggregated information provided by INRIX company against loop detector measurements on 44 links and highlighted that they do not appear to reflect the latency with respect to reference measures or the occurrence of repeated reported speeds. Schneider et al. (2010) compared the effectiveness and accuracy of floating car studies with that achievable by Bluetooth technology. Patire et al. (2015) discussed the opportunities and challenges related to the use of non-aggregated point-speed GPS data and developed a data fusion method to exploit raw probe data in addition to fixed sensor counts.

As far as the generalization capability of prediction models to provide accurate predictions under different congestion patterns, almost all studies, with the exception of Guo et al. (2014), applied the short-term prediction models to a selected set of data covering a suitable time interval and assess their performances on the whole period, without inspecting the reliability of predictions in the case of heavy congestion. Many authors looked at the problem from a different perspective and tried to improve the traffic prediction by adapting the model framework to different traffic states. Two main approaches can be individuated: a clustering approach, which classifies traffic states either on the basis of the observed time-series pattern (Cai et al., 2016) or over the fundamental diagram (Celikoglu and Silgu, 2016, Antoniou et al., 2013), and a regime switching approach, again based on either time-series pattern (Cetin and Comert, 2006, Kamarianakis et al., 2012) or on the fit to the fundamental diagram (Dunne and Ghosh, 2012). Charle et al. (2010) addressed a rather different problem, which was route travel time reliability, and analyzed the historical space correlations between travel times of close links. Their perspective highlights the significance of long-term effects to individuate recurrent congestion conditions, which the short-term variation superimposes to. A reliable historical estimate is significant especially when dealing with FCD, whose sampling rate in real-time is often low other than unknown, so reducing the reliability of predictions founded on short-term series only. So far, few studies were based on large real data sets of FCD, as it would be necessary to face the question concerning the reliability of traffic forecasting methods based on FCD with respect to the reliability of the measures. Hofleitner et al. (2012) used individual FCD collected by 500 cars in a specific experiment; Cai et al. (2016) used a data set of space mean speed data collected on 30 road segments for 20 weekdays. Data were suitably preprocessed to fill missed data and eliminate abnormal values and filtered to get smoothed data. In a very recent paper (Fusco et al., 2016), we compared different network-based short-term forecasting models on a 10-month long series of aggregated measures obtained from FCD and we proposed a model structure conceived to perform forecasts on large networks exploiting speed estimates on all the links where they are available.

The paper aims at providing a consistent method for short-term speed predictions on large networks based on raw floating car data and presents a modeling framework that implements some well-known network-structured prediction models. The paper also focuses on the issues that the analysis of the literature revealed to be worthy of further examination: the reliability of traffic measures collected at random points of the road network; the suitability of different prediction models with respect to different traffic conditions, such as free-flow, recurrent and non-recurrent congestion. The approach that we aim at following is that the nature of traffic congestion implicates that the computational methodologies of artificial intelligence must be transportation-inspired.

We introduce different architectures of machine learning models based on different levels of exploration of the road network in order to catch possible spatial correlations among traffic measures taken on different links of the network. In contrast to our previous study (Fusco et al., 2016), where we used the historical average speed as an a priori estimation, we are here closer to the Bayesian approach and we try to provide an as good as possible a priori estimation based on previous observations. Thus, we formulate a hybrid modeling framework where we integrate the best a priori estimation based on time correlation, which is provided by a consolidated Seasonal ARIMA model, with the spatial correlation estimated through a Bayesian network. Unlike our previous paper as well as other works in the literature, with the exception of Patire et al. (2015), we deal with issues and advantages of using raw data of individual cars. While Patire et al. focus on the question of sampling and penetration rates and present a data fusion framework to integrate floating car data and fixed point measurements, we introduce here a consistent method designed to use disaggregated raw data. We specify the model variables to exploit all the available information about traffic estimation. Specifically, variances between individual speeds and the number of measures in each time interval on each link are considered to account for the time-variable accuracy of the measures. However, no flow measure is assumed because the number of counts available is very often insufficient to get an accurate estimation in a reasonable time interval. We also enhance the validation method by introducing specific error indicators that relate the accuracy of different prediction models with the accuracy of the measures.

Unlike most studies in the literature, we assess the performances of the models under different traffic congestion conditions. Fig. 1 provides a flow-chart of the problems arising from sparse floating car data, the specific procedures implemented to face with each of them and the corresponding solutions that compose our method. It highlights also the main advantages that this method offers with respect to the state-of-the-art: the variable selection focuses on a fundamental issue of sparse floating car data, that is their variable sampling rate, and allows considering the accuracy of observed data in both model structure and prediction results; the double-star network structure of the forecasting models allows an easy modular implementation of the procedure even on very large networks as well as a parallel computation that preserves anyway the possible spatial correlation among the links; hybrid model formulation with a priori autoregressive predictions allows an easy extension of the model to integrate a supervisor mechanism that selects the best forecasting model based on estimated traffic conditions.

In contrast with other papers in the literature that aim at adapting the model framework to different traffic states, such supervisor exploits only individual point speed observations, so it does not require flow measure. Moreover, it does not seek to estimate traffic states but to individuate the occurrence of anomalous conditions and then it relaxes relationships based on recurrent observations. Finally, while only limited tests have been presented until now in the literature on traffic predictions using GPS-equipped Floating Car Data, we present a large numerical experiment conducted on a big data set composed of about 300,000 single point-speed data collected on a wide portion of an urban street network (120 links) selected on a sub-network of a large town, Rome.

The rest of the paper is organized as follows. Section 2 presents the methodology proposed for short-term forecasting, describes the state-of-art methods selected for reference and introduces the error indicators chosen for the comparison between different methods. Section 3 illustrates the experimental application on a suitable subarea of the road network of Rome, where the data set was available. Results of different prediction methods under different traffic conditions are illustrated and commented. Conclusions and suggestions for further research are reported in Section 4.