Personalized Route Recommendation with Neural Network Enhanced A* Search Algorithm

In this work, we study an important task in location-based services, namely Personalized Route Recommendation (PRR). Given a road network, the PRR task aims to generate user-specific route suggestions for replying to users' route queries. A classic approach is to adapting search algorithms to construct pathfinding-like solutions. These methods typically focus on reducing search space with suitable heuristic strategies. For these search algorithms, heuristic strategies are often handcrafted, which are not flexible to work in complicated task settings. In this paper, we propose to improve search algorithms with neural networks for solving the PRR task based on the widely used A* algorithm. 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. Second, we propose to use an estimation network for predicting the cost from a candidate location to the destination. The two components are integrated in a principled way for deriving a more accurate cost of a candidate location for the A* algorithm. Extensive experiment results on three real-world datasets have shown the effectiveness and robustness of the proposed model.