An Efficient Heuristic for the Vacation Planning Problem

In this paper we define the Vacation Planning Problem (VPP) as an optimization problem whose objective is to find a set of destinations in a specified region, the visiting order of the destinations in the set, and for each destination, a number of days of stay, a proposed hotel area and daily tours, i.e. ordered visits to points of interest, that maximize the satisfaction of the tourist while matching her preferences and respecting her constraints (e.g., the total number of days of stay, daily time budget). To the best of our knowledge, the VPP has not been studied so far in the literature. The problem is NP-hard and can be seen as an extension of the Tourist Trip Design Problem and its variants that focuses not only on suggesting personalized tourist routes but also optimal destinations and hotel areas as well as optimal distribution of the days of stay at different destinations, and as a variation of the Orienteering Problem with Hotel Selection. We present a heuristic approach for solving the problem and experimental results proving the efficiency of the approach.