A Tabu Search approach for Multi Constrained Team Orienteering Problem and its application in touristic trip planning

The touristic trip planning problem can be considered as a Multi Constrained Team Orienteering Problem with Time Windows (MCTOPTW). The MCTOPTW is characterized with a set of points of interest (POI), each having a score, a time window and some attributes such as the type or entry fee. The maximum number of POIs of certain types that can be included into the itinerary is limited. A tourist can visit the POIs during their respective time windows. The objective is to visit the points that have the highest scores during specified periods of time. This paper proposes a Tabu Search approach for solving the MCTOPTW problem. To explore the neighborhood the moves Insert, Replace and Swap are applied. Additionally, the algorithm employs a tabu list, a perturbation and a diversification mechanism. The algorithm is evaluated on benchmark instances from the literature and its performance is compared to the state of the art results.