Urban Traffic Flow Prediction Using a Spatio-Temporal Random Effects Model

Traffic prediction is critical for the success of intelligent transportation systems (ITS). However, most spatio-temporal models suffer from high mathematical complexity and low tune-up flexibility. This article presents a novel spatio-temporal random effects (STRE) model that has a reduced computational complexity due to mathematical dimension reduction, with additional tune-up flexibility provided by a basis function capable of taking traffic patterns into account. Bellevue, WA, was selected as the model test site due to its widespread deployment of loop detectors. Data collected during the 2 weeks of July 2007 from 105 detectors in the downtown area were used in the modeling process and traffic volumes predicted for 14 detectors for the entire month of July 2008. The results show that the STRE model not only effectively predicts traffic volume but also outperforms three well-established volume prediction models, the enhanced versions of autoregressive moving average (ARMA) and spatiotemporal ARMA, and artificial neural network. Even without further model tuning, all the experimental links produced mean absolute percentage errors between 8% and 16% except for three atypical locations. Based on lessons learned, recommendations are provided for future applications and tune-up of the proposed STRE model.     

Solving the K-shortest paths problem in timetable-based public transportation systems

Finding the K-shortest paths in timetable-based public transportation systems is an important problem in practice. It has three typical variants: the K-earliest arrival problem (K-EAP), the K-shortest travel time problem (K-STTP), and the K-minimum number of transfers problem (K-MNTP). In this article we show that these problems can be solved efficiently by first modeling the timetable information with the time-expanded approach, then applying the Martins and Santos (MS) algorithm. Then we model the timetable information with the time-dependent approach and propose a modified version of the MS algorithm for solving the K-EAP. Experimental results on real-world data show that for K smaller than 100, which is enough for most applications, the execution times of the MS algorithm for the problems in the time-expanded model are less than 100 ms on a server with a 1.86-GHz central processing unit (CPU) and 4 GB of memory. For solving the K-EAP the modified MS algorithm in the time-dependent model is even more efficient (about three times faster for K ≤ 100) than the original algorithm in the time-expanded model. Our results imply the great potential of the MS algorithms in practical transportation service systems.