Optimal Route Search with the Coverage of Users' Preferences

The preferences of users are important in route search and planning. Users may also weight their preferences differently. For example, when a user plans a trip within a city, their preferences can be expressed as keywords shopping mall, restaurant, and museum, with weights 0.5, 0.4, and 0.1, respectively. The resulting route should best satisfy their weighted preferences. In this paper, we take into account the weighted user preferences in route search, and present a keyword coverage problem, which finds an optimal route from a source location to a target location such that the keyword coverage is optimized and that the budget score satisfies a specified constraint. We prove that this problem is NP-hard. To solve the complex problem, we propose the optimal route search by adapting the A* algorithm. An admissible heuristic function is developed to preserve the solution optimality. The experiments conducted on real-world datasets demonstrate both the efficiency and accuracy of our proposed algorithms.