From destination prediction to route prediction - Krumm, John; Gruen, Robert; Delling, Daniel (Journal of Location Based Services, 2013)
A prediction of a vehicle's route would be useful for giving the driver advance warnings and alerts about upcoming situations and opportunities. This paper presents a new algorithm for predicting a driver's route based on a probabilistic prediction of the driver's destination. For each candidate destination, our route prediction algorithm plans a route to that destination. Roads on these routes accumulate the probabilities of their respective destinations, giving higher probabilities to roads along the way to higher probability destinations. The algorithm is based on a single parameter that characterises how efficiently a driver drives. Once this parameter is computed, it does not require storing a history of trips, and it works in places a driver has never visited. We test the algorithm on 100 routes recorded with the Global Positioning System (GPS) and show that the route prediction quickly narrows down the future route to a small fraction of the road network. We also compare our algorithm to two other algorithms to show how it performs better.