# Efficient Metaheuristics for the Mixed Team Orienteering Problem with Time Windows
## 5 The Iterated Local Search Metaheuristic
This in turn would exclude other subsequent insertions whose total profit could be actually higher than that of the costly TA. The pseudocode of the **insertBestTAIn** method is listed below (Algorithm 2). It is also worth mentioning that for each walk, a doubly-linked list is used for storing the TAs in that walk. Specifically, the TAs are stored in this list in the same order that they appear in the walk. This data structure is the most appropriate for Algorithm 2 since for each candidate TA, each possible insertion point is examined along the walk and the linked lists are suitable for this sequential processing, in general. Also, after deciding the best insertion point for each candidate TA, a pointer to the node of the TA preceding that point is kept so that later the insertion of the highest overall ratio can be executed fast. Also, the update of the time attributes of TAs along the just expanded walk also requires a sequential visit of nodes of the corresponding list, which can be implemented fast. ```
BestInsertionPoint \(\leftarrow\emptyset\) BestTA \(\leftarrow\emptyset\) BestRatio \(\leftarrow-\infty\) for each candidate TA \(cp\)do  TempLowestShift \(\leftarrow\infty\)  TempBestInsertionPoint \(\leftarrow\emptyset\) for each included TA \(ip\) in \(W_{i}\)do  (feasible, shift)=check_insertion_feasibility(cp,ip) if feasible then  if shift \(<\) TempLowestShift then  TempLowestShift \(\leftarrow\) shift  TempBestInsertionPoint \(\gets ip\) if\(\frac{\text{profit}_{cp}}{\text{TempLowestShift}}>\) BestRatio then  BestInsertionPoint \(\leftarrow\) TempBestInsertionPoint  BestTA \(\gets cp\)  BestRatio \(\leftarrow\frac{\text{profit}_{cp}}{\text{TempLowestShift}}\) Insert the BestTA after BestInsertionPoint in \(W_{i}\)  Update the time attributes of all nodes along \(W_{i}\)
```  
**Algorithm 2** InsertBestTAIn (\(W_{i}\))  
The ILS algorithm escapes from the current local optimum by applying the **perturb** method. In this method a randomly selected chain of consecutive TAs is removed from the TA representation of each walk \(W_{i}\) in the solution. More specifically, for each walk \(W_{i}\), the number of the TAs that will be removed (numberOfRemoved), is chosen randomly. Then, the position (\(L\)) in \(W_{i}\) where the removal of the TAs will start, is selected randomly in the range \([1,m_{i}-1-\text{numberOfRemoved}]\) where \(m_{i}\) denotes the number of TAs in \(W_{i}\). Finally, starting from the position \(L\), (_i.e._, node \(p_{L}^{i}\)), numberOfRemoved consecutive TAs are removed from \(W_{i}\) and the time attributes associated to each one of the nodes of \(W_{i}\) are recalculated. The pseudocode of the method follows (Algorithm 3). ```
for each walk \(W_{i}\)do \(m_{i}\leftarrow\) the number of TAs in \(W_{i}\)  numberOfRemoved \(\leftarrow\) a random number in \([0,m_{i}]\) \(L\leftarrow\) a random number in \([1,m_{i}-1-\text{numberOfRemoved}]\) \(R\leftarrow\) L + numberOfRemoved \(-1\)  remove all TAs from L (\(p_{L}^{i}\)) to R (\(p_{R}^{i}\))  update the time attributes of all the nodes along \(W_{i}\)
```  
**Algorithm 3** Perturb  
The ILS algorithm loops for a number of iterations (numberOfIterations) that is given as a parameter. At each iteration, \(W\) is a random ordering of the set of the constructed walks \(\{W_{0},W_{1},\dots,W_{K-1}\}\). Note that at the first iteration each walk \(W_{i}\) in \(W\) consists only of the staring and ending nodes, _i.e._, \(W_{i}=(s_{i},e_{i}),i=0,\cdots,K-1\). Then, a loop is executed as long as \(W\) is not empty. Inside the loop, each walk \(W_{i}\) in \(W\) is considered and the best insertion for this walk is applied. If no insertion was feasible, then \(W_{i}\) is removed from \(W\). When the loop is over, the current solution is considered. If its profit is the largest found so far, the current solution becomes the best solution found so far and its profit becomes the best profit (bestProfit). The last step in the loop is the perturb step. When the method ends, the best found solution as well as the best found profit are returned.