IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v12y2024i8p1255-d1379668.html
   My bibliography  Save this article

Urban Origin–Destination Travel Time Estimation Using K-Nearest-Neighbor-Based Methods

Author

Listed:
  • Felipe Lagos

    (Faculty of Engineering and Sciences, Universidad Adolfo Ibáñez, Santiago 7941169, Chile)

  • Sebastián Moreno

    (Faculty of Engineering and Sciences, Universidad Adolfo Ibáñez, Viña del Mar 2562340, Chile)

  • Wilfredo F. Yushimito

    (Faculty of Engineering and Sciences, Universidad Adolfo Ibáñez, Viña del Mar 2562340, Chile)

  • Tomás Brstilo

    (Faculty of Engineering and Sciences, Universidad Adolfo Ibáñez, Viña del Mar 2562340, Chile)

Abstract

Improving the estimation of origin–destination (O-D) travel times poses a formidable challenge due to the intricate nature of transportation dynamics. Current deep learning models often require an overwhelming amount of data, both in terms of data points and variables, thereby limiting their applicability. Furthermore, there is a scarcity of models capable of predicting travel times with basic trip information such as origin, destination, and starting time. This paper introduces novel models rooted in the k-nearest neighbor (KNN) algorithm to tackle O-D travel time estimation with limited data. These models represent innovative adaptations of weighted KNN techniques, integrating the haversine distance of neighboring trips and incorporating correction factors to mitigate prediction biases, thereby enhancing the accuracy of travel time estimations for a given trip. Moreover, our models incorporate an adaptive heuristic to partition the time of day, identifying time blocks characterized by similar travel-time observations. These time blocks facilitate a more nuanced understanding of traffic patterns, enabling more precise predictions. To validate the effectiveness of our proposed models, extensive testing was conducted utilizing a comprehensive taxi trip dataset sourced from Santiago, Chile. The results demonstrate substantial improvements over existing state-of-the-art models (e.g., MAPE between 35 to 37% compared to 49 to 60% in other methods), underscoring the efficacy of our approach. Additionally, our models unveil previously unrecognized patterns in city traffic across various time blocks, shedding light on the underlying dynamics of urban mobility.

