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.
|Publication status||Published - 2015|
|Event||24th International Joint Conference on Artificial Intelligence - Buenos Aires, Argentina|
Duration: 25 Jul 2015 → 31 Jul 2015
|Conference||24th International Joint Conference on Artificial Intelligence|
|Abbreviated title||IJCAI 2015|
|Period||25/07/15 → 31/07/15|
Bibliographical noteAAAI authors are granted back the right to use their own papers for noncommercial uses. Publisher advice [Recieved: 17/12/2015]
Zeng, Y., Chen, X., Cao, X., Qin, S., Cavazza, M., & Xiang, Y. (2015). Optimal Route Search with the Coverage of Users' Preferences. Paper presented at 24th International Joint Conference on Artificial Intelligence, Buenos Aires, Argentina.