Empowering A* Search Algorithms with Neural Networks for Personalized Route Recommendation

Jingyuan Wang, Ning Wu, Wayne Xin Zhao, Fanzhang Peng, Xin Lin

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.

The NASR architecture integrates user history and current sub-trajectories to predict the next location within a road network.

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).

Ablation studies examining the impact of the RNN component, the value network, and the TD learning method on performance across different route lengths.

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

Abstract

Personalized Route Recommendation (PRR) aims to generate user-specific route suggestions in response to users' route queries. Early studies cast the PRR task as a pathfinding problem on graphs, and adopt adapted search algorithms by integrating heuristic strategies. Although these methods are effective to some extent, they require setting the cost functions with heuristics. In addition, it is difficult to utilize useful context information in the search procedure. To address these issues, we propose using neural networks to automatically learn the cost functions of a classic heuristic algorithm, namely A* algorithm, for the PRR task. Our model consists of two components. First, we employ attention-based Recurrent Neural Networks (RNN) to model the cost from the source to the candidate location by incorporating useful context information. Instead of learning a single cost value, the RNN component is able to learn a time-varying vectorized representation for the moving state of a user. Second, we propose to use a value network for estimating the cost from a candidate location to the destination. For capturing structural characteristics, the value network is built on top of improved graph attention networks by incorporating the moving state of a user and other context information. The two components are integrated in a principled way for deriving a more accurate cost of a candidate location. Extensive experiment results on three real-world datasets have shown the effectiveness and robustness of the proposed model.
BibTeX
@inproceedings{wang2019empowering,
  author = {Jingyuan Wang and Ning Wu and Wayne Xin Zhao and Fanzhang Peng and Xin Lin},
  title = {{Empowering A* Search Algorithms with Neural Networks for Personalized Route Recommendation}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2019},
  doi = {10.1145/3292500.3330824},
}
Figure