A Large Neighborhood Search Matheuristic for Tourist Trip Design Problems

Tourists visiting a destination for one or several days, face the problem to decide which points of interest (POIs) would be more interesting to visit and to design a trip for each day, which consists of two main issues: firstly, to determine which POIs to visit and secondly to decide the visiting order among them. Each POI is associated with a score that measure the degree of satisfaction associated with its visit. The basic version of the Tourist Trip Design Problem has been modeled in the literature as a Team Orienteering Problem (TOP), but, in order to better describe real problems, further issues must be addressed, such as opening time windows, visiting time and cost, category to which the site belongs, exc. As stated in the literature, the TOP can be solved to the optimality, in reasonable time, only for small and medium sized instances. Several heuristics and metaheuristics have been proposed to address large sized instances, nevertheless, methods which are very performing on the basic version of the TOP, may results less effective when extended versions with additional constraints. The aim of this work is to provide a general metaheuristic framework able to reach competitive results on different variants of the TOP.