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

20 Citations (Scopus)

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.
Original languageEnglish
Title of host publicationProceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015)
Place of PublicationCalifornia
PublisherAAAI Press
Pages2118-2124
ISBN (Print)9781577357384
Publication statusPublished - 2015

Fingerprint

Shopping centers
Museums
Computational complexity
Planning
Experiments

Cite this

Zeng, Y., Chen, X., Cao, X., Qin, S., Cavazza, M., & Xiang, Y. (2015). Optimal Route Search with the Coverage of Users' Preferences. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015) (pp. 2118-2124). California: AAAI Press.
Zeng, Yifeng ; Chen, Xuefeng ; Cao, Xin ; Qin, Shengchao ; Cavazza, Marc ; Xiang, Yanping. / Optimal Route Search with the Coverage of Users' Preferences. Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015). California : AAAI Press, 2015. pp. 2118-2124
@inproceedings{84b0855961ae49a8b1e9c5918a812979,
title = "Optimal Route Search with the Coverage of Users' Preferences",
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.",
author = "Yifeng Zeng and Xuefeng Chen and Xin Cao and Shengchao Qin and Marc Cavazza and Yanping Xiang",
year = "2015",
language = "English",
isbn = "9781577357384",
pages = "2118--2124",
booktitle = "Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015)",
publisher = "AAAI Press",

}

Zeng, Y, Chen, X, Cao, X, Qin, S, Cavazza, M & Xiang, Y 2015, Optimal Route Search with the Coverage of Users' Preferences. in Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015). AAAI Press, California, pp. 2118-2124.

Optimal Route Search with the Coverage of Users' Preferences. / Zeng, Yifeng; Chen, Xuefeng; Cao, Xin; Qin, Shengchao; Cavazza, Marc; Xiang, Yanping.

Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015). California : AAAI Press, 2015. p. 2118-2124.

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

TY - GEN

T1 - 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

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

M3 - Conference contribution

SN - 9781577357384

SP - 2118

EP - 2124

BT - Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015)

PB - AAAI Press

CY - California

ER -

Zeng Y, Chen X, Cao X, Qin S, Cavazza M, Xiang Y. Optimal Route Search with the Coverage of Users' Preferences. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015). California: AAAI Press. 2015. p. 2118-2124