Publication Type

Conference Proceeding Article

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

Research Areas

Intelligent Systems and Decision Analytics

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

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.

Additional URL

http://www.patatconference.org/patat2016/files/proceedings/paper_15.pdf

Share

COinS