TY - GEN
T1 - Interactive itinerary planning
AU - Roy, Senjuti Basu
AU - Das, Gautam
AU - Amer-Yahia, S.
AU - Yu, Cong
PY - 2011
Y1 - 2011
N2 - Planning an itinerary when traveling to a city involves substantial effort in choosing Points-of-Interest (POIs), deciding in which order to visit them, and accounting for the time it takes to visit each POI and transit between them. Several online services address different aspects of itinerary planning but none of them provides an interactive interface where users give feedbacks and iteratively construct their itineraries based on personal interests and time budget. In this paper, we formalize interactive itinerary planning as an iterative process where, at each step: (1) the user provides feedback on POIs selected by the system, (2) the system recommends the best itineraries based on all feedback so far, and (3) the system further selects a new set of POIs, with optimal utility, to solicit feedback for, at the next step. This iterative process stops when the user is satisfied with the recommended itinerary. We show that computing an itinerary is NP-complete even for simple itinerary scoring functions, and that POI selection is NP-complete. We develop heuristics and optimizations for a specific case where the score of an itinerary is proportional to the number of desired POIs it contains. Our extensive experiments show that our algorithms are efficient and return high quality itineraries.
AB - Planning an itinerary when traveling to a city involves substantial effort in choosing Points-of-Interest (POIs), deciding in which order to visit them, and accounting for the time it takes to visit each POI and transit between them. Several online services address different aspects of itinerary planning but none of them provides an interactive interface where users give feedbacks and iteratively construct their itineraries based on personal interests and time budget. In this paper, we formalize interactive itinerary planning as an iterative process where, at each step: (1) the user provides feedback on POIs selected by the system, (2) the system recommends the best itineraries based on all feedback so far, and (3) the system further selects a new set of POIs, with optimal utility, to solicit feedback for, at the next step. This iterative process stops when the user is satisfied with the recommended itinerary. We show that computing an itinerary is NP-complete even for simple itinerary scoring functions, and that POI selection is NP-complete. We develop heuristics and optimizations for a specific case where the score of an itinerary is proportional to the number of desired POIs it contains. Our extensive experiments show that our algorithms are efficient and return high quality itineraries.
UR - http://www.scopus.com/inward/record.url?scp=79957814783&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79957814783&partnerID=8YFLogxK
U2 - 10.1109/ICDE.2011.5767920
DO - 10.1109/ICDE.2011.5767920
M3 - Conference contribution
AN - SCOPUS:79957814783
SN - 9781424489589
T3 - Proceedings - International Conference on Data Engineering
SP - 15
EP - 26
BT - 2011 IEEE 27th International Conference on Data Engineering, ICDE 2011
T2 - 2011 IEEE 27th International Conference on Data Engineering, ICDE 2011
Y2 - 11 April 2011 through 16 April 2011
ER -