Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
T-Drive: Driving Directions Based on Taxi Trajectories

Jing Yuan, Yu Zheng, Chengyang Zhang, Wenlei Xie, Xing Xie, and Yan Huang

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.

Details

Publication typeInproceedings
Published inACM SIGSPATIAL GIS 2010
PublisherAssociation for Computing Machinery, Inc.

Newer versions

Yu Zheng. T-Drive trajectory data sample, 12 August 2011.

Jing Yuan, Yu Zheng, Xing Xie, and Guangzhong Sun. T-Drive: Enhancing Driving Directions with Taxi Drivers' Intelligence, IEEE Transactions on Knowledge and Data Engineering (TKDE), IEEE, January 2012.

Jing Yuan, Yu Zheng, Xing Xie, and Guangzhong Sun. Driving with Knowledge from the Physical World, Association for Computing Machinery, Inc., 24 August 2011.

Previous versions

Jing Yuan, Yu Zheng, Chengyang Zhang, Xing Xie, and Guangzhong Sun. An Interactive Voting-based Map Matching Algorithm, IEEE, 25 May 2010.

Yin Lou, Chengyang Zhang, Yu Zheng, Xing Xie, Wei Wang, and Yan Huang. Map-Matching for Low-Sampling-Rate GPS Trajectories, Association for Computing Machinery, Inc., 4 November 2009.

Yu Zheng, Jing Yuan, and Xing Xie. Drive smartly as a taxi driver, IEEE, 26 October 2010.

> Publications > T-Drive: Driving Directions Based on Taxi Trajectories