A Taboo Search approach for solving Multi Constrained Team Orienteering Problem for application in touristic trip planning

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