# Efficient Metaheuristics for the Mixed Team Orienteering Problem with Time Windows
## 5 The Iterated Local Search Metaheuristic  
The Iterated Local Search [18; 19] is a metaheuristic method widely used in combinatorial optimization problems in order to search the solution space extensively. The intuition of this metaheuristic is to iteratively reach a local optimum solution by applying a local search process and then perturb the solution. Specifically, the local search process explores a neighbourhood by iteratively generating the neighbourhood of the current solution and moving from the current solution to an improving neighbouring solution. This process is repeated until a local optimum is reached. The solution is perturbed in order to escape from the local optimum and reach a different local optimum in the next iteration. By exploring different local optimum solutions, the method is expected to produce better results than a simple local search method. The neighborhood structure in our MTOPTW metaheuristic approach is obtained as follows. Consider a solution of an instance of the problem and any walk \(W_{i}\) belonging to that solution. A neighboring solution (**Insert** Neighborhood) can be obtained by inserting a non-included TA between two consecutive nodes of the walk \(W_{i}\) that are not connected with a profitable edge. Figure 1: Preprocessing steps. Profitable edges and profitable nodes are colored gray. (**a**) Profitable edges incident to a profitable node; (**b**) Elimination of the adjacency among the profitable node and profitable edges; (**c**) Profitable edges incident to the same node; (**d**) Elimination of the adjacency among profitable edges. Figure 2: Walk representation. For example in Figure 3 we consider the neighboring solutions of the single walk solution with node representation \(W_{i}=(sl_{i},u,v,w,el_{i})\) given in Figure 2. We consider that there are only two non-included TAs, the profitable edge \(\{y,z\}\) and the profitable node \(x\). Figure 3a-f show the neighboring solutions that are produced by inserting the edge \(\{y,z\}\) between two consecutive nodes of the walk. Figure 3a,b depict the two solutions obtained by inserting \(\{y,z\}\) between \(sl_{i}\) and \(u\), the former with direction from \(y\) to \(z\) and the latter from \(z\) to \(y\). Similarly, Figure 3c,d depict the insertion of \(\{y,z\}\) between \(u\) and \(\{v,w\}\), while Figure 3e,f present the solution obtained by inserting \(\{y,z\}\) after \(\{v,w\}\). As far as the non-included profitable node \(x\) is concerned, the neighboring solutions are depicted in Figure 3g-i, where the insertion after \(sl_{i}\), \(u\) and \(\{v,w\}\) is considered, respectively. Note, that neither \(\{y,z\}\) nor \(x\) can be inserted between \(v\) and \(w\), since \(\{v,w\}\) is a profitable edge. Inspired by [17], each included node in a walk of the solution is associated with its arrival (arrive), starting (start) and leaving (leave) time, as well as the latest time the arrival at the node can take place (maxArrive), such that the walk remains feasible. Considering the walk \(W_{i}=(w_{0}^{i},w_{1}^{i},\ldots,w_{i-1}^{i})\) in its node representation, that takes place in day \(d\), the time attributes of each included node are given by the recursive formulas:  
Figure 3: Illustration of the **Insert** Neighborhood.