TY - GEN
T1 - Speeding up KNN-WH for Origin–Destination Travel Time Estimation
AU - Alvarez, Sofía
AU - Moreno, Sebastián
AU - Tobar-Arancibia, Alfonso
AU - Yushimito, Wilfredo
N1 - Publisher Copyright:
©2025 IEEE.
PY - 2025
Y1 - 2025
N2 - 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.
AB - 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.
KW - k-nearest neighbor
KW - machine learning
KW - origin–destination travel time
KW - speed up estimation process
UR - https://www.scopus.com/pages/publications/105032188917
U2 - 10.1109/ICPRS66293.2025.11302832
DO - 10.1109/ICPRS66293.2025.11302832
M3 - Conference contribution
AN - SCOPUS:105032188917
T3 - 2025 15th IEEE International Conference on Pattern Recognition Systems, ICPRS 2025
BT - 2025 15th IEEE International Conference on Pattern Recognition Systems, ICPRS 2025
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 15th IEEE International Conference on Pattern Recognition Systems, ICPRS 2025
Y2 - 1 December 2025 through 4 December 2025
ER -