An Efficient Method for Multi-request Route Search

摘要

Location-based services are ubiquitous in our daily lives, which make our lives more convenient. One of the popular topics is the route planning for Point of Interest in the urban environments. In this article, we study on Multi-Request Route Planning. The previous research only provided an approximate solution to this problem. In this work, we investigate the possibility o ffinding the best route within a reasonable time and propose the One-way Search algorithm. This method expands the node in one direction in one search, and each search will reduce the candidate nodes for the next search. In the experiment, we compare our method with the Anytime Potential Search/Anytime Non-Parametric A* algorithm, which was proposed in recent years and is also an optimal solution. The evaluation is based on two real-world datasets, and the results show that our method outperforms the competition method in terms of execution time and memory usage.