Travel time prediction from limited GPS floating cars

alt text 

Predicting the travel time of a path is an important task in route planning and navigation applications. As more GPS floating car data has been collected to monitor urban traffic, GPS trajectories of floating cars has been frequently used to predict path travel time. However, most trajectory-based methods rely on deploying GPS devices and collect real-time data on a large taxi fleet, which can be expensive and impractical in smaller cities. This work deals with the problem of predicting path travel time when only a small number of GPS floating cars.

We developed an algorithm that learns travel time patterns of a compact set of frequently shared paths from historical data. Given a travel time prediction query, we identify the current travel time pattern from recent trajectories, then infer its travel time in the near future. Experimental results using 10-15 taxis tracked for 6-11 months in urban area of Shenzhen, China show that our prediction has on average 5.4 minute error on trips of duration 10-75 minutes. The results improve the baseline approach of using purely historical trajectories by 2-30% on regions with various degree of path regularity.

Publication

Conference Version
Yang Li, Dimitrios Gunopulos, Cewu Lu and Leonidas Guibas, Urban Travel Time Prediction using a Small Number of GPS-Floating Cars, In Proceedings of the 25th SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2017. pdf ppt
Bibtex
@inproceedings{llgg-kbtcsgs-16,
title = "Urban Travel Time Prediction using a Small Number of GPS-Floating Cars",
author = "Yang Li, Dimitrios Gunopulos, Cewu Lu, and Leonidas Guibas",
booktitle = "Proc. 25st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.",
year = 2017,
series = {SIGSPATIAL '17},
isbn = {978-1-4503-4589-7},
location = {Los Angeles Area, California},
publisher = {ACM},
address = {New York, NY, USA}
}
Journal Version

In the extended version, we incorporate driver identity information into the pattern extraction and travel time prediction framework, allowing it to make personalized predictions based on a driver's past driving behavior. We tested the extended algorithm on a larger dataset consisting of 25 taxis collected during 2016-2017. The experiments show that personalized travel time prediction has greatly improved the scalability of our algorithm for larger, more diverse driver pools.

Yang Li, Dimitrios Gunopulos, Cewu Lu and Leonidas Guibas, Personalized Travel Time Prediction using a Small Number of Probe Vehicles, ACM Transactions on Spatial Algorithms and Systems, Special Issue on Urban Mobility: Algorithms and Systems, Volume 5 Issue 1, Artical No. 4, June 2019 pdf
Bibtex
@article{li2019personalized,
  title={Personalized Travel Time Prediction Using a Small Number of Probe Vehicles},
  author={Li, Yang and Gunopulos, Dimitrios and Lu, Cewu and Guibas, Leonidas J},
  journal={ACM Transactions on Spatial Algorithms and Systems (TSAS)},
  volume={5},
  number={1},
  pages={4},
  year={2019},
  publisher={ACM}
}

Project list