Citywide Spatial-Temporal Travel Time Estimation Using Big and Sparse Trajectories

Urban travel time estimation is a strategically important task for many levels of traffic management and operation. Although a number of technologies regarding data and model have been developed recently, it has not been well solved yet given the following challenges: effective modeling approach, data sparsity, and traffic condition fluctuation. In this paper, a tensor-based spatial-temporal model is proposed for citywide travel time estimation, using the big and sparse GPS trajectories received from taxicabs. The travel time of different road segments under different traffic conditions in some time slots is modeled with a third-order tensor. Meanwhile, the occurrence probability of different traffic conditions on different road segments in these time slots are modeled with another third-order tensor. Combined with historical knowledge learned from trajectories, missing entries in the two tensors can be estimated by a context-aware tensor factorization approach. Based on the reconstruction results, for any road segment of the urban road network in the current time slot, we can know not only the travel times under different traffic conditions but also the occurrence probabilities of corresponding traffic conditions. The model incorporates both the spatial correlation between different road segments and the deviation between different traffic conditions, as well as the coarse-grain temporal correlation between recent and historical traffic conditions and the fine-grain temporal correlation between different time slots. The model is applied to a case study for the citywide road network of Beijing, China. Empirical results of extensive experiments, based on the GPS trajectories derived from over 32670 taxicabs for a period of two months, demonstrate that the model outperforms the competing methods in terms of both effectiveness and robustness.