Optimal Route Search with the Coverage of Users' Preferences

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

Optimal Route Search with the Coverage of Users' Preferences

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

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 2118-2123.

Abstract

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.

Yifeng Zeng, Xuefeng Chen, Xin Cao, Shengchao Qin, Marc Cavazza, and Yanping Xiang. 2015. Optimal Route Search with the Coverage of Users' Preferences. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 2118–2123. https://ijcai.org/proceedings/2015/300

@inproceedings{ijcai2015p300,
  title     = {Optimal Route Search with the Coverage of Users' Preferences},
  author    = {Zeng, Yifeng and Chen, Xuefeng and Cao, Xin and Qin, Shengchao and Cavazza, Marc and Xiang, Yanping},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {2118--2123},
  year      = {2015},
  month     = {7},
  note      = {Main Track},
  url       = {https://ijcai.org/proceedings/2015/300},
}

TY  - CPAPER
TI  - Optimal Route Search with the Coverage of Users' Preferences
AU  - Zeng, Yifeng
AU  - Chen, Xuefeng
AU  - Cao, Xin
AU  - Qin, Shengchao
AU  - Cavazza, Marc
AU  - Xiang, Yanping
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 2118
EP  - 2123
UR  - https://ijcai.org/proceedings/2015/300
ER  -