# Efficient Metaheuristics for the Mixed Team Orienteering Problem with Time Windows
## 5 The Iterated Local Search Metaheuristic
In a similar fashion, we may check if the insertion of a non-included profitable node \(x\) is feasible after an included TA, just by skipping the time window feasibility of the second node, _i.e._, the node \(x\) can be inserted after \(w^{i}_{k}\) (see Figure 4b) if and only if the following conditions are satisfied:  
1. leave(\(w^{i}_{k}\)) \(\leq C^{i}_{w^{i}_{k}x}\)
2. the arrival time at \(x\) is at most \(C^{i}_{x}\)
3. the leaving time from \(x\) is at most \(C^{i}_{x,w^{i}_{k+1}}\)
4. the new arrival time at \(w^{i}_{k+1}\) is at most maxArrive(\(w^{i}_{k+1}\))  
Similarly to the Algorithm 1, there is the subroutine check_insertion_feasibilty(\(x,w^{i}_{k}\)) which implements the logic above. Figure 4: Illustration of insertion’s feasibility. **(a)** Insertion of the edge \(\{y,z\}\) with the direction from \(y\) to \(z\) after node \(w^{i}_{k}\). **(b)** Insertion of the node \(x\) after node \(w^{i}_{k}\). ```
\(\triangleright\) Check if the edge \((y,z)\) can be inserted between \(w_{k}^{i}\) and \(w_{k+1}^{i}\) shift \(\gets 0\) ifleave(\(w_{k}^{i}\)) \(>C_{w_{k}^{i},y}^{i}\)then\(\triangleright\) departure when the route ahead is not available return (FALSE,shift) \(\text{firstArrive}\leftarrow\max(\text{leave}(w_{k}^{i})\),\(O_{w_{k}^{i},y}^{i})+T_{w_{k}^{i},y}\) iffirstArrive \(>C_{y}^{i}\)then\(\triangleright\) arrival at \(y\) after its closing time return (FALSE,shift) \(\text{firstLeave}\leftarrow\max(\text{firstArrive}\),\(O_{y}^{i})+T_{y}\) iffirstLeave \(>C_{y,z}^{i}\)then\(\triangleright\) departure from \(y\) with closed route \((y,z)\) return (FALSE,shift) \(\text{secondArrive}\leftarrow\max(\text{firstLeave}\),\(O_{y,z}^{i})+T_{y,z}\) ifsecondArrive \(>C_{z}^{i}\)then\(\triangleright\) arrival at \(z\) after its closing time return (FALSE,shift) \(\text{secondLeave}\leftarrow\max(\text{secondArrive}\),\(O_{z}^{i})+T_{z}\) ifsecondLeave \(>C_{z,w_{k}^{i}}^{i}\)then\(\triangleright\) departure from \(z\) with closed route \((z,w_{k+1}^{i})\) return (FALSE,shift) \(\text{newArrive}\leftarrow\max(\text{secondLeave}\),\(O_{z,w_{k+1}^{i}}^{i})+T_{z,w_{k+1}^{i}}\) ifnewArrive \(\leq\max\)Arrive(\(w_{k+1}^{i}\))then\(\triangleright\) the visits along \(W_{i}\) after \(w_{k+1}^{i}\) still valid shift \(\leftarrow\text{newArrive}-\text{arrive}(w_{k+1}^{i})\) return (TRUE,shift)
```  
**Algorithm 1** Check_insertion_feasibility \(((y,z),w_{k}^{i})\)  
The **insertBestTAIn** method implements the local search step of the ILS algorithm. The local search step takes as input a walk \(W_{i}\) of the current solution and considers for insertion in \(W_{i}\) all TAs not yet included in any walk. For each such candidate TA every possible insert position is examined, _i.e._, the insertion between every consecutive pair of included TAs, and the position of the lowest shift is stored. When all candidate TAs and possible insert positions have been examined, the TA achieving the highest ratio of profit over shift is chosen for insertion in \(W_{i}\). The use of the ratio of profit over the shift as a optimization criterion is a common approach in resource-constraint problems where profit should be maximized by properly selecting some items each having a cost and at the same time without exceeding a certain budget. A well-known algorithm which uses this sort of ratios is the optimal greedy algorithm for the fractional knapsack problem, an exemplary problem for all the resource-constrained problems. This particular ratio represents a trade-off between selecting a highly profitable item which at the same time costs a lot. Thus, it will be more beneficial if we first select highly profitable items of low cost for inclusion in the solution, that is, items giving large values in this particular ratio. If we took into account only the profit of a newly inserted TA without seeing the cost, namely the shift caused by the new insertion, we might have ended up choosing a highly profitable TA but associated with large shift value which would consume most of the available time of a walk.