Abstract
Personalized Route Recommendation (PRR) aims to suggest paths that align with individual user preferences and real-world constraints. Traditional methods often rely on rigid heuristics or pure deep learning models that struggle with long-term planning. This paper introduces NASR, a framework that "neuralizes" the classic A* search algorithm. By replacing handcrafted cost functions with attention-based Recurrent Neural Networks (RNNs) and Graph Attention Networks (GATs), NASR learns to navigate complex road networks while reflecting unique user behaviors. Experimental results on three large-scale trajectory datasets demonstrate that NASR significantly outperforms existing baselines in accuracy and search efficiency.
Introduction
Finding the "best" route from a source to a destination is a fundamental problem in navigation services. However, "best" is subjective; it depends on user habits, time of day, and specific road network characteristics. Traditional heuristic search algorithms like A* are efficient but limited by simple cost functions (e.g., shortest distance). Conversely, pure deep learning models excel at sequence modeling but often fail to reach distant destinations effectively.
NASR bridges this gap by embedding learnable neural components within the A* search framework. This approach maintains the mathematical rigor of search while leveraging the representational power of deep learning to capture "soft" preferences and complex temporal patterns.
The NASR Framework
The A* algorithm relies on an evaluation function $f(n) = g(n) + h(n)$, where $g(n)$ is the cost from the source to the current node and $h(n)$ is the estimated cost to the destination. NASR transforms these components into neural modules.
Neuralizing $g(n)$ with RNNs
Instead of a scalar distance, NASR uses an attention-based Gated Recurrent Unit (GRU) to model the "observed cost." This component generates a "moving state" vector that encapsulates contextual information such as user identity, current location, and temporal features. Dual attention mechanisms—intra-trajectory attention for the current trip and inter-trajectory attention for historical patterns—ensure that the model accounts for both immediate and long-term user behavior.
Neuralizing $h(n)$ with a Value Network
To estimate the cost of the unobserved path to the destination, NASR employs a value network built upon a context-aware Graph Attention Network (GAT). This network incorporates the user's moving state and discretized distance bins to understand road connectivity and predict future movements toward the destination. The model is trained using Temporal Difference (TD) learning, a reinforcement learning technique that optimizes the value network based on multi-step future decisions.
Experimental Evaluation
The model was rigorously tested on three real-world datasets: Beijing Taxi (low-frequency), Beijing Bicycle (high-frequency), and the popular Porto Taxi dataset. All trajectories were map-matched to their respective road networks to ensure structural consistency.
Key Results and Discussion
NASR consistently achieved higher F1-scores than state-of-the-art baselines. For instance, in the Beijing Taxi dataset, it reached an F1-score of 0.834 for short routes, significantly higher than models like DeepMove (0.749).
Robustness and Efficiency
A significant advantage of NASR is its performance on long-distance queries. While traditional models often degrade as the path length increases, NASR's GAT-based value network provides global structural knowledge that maintains accuracy. Furthermore, the "smarter" cost function acts as an effective pruning mechanism, reducing the search space by exploring fewer irrelevant nodes compared to standard A*.
Insights into Human Behavior
The study confirms that human route choices are rarely dictated by distance alone. By learning from data, NASR captures nuances like traffic avoidance and personal preferences that handcrafted heuristics miss. The generated routes also showed lower edit distances to ground-truth paths, indicating high structural similarity to real human choices.
Conclusion
NASR successfully "neuralizes" the A* algorithm, creating a powerful tool for personalized route recommendation. While the model currently depends on accurate road network data and involves higher computational costs than simple heuristics, it sets a new standard for integrating deep learning with classical search. Future work will focus on optimizing real-time performance and extending the framework to environments with incomplete map data.
Summary updated