TARP: An Effective and Efficient Route Prediction Method via Uncertainty-Aware Traffic Imputation and Divide-and-Conquer Inference

Route prediction aims to infer the most probable route between a given Origin and Destination under a specific departure Time (ODT), based on historical trajectories and the road network. However, it remains challenging due to two key limitations. First, existing route prediction models struggle to reliably leverage real-time traffic conditions, as the data are often highly missing and noisy, making it difficult to accurately capture dynamic road conditions. Second, the large model sizes and the autoregressive decoding of long sequences incur high inference latency, making efficiency difficult to maintain while preserving accuracy. In this paper, we propose a novel Traffic-Aware Route Prediction model (TARP). To tackle the challenge of missing and noisy real-time traffic data, we propose a spatio-temporal uncertainty-aware traffic imputation module that initializes traffic conditions as Gaussian distributions and uses variance-guided attention to propagate uncertainty and emphasize reliable information. To improve inference efficiency, we propose a divide-and-conquer strategy with landmark guidance to shorten prediction horizons, and further introduce a linear-time Spatial Bottleneck Attention Mechanism (SBAM) to significantly reduce latency without compromising accuracy. Experiments on two real-world datasets show that our model consistently outperforms state-of-the-art methods in both prediction quality and efficiency. Our code is available at https://github.com/XingYuXian/TARP_main .