Suggested Citation

  • Felipe Lagos & Sebastián Moreno & Wilfredo F. Yushimito & Tomás Brstilo, 2024. "Urban Origin–Destination Travel Time Estimation Using K-Nearest-Neighbor-Based Methods," Mathematics, MDPI, vol. 12(8), pages 1-18, April.
  • Handle: RePEc:gam:jmathe:v:12:y:2024:i:8:p:1255-:d:1379668
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/12/8/1255/pdf
    Download Restriction: no

    File URL: https://www.mdpi.com/2227-7390/12/8/1255/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Dimitris Bertsimas & Arthur Delarue & Patrick Jaillet & Sébastien Martin, 2019. "Travel Time Estimation in the Age of Big Data," Operations Research, INFORMS, vol. 67(2), pages 498-515, March.
    2. Zheng, Linjiang & Xia, Dong & Zhao, Xin & Tan, Longyou & Li, Hang & Chen, Li & Liu, Weining, 2018. "Spatial–temporal travel pattern mining using massive taxi trajectory data," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 501(C), pages 24-41.
    3. Shuming Sun & Juan Chen & Jian Sun, 2019. "Traffic congestion prediction based on GPS trajectory data," International Journal of Distributed Sensor Networks, , vol. 15(5), pages 15501477198, May.
    4. Xiyang Zhou & Zhaosheng Yang & Wei Zhang & Xiujuan Tian & Qichun Bing, 2016. "Urban Link Travel Time Estimation Based on Low Frequency Probe Vehicle Data," Discrete Dynamics in Nature and Society, Hindawi, vol. 2016, pages 1-13, January.
    5. Krause, Cory M. & Zhang, Lei, 2019. "Short-term travel behavior prediction with GPS, land use, and point of interest data," Transportation Research Part B: Methodological, Elsevier, vol. 123(C), pages 349-361.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Chaoyang Shi & Waner Zou & Yafei Wang & Zhewen Zhu & Tengda Chen & Yunfei Zhang & Ni Wang, 2025. "Enhancing Travel Time Prediction for Intelligent Transportation Systems: A High-Resolution Origin–Destination-Based Approach with Multi-Dimensional Features," Sustainability, MDPI, vol. 17(5), pages 1-17, February.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Yanjun Chen & Ge Zhang & Chengkun Liu & Chunjiang Lu, 2024. "Privacy-Preserving Modeling of Trajectory Data: Secure Sharing Solutions for Trajectory Data Based on Granular Computing," Mathematics, MDPI, vol. 12(23), pages 1-20, November.
    2. Chen, Enhui & Stathopoulos, Amanda & Nie, Yu (Marco), 2022. "Transfer station choice in a multimodal transit system: An empirical study," Transportation Research Part A: Policy and Practice, Elsevier, vol. 165(C), pages 337-355.
    3. Balaji Ganesh Rajagopal & Manish Kumar & Pijush Samui & Mosbeh R. Kaloop & Usama Elrawy Shahdah, 2022. "A Hybrid DNN Model for Travel Time Estimation from Spatio-Temporal Features," Sustainability, MDPI, vol. 14(21), pages 1-20, October.
    4. Dokuz, Yesim & Dokuz, Ahmet Sakir, 2023. "Time-persistent regions discovery of taxi trajectory big datasets based on regional spatio-temporal velocity," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 623(C).
    5. Tang, Jinjun & Bi, Wei & Liu, Fang & Zhang, Wenhui, 2021. "Exploring urban travel patterns using density-based clustering with multi-attributes from large-scaled vehicle trajectories," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 561(C).
    6. Xia, Dawen & Jiang, Shunying & Yang, Nan & Hu, Yang & Li, Yantao & Li, Huaqing & Wang, Lin, 2021. "Discovering spatiotemporal characteristics of passenger travel with mobile trajectory big data," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 578(C).
    7. Long He & Sheng Liu & Zuo‐Jun Max Shen, 2022. "Smart urban transport and logistics: A business analytics perspective," Production and Operations Management, Production and Operations Management Society, vol. 31(10), pages 3771-3787, October.
    8. Yao, Kaisen & Chen, Larry & Chen, Suren, 2025. "Time-evolving traffic resilience performance forecasting during hazardous weather toward proactive intervention," Reliability Engineering and System Safety, Elsevier, vol. 253(C).
    9. Jiayi Liu & Yanbin Li & Yanhan Xu & Castiel Chen Zhuang & Yang Hu & Yue Yu, 2024. "Impacts of Built Environment on Urban Vitality in Cultural Districts: A Case Study of Haikou and Suzhou," Land, MDPI, vol. 13(6), pages 1-26, June.
    10. Alexandre M. Florio & Nabil Absi & Dominique Feillet, 2021. "Routing Electric Vehicles on Congested Street Networks," Transportation Science, INFORMS, vol. 55(1), pages 238-256, 1-2.
    11. Sariffuddin, S. & Samsura, D. Ary A. & van der Krabben, Erwin & Setiyono, Budi & Pradoto, Wisnu, 2024. "Distressed property and spillover effect: A study of property price response to coastal flood risk," Land Use Policy, Elsevier, vol. 147(C).
    12. Tong Zhou & Xintao Liu & Zhen Qian & Haoxuan Chen & Fei Tao, 2019. "Dynamic Update and Monitoring of AOI Entrance via Spatiotemporal Clustering of Drop-Off Points," Sustainability, MDPI, vol. 11(23), pages 1-20, December.
    13. Saridakis, Charalampos & Katsikeas, Constantine S. & Angelidou, Sofia & Oikonomidou, Maria & Pratikakis, Polyvios, 2023. "Mining Twitter lists to extract brand-related associative information for celebrity endorsement," European Journal of Operational Research, Elsevier, vol. 311(1), pages 316-332.
    14. Edward He & Natashia Boland & George Nemhauser & Martin Savelsbergh, 2021. "Time-Dependent Shortest Path Problems with Penalties and Limits on Waiting," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 997-1014, July.
    15. Sun, Lu & Liu, Xinmin, 2023. "Mining of interactions between travel demand and land use mixture using multi-source data," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 629(C).
    16. Sai Wang & Jianjun Wang & Chicheng Ma & Dongyi Li & Lu Cai, 2024. "The Real-Time Dynamic Prediction of Optimal Taxi Cruising Area Based on Deep Learning," Sustainability, MDPI, vol. 16(2), pages 1-23, January.
    17. Lu, Zhong-Wen & Xu, Yuan-Hao & Chen, Jie & Hu, Mao-Bin, 2023. "Investigation of traffic-driven epidemic spreading by taxi trip data," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 632(P1).
    18. Fu, Xin & Xu, Chengyao & Liu, Yuteng & Chen, Chi-Hua & Hwang, F.J. & Wang, Jianwei, 2022. "Spatial heterogeneity and migration characteristics of traffic congestion—A quantitative identification method based on taxi trajectory data," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 588(C).
    19. Dokuz, Ahmet Sakir, 2022. "Weighted spatio-temporal taxi trajectory big data mining for regional traffic estimation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 589(C).
    20. Wagenaar, J.C. & Fragkos, I. & Faro, W.L.C., 2023. "Transportation asset acquisition under a newsvendor model with cutting-stock restrictions: Approximation and decomposition algorithms," Other publications TiSEM 97eddbd0-6e34-489c-b27d-9, Tilburg University, School of Economics and Management.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:12:y:2024:i:8:p:1255-:d:1379668. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.