A hidden Markov model for route and destination prediction

We present a simple model and algorithm for predicting driver destinations and routes, based on the input of the latest road links visited as part of an ongoing trip. The algorithm may be used to predict any clusters previously observed in a driver's trip history. It assumes that the driver's historical trips are grouped into clusters sharing similar patterns. Given a new trip, the algorithm attempts to predict the cluster in which the trip belongs. The proposed algorithm has low temporal complexity. In addition, it does not require the transition and emission matrices of the Markov chain to be computed. Rather it relies on the frequencies of co-occurrences of road links and trip clusters. We validate the proposed algorithm against an experimental dataset. We discuss the success and convergence of the algorithm and show that our algorithm has a high prediction success rate.