Publication Type
Conference Proceeding Article
Version
publishedVersion
Publication Date
8-2016
Abstract
With the pervasive use of recommender systems and web/mobile applications such as TripAdvisor and Booking.com, an emerging interest is to generate personalized tourist routes based on a tourist’s preferences and time budget constraints, often in real-time. The problem is generally known as the Tourist Trip Design Problem (TTDP) which is a route-planning problem on multiple Points of Interest (POIs). TTDP can be considered as an extension of the classical problem of Team Orienteering Problem with Time Windows (TOPTW). The objective of the TOPTW is to determine a fixed number of routes that maximize the total collected score. The TOPTW also considers the time window constraints when the visit at a particular node has to start within a predefined time window. In the context of the TTDP, the utility score for a particular node can be treated as the user’s preference on a POI. In this paper, we propose a mathematical model for the TTDP that extends the TOPTW constraints by incorporating more real-world constraints, such as different total travel time budgets, different start and end nodes for routes. We then propose an Iterated Local Search (ILS) algorithm to solve both TTDP and TOPTW. We implement our ILS to provide tour guidance in the Singapore context. We show experimentally that ILS is able to solving real-world problem instances within a few seconds, and our ILS can improve 19 best known solution values on the benchmark TOPTW instances.
Keywords
Recommender System, Tourist Trip Design Problem, Team Orienteering Problem with Time Windows, Iterated Local Search
Discipline
Artificial Intelligence and Robotics | Computer Sciences | Tourism and Travel
Publication
PATAT 2016: Proceedings of the 11th International Conference of the Practice and Theory of Automated Timetabling: Udine, Italy, August 23-26, 2016
First Page
163
Last Page
179
ISBN
9780992998417
Publisher
PATAT
City or Country
Udine, Italy
Citation
GUNAWAN, Aldy; LAU, Hoong Chuin; and LU, Kun.
A fast algorithm for personalized travel planning recommendation. (2016). PATAT 2016: Proceedings of the 11th International Conference of the Practice and Theory of Automated Timetabling: Udine, Italy, August 23-26, 2016. 163-179.
Available at: https://ink.library.smu.edu.sg/sis_research/3405
Copyright Owner and License
LARC
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
http://www.patatconference.org/patat2016/files/proceedings/paper_15.pdf