Interactive itinerary planning

Senjuti Basu Roy, Gautam Das, S. Amer-Yahia, Cong Yu

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

56 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publication2011 IEEE 27th International Conference on Data Engineering, ICDE 2011
Pages15-26
Number of pages12
DOIs
StatePublished - Jun 6 2011
Externally publishedYes
Event2011 IEEE 27th International Conference on Data Engineering, ICDE 2011 - Hannover, Germany
Duration: Apr 11 2011Apr 16 2011

Publication series

NameProceedings - International Conference on Data Engineering
ISSN (Print)1084-4627

Other

Other2011 IEEE 27th International Conference on Data Engineering, ICDE 2011
Country/TerritoryGermany
CityHannover
Period4/11/114/16/11

All Science Journal Classification (ASJC) codes

  • Software
  • Signal Processing
  • Information Systems

Fingerprint

Dive into the research topics of 'Interactive itinerary planning'. Together they form a unique fingerprint.

Cite this