A fast algorithm for personalized travel planning recommendation

• Main Authors: GUNAWAN, Aldy, LAU, Hoong Chuin, LU, Kun
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2016
• Subjects: Recommender System; Tourist Trip Design Problem; Team Orienteering Problem with Time Windows; Iterated Local Search; Artificial Intelligence and Robotics; Computer Sciences; Tourism and Travel
• 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
• Institution: Singapore Management University

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.