Link Representation Learning for Probabilistic Travel Time Estimation

Lijun Sun (孙立君), Chen Xu, Qiang Wang, Lijun SunIEEE Trans. ITS 2025 · DOI

TL;DR

This paper introduces ProbETA, a novel deep probabilistic model for travel time estimation that explicitly models correlations between multiple trips. By learning "link representations," ProbETA captures both inter-trip and intra-trip dependencies, leading to more accurate and uncertainty-aware travel time predictions compared to existing methods.

What Problem Does This Paper Address?

Estimating travel time (or predicting Estimated Time of Arrival - ETA) is crucial for navigation apps and transportation systems. Traditional methods often treat each trip independently, assuming their travel times are uncorrelated. However, real-world factors like weather, traffic incidents, and driver behavior create strong correlations between trips, especially those occurring around the same time or in proximity. Ignoring these correlations can lead to inaccurate predictions and a lack of confidence intervals. Existing probabilistic models, while offering uncertainty estimates, still often rely on the independence assumption, making them impractical for capturing these real-world dependencies.

Methods

The core of ProbETA is a deep hierarchical joint probabilistic model that explicitly models the covariance between travel times of multiple trips. Key innovations include:

  • Link Representation Learning: The model learns "link representations" which are vector embeddings for road segments. These representations are then used to model the covariance matrix, capturing both inter-trip and intra-trip correlations. This is a departure from previous methods that either ignored correlations or relied on hand-crafted features.
  • Low-Rank Parameterization: To manage the computational complexity of modeling covariance matrices (which can grow quadratically with the number of links), ProbETA uses a low-rank plus diagonal approach. This significantly reduces the number of parameters to learn.
  • Trip Sub-sampling Data Augmentation: To better leverage sparse GPS data and enable fine-grained gradient backpropagation for learning link representations, the authors introduce a data augmentation technique. This involves creating "sub-trips" from original trajectories, effectively increasing the number of samples and improving the learning process.
  • Hierarchical Model: The model uses a three-tier hierarchical structure to account for daily random fluctuations and trip-specific errors, allowing for a more nuanced representation of travel time variability.
  • Conditional Estimation: For a queried trip, ProbETA uses completed trips in its spatiotemporal vicinity to estimate the conditional probability distribution of its travel time.

Datasets

The paper evaluates ProbETA on two publicly available GPS trajectory datasets:

  • Chengdu: Contains 3,186 links and 346,074 samples over 6 days.
  • Harbin: Contains 8,497 links and 1,268,139 samples over 6 days.

These datasets are standard for travel time estimation research.

Key Insights and Ideas

  • Trip correlations are crucial: The paper strongly emphasizes that ignoring trip correlations leads to significant limitations in travel time estimation accuracy. Modeling these dependencies is key to improving predictions.
  • Link representations capture geometry implicitly: Surprisingly, the learned link representations and their correlations effectively capture the underlying road network geometry without explicit geometric features being fed into the model. This suggests that the learned representations are highly interpretable and generalizable.
  • Data augmentation for better learning: The sub-sampling data augmentation technique is vital for improving the learning of link representations, especially when dealing with sparse GPS data. It allows for more effective gradient propagation at the link level.
  • Hierarchical modeling for nuanced uncertainty: The hierarchical structure helps disentangle different sources of uncertainty (day-specific vs. trip-specific), leading to more accurate probabilistic predictions.

Key Results

  • Superior Accuracy: ProbETA consistently outperforms state-of-the-art deterministic and probabilistic baselines. It achieved an average reduction of over 12.11% in Mean Absolute Percentage Error (MAPE) on the Chengdu dataset and 13.34% on the Harbin dataset.
  • Improved Uncertainty Quantification: The probabilistic nature of ProbETA provides confidence intervals, which are absent in deterministic models.
  • Ablation Studies:
    • Removing multi-trip modeling (ProbETA-w/o MT) significantly degraded performance, highlighting the importance of joint modeling.
  • Data augmentation (ProbETA-w/o DA) provided a notable improvement, reducing MAPE by 0.52% and 0.44%.
  • Time discretization (ProbETA-w/o TD) also contributed positively, showing gains of 0.48% and 0.32%.
  • Interpretability: Visualizations of learned correlations and link embeddings show alignment with real-world road network structures and traffic patterns.

Limitations and Future Work

  • Time Discretization: The current model uses a discrete time horizon for learning link embeddings. The authors suggest future work could explore continuous modeling of link embedding vectors using dynamic graph neural networks to better capture temporal trends and address spatiotemporal sparsity.
  • Computational Cost: While ProbETA uses efficient parameterization, its training time is slightly higher than some baselines due to the complexity of joint probabilistic modeling. However, the authors deem it acceptable given the performance gains.
  • Generalization to Rare Events: The current model focuses on typical traffic variations. Future work could explore incorporating rare temporal conditions like events and holidays more explicitly.

Summary updated

BibTeX
@article{2025link,
  author = {Lijun Sun (孙立君) and Chen Xu and Qiang Wang and Lijun Sun},
  title = {{Link Representation Learning for Probabilistic Travel Time Estimation}},
  journal = {IEEE Trans. ITS},
  year = {2025},
  doi = {10.1109/tits.2025.3590075},
}
Figure