Speeding up KNN-WH for Origin–Destination Travel Time Estimation

Origin-destination (O-D) travel time estimation is among the most important problems studied in transportation. It focuses on determining accurate travel time from a specific origin point to a destination point. Given the development of new technologies such as GPS and mobile applications, this data can be easily gathered, improving the estimation of the O-D travel time and enabling prediction in almost real-time. Currently, one of the simplest and newest algorithms is the KNN − WH model, an improvement of the K-Nearest Neighbors method with Haversine distance and a correction factor. Unfortunately, the direct application of this method can take over 50 minutes to predict a new set of 70,000 data points. This paper proposes k − KNN − WH, a new two-step framework that clusters the data using k-means and then applies KNN − WH on the corresponding cluster. The empirical results show a minimal impact on the MAPE performance (1.5%) while reducing the time estimation process from approximately 50 to 20 minutes.