Vehicle Tracking Data Imputation and Shortest Path Prediction under Stochastic Travel Time Conditions

Author

Michael J. Han, University of Tennessee, KnoxvilleFollow

Date of Award

8-2025

Degree Type

Dissertation

Degree Name

Doctor of Philosophy

Major

Civil Engineering

Major Professor

Shuai Li

Committee Members

Shuai Li, Baoshan Huang, Weizi Li, Hyeonsup Lim

Abstract

This study addresses two major challenges in transportation analytics: recovering missing truck-tracking data and predicting shortest paths under stochastic conditions. We first investigated significant data loss in truck-tracking datasets, where nearly one-third of trips were missing due to misaligned data collection windows between origin and destination points. These losses, largely unaccounted for in aggregated statistics, distorted key trends such as average journey time and trip frequency. We identified nine distinct data loss scenarios, with late starts and early ends at destination nodes contributing most significantly in our case study.

To recover the missing data, we expanded and analyzed the raw field data to assess its stochastic distribution, identifying the shifted Negative Exponential Distribution (shifted-NED) as the best fit. Validated through iterative Monte Carlo simulations (MAPE = 4.79%, MAE < 9 minutes), this model enabled the generation of synthetic missing data. By fusing these simulated values with the existing dataset, we created hybrid datasets that corrected misleading trends—replacing artificially decreasing journey times and declining trip frequencies with stable and plausible patterns. Though real-time driver behavior analysis was beyond the scope of this study due to the delayed installation of Dynamic Message Signs, our imputation process lays a foundation for such future work.

Building on this robust, corrected dataset, we turned to the challenge of predicting shortest paths in the face of stochastic travel times. Traditional deterministic algorithms fall short when future travel times are uncertain. We reframed the shortest-path problem as a stochastic one and introduced the Degree of Independence (DoI) to quantify how path interdependencies affect the likelihood of optimality. Through millions of Monte Carlo simulations across varied grid structures, we established a strong correlation between DoI and a path’s probability of being shortest.

We developed the Relative Frequency (RF) metric to quantify this advantage, showing that high-DoI paths can be far more optimal than average paths. We developed a near-perfect regression model (R² = 0.9964) that allows RF estimation across grid sizes, transforming a previously intractable stochastic problem into a simple deterministic one. Together, these contributions enable more accurate modeling of both route performance and traveler behavior under uncertainty.

Recommended Citation

Han, Michael J., "Vehicle Tracking Data Imputation and Shortest Path Prediction under Stochastic Travel Time Conditions. " PhD diss., University of Tennessee, 2025.
https://trace.tennessee.edu/utk_graddiss/12653