DRNCS: Dual-Level Route Generation Model Based on Node Contraction and Shortcuts

Abstract

Route prediction is a fundamental task in mapping services, with critical applications in trajectory reconstruction and route recommendation. However, existing algorithms face efficiency challenges, particularly for long routes. The primary challenge is to enhance computational efficiency while maintaining prediction accuracy, especially in large-scale, real-time scenarios. To address this challenge, we propose an accelerated route generation model DRNCS based on node contraction and shortcut acceleration, utilizing a dual-level model specifically designed for path prediction. By effectively employing Shortcut-Edge Differential Contraction, we manage to contract nodes in a way that avoids the common problem of out-degree explosion, which is typically encountered in conventional node contraction methods. This approach allows us to transform the original graph into a much sparser representation, preserving the structural integrity while significantly reducing the complexity of the graph. We then compute and store the most likely shortcuts using two methods: merging historical routes and applying a probability-based bidirectional Dijkstra’s algorithm on historical paths. Ultimately, the final prediction results are generated by predicting on the sparse graph and invoking the stored shortcut data, which is produced by the model trained on the original graph. Through in-depth experiments on real-world datasets, we establish that our model imparts significant improvement in generation speed while maintaining query accuracy over state-of-the-art approaches and demonstrates advantages in reachability. This provides robust support for the practical application of our algorithm in real-world route generation scenarios.