Optimal Route Search with the Coverage of Users' Preferences

Yifeng Zeng, Xuefeng Chen, Xin Cao, Shengchao Qin, Marc Cavazza, Yanping Xiang

Research output: Contribution to conferencePaperpeer-review

150 Downloads (Pure)


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.
Original languageEnglish
Publication statusPublished - 2015
Event24th International Joint Conference on Artificial Intelligence - Buenos Aires, Argentina
Duration: 25 Jul 201531 Jul 2015


Conference24th International Joint Conference on Artificial Intelligence
Abbreviated titleIJCAI 2015
CityBuenos Aires

Bibliographical note

AAAI authors are granted back the right to use their own papers for noncommercial uses. Publisher advice [Recieved: 17/12/2015]


Dive into the research topics of 'Optimal Route Search with the Coverage of Users' Preferences'. Together they form a unique fingerprint.

Cite this