A fast algorithm for personalized travel planning recommendation
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 Touri...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | text |
| Language: | English |
| Published: |
Institutional Knowledge at Singapore Management University
2016
|
| Subjects: | |
| Online Access: | https://ink.library.smu.edu.sg/sis_research/3405 https://ink.library.smu.edu.sg/context/sis_research/article/4406/viewcontent/FastAlgorPersonlizedTravel_PATAT_2016.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Singapore Management University |
| Language: | English |
| Summary: | 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. |
|---|