T-drive

TLDR

GPS‑equipped taxis act as mobile sensors that capture traffic flows, and drivers typically choose the quickest route based on experience. The study mines historical taxi GPS trajectories to provide users with practically fastest routes for a given departure time. We construct a time‑dependent landmark graph of frequently traversed road segments, estimate travel‑time distributions with variance‑entropy clustering, and run a two‑stage routing algorithm, evaluated on data from 33,000 taxis over three months. Our method yields faster routes in 60–70% of cases, with 50% of routes at least 20% faster than competing approaches, and 20% of routes matching the best alternatives.

Abstract

GPS-equipped taxis can be regarded as mobile sensors probing traffic flows on road surfaces, and taxi drivers are usually experienced in finding the fastest (quickest) route to a destination based on their knowledge. In this paper, we mine smart driving directions from the historical GPS trajectories of a large number of taxis, and provide a user with the practically fastest route to a given destination at a given departure time. In our approach, we propose a time-dependent landmark graph, where a node (landmark) is a road segment frequently traversed by taxis, to model the intelligence of taxi drivers and the properties of dynamic road networks. Then, a Variance-Entropy-Based Clustering approach is devised to estimate the distribution of travel time between two landmarks in different time slots. Based on this graph, we design a two-stage routing algorithm to compute the practically fastest route. We build our system based on a real-world trajectory dataset generated by over 33,000 taxis in a period of 3 months, and evaluate the system by conducting both synthetic experiments and in-the-field evaluations. As a result, 60-70% of the routes suggested by our method are faster than the competing methods, and 20% of the routes share the same results. On average, 50% of our routes are at least 20% faster than the competing approaches.