T-drive is a smart driving direction services based on GPS trajectories of a large number of taxis. It helps user find out the practically fastest path to a destination at a given departure time.
A prototype has been built based on a real-world trajectory dataset generated by 30,000 taxis in Beijing in a period of 3 monthes.
The service is available (within Microsoft corpnet), which provides a user with the practically fastest path with less online computation and according to your departure time.
Three Challenges in T-Drive:
- Intelligence Modeling
- Data sparseness
- Low-sampling-rate of the trajectories
Motivation
First, taxi drivers are experienced drivers who can usually find out the fastest path to send passengers to a destination based on their knowledge. Second, the GPS-equipped taxis are mobile sensors probing the traffic flows on road surfaces. So, the taxi trajectories contain the information of both human knowledge of experienced drivers and traffic patterns.
Methodology
Refer to our T-Drive publication on ACM SIGSPATIAL GIS 2010, which won the best paper runner up award and was featured on the homepage MIT Technology review.
1. landmark graph building
2. Travel time estimation
3. two-stage routing.
Results
We evaluate the system with extensive experiments and in-the-field evaluations. The results show that our method signi cantly outperforms both the speed-constraint-based and the real-time-traffic-based method in the aspects of e ectiveness and efficiency. Given over 5 taxis in a region of 1km2, more than 60% of our routes are faster than that of the speed-constraint-based approach, and 50% of these routes are at least 20% faster than the latter. On average, our method can save about 16% of time for a trip, i.e., 5 minutes per 30-minutes driving.
News
- "A driving route made just for you", MIT Technology Review, 2011.8.30. (Another Chinese version).
- Adding cabbie know-how to online maps, Technology Review, news featured on the first page, 2010.11.6
- Follow that cab! Racing Google Maps on city streets, NewScientist, 2010.11.5
- Microsoft aims to improve maps with GPS data from 33,000 Beijing cab drivers, engadget, 2010.11.9
- Cabbies help Microsoft Improve Online Mapping, Wired, November 10, 2010.
Patents
- International Patent. MS 328341.01, MS1-4911US, "Route Computation Based on Route-Oriented Vehicle Trajectories", 12/28/2009
- US Patent. MS328342.01, MS1-4909US, "Map-Matching for Low-Sampling-Rate GPS Trajectories", 12/30/2009
- Jing Yuan, Yu Zheng, Xing Xie, and Guangzhong Sun, T-Drive: Enhancing Driving Directions with Taxi Drivers' Intelligence, in IEEE Transactions on Knowledge and Data Engineering (TKDE), IEEE, January 2012
- Yin Zhu, Yu Zheng, Liuhang Zhang, Darshan Santani, Xing Xie, and Qiang Yang, Inferring Taxi Status Using GPS Trajectories, no. MSR-TR-2011-144, November 2011
- Jing Yuan, Yu Zheng, Liuhang Zhang, Xing Xie, and Guangzhong Sun, Where to Find My Next Passenger?, in Ubicomp 2011, ACM, 17 September 2011
- Yu Zheng, Yanchi Liu, Jing Yuan, and Xing Xie, Urban Computing with Taxicabs, in Ubicomp 2011, ACM, 16 September 2011
- Jing Yuan, Yu Zheng, Xing Xie, and Guangzhong Sun, Driving with Knowledge from the Physical World, in SIGKDD 2011, Association for Computing Machinery, Inc., 24 August 2011
- Wei Liu, Yu Zheng, Sanjay Chawla, Jing Yuan, and Xing Xie, Discovering Spatio-Temporal Causal Interactions in Traffic Data Streams, in SIGKDD 2011, Association for Computing Machinery, Inc., 24 August 2011
- Yu Zheng, T-Drive trajectory data sample, 12 August 2011
- Jing Yuan, Yu Zheng, Chengyang Zhang, Wenlei Xie, Xing Xie, and Yan Huang, T-Drive: Driving Directions Based on Taxi Trajectories, in ACM SIGSPATIAL GIS 2010, Association for Computing Machinery, Inc., 1 November 2010
- Yu Zheng, Jing Yuan, and Xing Xie, Drive smartly as a taxi driver, in UIC 2010, IEEE, 26 October 2010
- Jing Yuan, Yu Zheng, Chengyang Zhang, Xing Xie, and Guangzhong Sun, An Interactive Voting-based Map Matching Algorithm, in MDM 2010, IEEE, 25 May 2010
