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 conferencePaper

17 Downloads (Pure)

Abstract

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

Conference

Conference24th International Joint Conference on Artificial Intelligence
Abbreviated titleIJCAI 2015
CountryArgentina
CityBuenos Aires
Period25/07/1531/07/15

Bibliographical note

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

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

  • Profiles

    Cite this

    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.