Implementation of an iterated local search heuristic for the team orienteering problem with time windows

When tourists visit a city or region, they cannot visit every possible attraction as they are constrained in time. A Personalized Electronic Tourist guide may be used to derive a personalized tourist route that maximizes the tourists’ satisfaction. The planning problem that needs to be solved can be modeled as a Team Orienteering Problem with Time Windows (TOPTW). In the TOPTW, a set of locations is given, each with a score, a service time and a time window. The goal is to maximize the sum of the collected scores by a fi number of routes, while the visits are within the time windows of the locations and the time budget of the tourist. Each route can be interpreted as a day trip. In this thesis, we discuss the algorithm used to solve the TOPTW developed by Vansteenwegen et al. (2009). They developed an iterated local search heuristic with an insertion step and a shake step. We implement this heuristic and we compare the results. Moreover, we extend the problem by adding the possibility to add more constraints, such as a limited money budget. This problem can be solved as a Multi Constrained Team Orienteering Problem with Time Windows (MCTOPTW). To solve a MCTOPTW, we make the adjustments to the heuristic proposed by Garcia et al. (2010) and we compare the results.