# Efficient Metaheuristics for the Mixed Team Orienteering Problem with Time Windows
## 5 The Iterated Local Search Metaheuristic
**(a)** Insertion of the edge \(\{y,z\}\) between \(sl_{i}\) and \(u\) with direction from \(y\) to \(z\); **(b)** Insertion of the edge \(\{y,z\}\) between \(sl_{i}\) and \(u\) with direction from \(z\) to \(y\); **(c)** Insertion of the edge \(\{y,z\}\) between \(u\) and \(\{v,w\}\) with direction from \(y\) to \(z\); **(d)** Insertion of the edge \(\{y,z\}\) between \(u\) and \(\{v,w\}\) with direction from \(z\) to \(y\); **(e)** Insertion of the edge \(\{y,z\}\) after \(\{v,w\}\) with direction from \(y\) to \(z\); **(f)** Insertion of the edge \(\{y,z\}\) after \(\{v,w\}\) with direction from \(z\) to \(y\); **(g)** Insertion of the node \(x\) between \(sl_{i}\) and \(u\); **(h)** Insertion of the node \(x\) between \(u\) and \(\{v,w\}\); **(i)** Insertion of the node \(x\) after \(\{v,w\}\). arrive(\(w^{i}_{0}\)) = start(\(w^{i}_{0}\)) = leave(\(w^{i}_{0}\)) = \(st_{i}\) and for each \(k=0,1,\ldots,l_{i}-2\) arrive(\(w^{i}_{k+1}\)) = max(leave(\(w^{i}_{k}\)),\(O^{i}_{w^{i}_{k}w^{i}_{k+1}}\)) + \(T_{w^{i}_{k},w^{i}_{k+1}}\), start(\(w^{i}_{k+1}\)) = max(arrive(\(w^{i}_{k+1}\)),\(O^{i}_{w^{i}_{k+1}}\)) and leave(\(w^{i}_{k+1}\)) = start(\(w^{i}_{k+1}\)) + \(T_{w^{i}_{k+1}}\). The maxArrive time of the nodes is calculated recursively from the ending location to the start as follows:  
maxArrive(\(w^{i}_{l_{i}-1}\)) = \(et_{i}\) and for each \(k=l_{i}-2,l_{i}-3,\ldots,1,0\) maxArrive(\(w^{i}_{k}\)) = min(\(C^{i}_{w^{i}_{k}}\),\(C^{i}_{w^{i}_{k}w^{i}_{k+1}}\) - \(T_{w^{i}_{k}}\),maxArrive(\(w^{i}_{k+1}\)) - \(T_{w^{i}_{k}}\),\(T_{w^{i}_{k}w^{i}_{k+1}}\)). Using the previously introduced time attributes of the included nodes, checking that the insertion of a non-included TA after an included TA in a walk \(W_{i}\) is feasible requires constant time, _i.e._, time independent of the size of the walk. To see this, consider that the candidate for insertion TA will be inserted between nodes \(w^{i}_{k}\) and \(w^{i}_{k+1}\), _i.e._, after the included TA whose last node is \(w^{i}_{k}\), (_i.e._, either the profitable node \(w^{i}_{k}\) or the profitable edge \((w^{i}_{k-1},w^{i}_{k})\)) and that the walk takes place at day \(d\). In the case that the candidate for insertion TA is the edge \(\{y,z\}\), we have to examine both directions, _i.e._, from \(y\) to \(z\) and from \(z\) to \(y\). The insertion of \(\{y,z\}\) with the direction from \(y\) to \(z\) after node \(w^{i}_{k}\) (see Figure 4a) is feasible if and only if the following conditions are satisfied:  
1. leave(\(w^{i}_{k}\)) \(\leq C^{i}_{w^{i}_{k}y}\)
2. the arrival time at \(y\) is at most \(C^{i}_{y}\)
3. the leaving time from \(y\) is at most \(C^{i}_{y,z}\)
4. the arrival time at \(z\) is at most \(C^{i}_{z}\)
5. the leaving time from \(z\) is at most \(C^{i}_{z,w^{i}_{k+1}}\)
6. the new arrival time at \(w^{i}_{k+1}\) is at most maxArrive(\(w^{i}_{k+1}\))  
If the insertion of the edge \((y,z)\) after the included TA (inclTA) with last node \(w^{i}_{k}\) is feasible, the difference between the new arrival time at \(w^{i}_{k+1}\) and the former one will be considered as the time shift. Notice that the insertion of a new TA in a walk always results in a positive time shift as this insertion is done over a non profitable edge corresponding to shortest time connection. A negative shift would be possible only if the insertion process allowed insertion over profitable edges. The pseudo code of the method that checks the feasibility of the insertion of the edge \((y,z)\) after an included TA with last node \(w^{i}_{k}\) follows (Algorithm 1).