Interactive itinerary planning

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

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

43 Citations (Scopus)

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

Other

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

Fingerprint

Feedback
Planning
User interfaces
Experiments

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Signal Processing

Cite this

Basu Roy, S., Das, G., Amer-Yahia, S., & Yu, C. (2011). Interactive itinerary planning. In 2011 IEEE 27th International Conference on Data Engineering, ICDE 2011 (pp. 15-26). [5767920] (Proceedings - International Conference on Data Engineering). https://doi.org/10.1109/ICDE.2011.5767920
Basu Roy, Senjuti ; Das, Gautam ; Amer-Yahia, S. ; Yu, Cong. / Interactive itinerary planning. 2011 IEEE 27th International Conference on Data Engineering, ICDE 2011. 2011. pp. 15-26 (Proceedings - International Conference on Data Engineering).
@inproceedings{54a5ba73aac245c5b2b777ee9695d282,
title = "Interactive itinerary planning",
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.",
author = "{Basu Roy}, Senjuti and Gautam Das and S. Amer-Yahia and Cong Yu",
year = "2011",
month = "6",
day = "6",
doi = "https://doi.org/10.1109/ICDE.2011.5767920",
language = "English (US)",
isbn = "9781424489589",
series = "Proceedings - International Conference on Data Engineering",
pages = "15--26",
booktitle = "2011 IEEE 27th International Conference on Data Engineering, ICDE 2011",

}

Basu Roy, S, Das, G, Amer-Yahia, S & Yu, C 2011, Interactive itinerary planning. in 2011 IEEE 27th International Conference on Data Engineering, ICDE 2011., 5767920, Proceedings - International Conference on Data Engineering, pp. 15-26, 2011 IEEE 27th International Conference on Data Engineering, ICDE 2011, Hannover, Germany, 4/11/11. https://doi.org/10.1109/ICDE.2011.5767920

Interactive itinerary planning. / Basu Roy, Senjuti; Das, Gautam; Amer-Yahia, S.; Yu, Cong.

2011 IEEE 27th International Conference on Data Engineering, ICDE 2011. 2011. p. 15-26 5767920 (Proceedings - International Conference on Data Engineering).

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

TY - GEN

T1 - Interactive itinerary planning

AU - Basu Roy, Senjuti

AU - Das, Gautam

AU - Amer-Yahia, S.

AU - Yu, Cong

PY - 2011/6/6

Y1 - 2011/6/6

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 - https://doi.org/10.1109/ICDE.2011.5767920

DO - https://doi.org/10.1109/ICDE.2011.5767920

M3 - Conference contribution

SN - 9781424489589

T3 - Proceedings - International Conference on Data Engineering

SP - 15

EP - 26

BT - 2011 IEEE 27th International Conference on Data Engineering, ICDE 2011

ER -

Basu Roy S, Das G, Amer-Yahia S, Yu C. Interactive itinerary planning. In 2011 IEEE 27th International Conference on Data Engineering, ICDE 2011. 2011. p. 15-26. 5767920. (Proceedings - International Conference on Data Engineering). https://doi.org/10.1109/ICDE.2011.5767920