Optimal Route Search with the Coverage of Users' Preferences

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

29 Citations (Scopus)


The preferences of users are important in route search and planning. 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 this complex problem, we pro- pose an optimal route search based on an A* variant for which we have defined an admissible heuristic function. The experiments conducted on real-world datasets demonstrate both the efficiency and accu- racy of our proposed algorithms.
Original languageEnglish
Title of host publicationProceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015)
Place of PublicationCalifornia
PublisherAAAI Press
ISBN (Print)9781577357384
Publication statusPublished - 2015


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

Cite this