PR-LTTE: Link travel time estimation based on path recovery from large-scale incomplete trip data

The widespread use of positioning devices has generated large-scale trip data, boosting the study of traffic modeling. For instance, New York City Taxi & Limousine Commission regularly releases over 165 million taxi trip records containing the end-point information of each trip every year. Such big datasets provide us potential new perspectives to tackle traditional issues in traffic modeling. In this paper, we propose to use such vehicle trip data, which do not contain information on the intermediate vehicle positions other than the end points, to study the link (road segment) travel time estimation problem. A method named PR-LTTE is developed to estimate the mean travel time for interested links in a road network based on path recovery, jointly modeling trip distance and trip travel time. The key idea is to iteratively alternate between 1) inferring the most likely path for a given trip by minimizing a loss function that considers both trip distance and trip travel time, and 2) computing the link travel time via the least-squares estimation with the inferred path. Our experiments on two large-scale trip datasets (including New York City taxi trip data and Chengdu DiDi trip data) show very promising results. PR-LTTE improves the accuracy of travel time estimation by more than 50% in most cases over state-of-the-art methods.