# Efficient Metaheuristics for the Mixed Team Orienteering Problem with Time Windows
## 6 The Simulated Annealing Metaheuristic  
The Simulated Annealing [18; 20] is a metaheuristic method that escapes from a local optimum by allowing moves that result in worse solutions. An initial local optimum solution is usually constructed. Then, moves that result in worse solutions are allowed with a probability that is high in the early stages of the algorithm in order to search the solution space in more depth. This probability is reduced along the execution of the method until it becomes negligible in order to allow only improving solutions and find new (possibly better) local optima. In the generic scheme of the Simulated Annealing an auxiliary parameter is used, the temperature (\(T\)). The likelihood of worse resulting moves is usually a function inversely proportional to \(T\) and proportional to the decrease of the solution's value, _i.e._, it may be \(\exp(\frac{\Delta P}{T})\), where \(\Delta P\) is the difference of the value of the resulting solution from the initial. The temperature is initially set to the maximum temperature which is high enough to allow moves to worse solutions with high probability, and is decreased after a number of iterations. The temperature is usually decreased, multiplied by a cooling factor after a number of iterations (coolingIterations). In order to add diversification, we may allow a lot of schemes, _i.e._, when the temperature becomes too low, we may reinitialize it to the maximum temperature and start a new scheme again. In our setting the initial solution of the Simulated Annealing procedure will be obtained from the **SimultaneousWalkConstruction** function. This function produces the same solution with the ILS algorithm executed for a single iteration. In the Simulated Annealing procedure, apart from the **Insert** neighborhood we also consider the **Replace** neighborhood. The **Replace** neighborhood of a feasible MTOPTW solution consists of all the solutions that can be obtained by replacing an included profitable TA in a walk by a non-included profitable TA. For example, in Figure 5 the neighboring solutions of the walk with node representation \(W_{i}=(sl_{i},u,v,w,el_{i})\) in the **Replace** neighborhood are presented, considering that the only non-included profitable TAs are the edge \(\{y,z\}\) and the node \(x\). Figure 4(a),b depict the replacement of \(u\) by the edge \(\{y,z\}\), considering both directions that the edge can be traversed, _i.e._, from \(y\) to \(z\) and from \(z\) to \(y\), respectively. Similarly, Figure 4(c),d depict the replacement of \(\{v,w\}\) by the edge \(\{y,z\}\), while Figure 4(e),f depict the replacement of \(u\) and \(\{v,w\}\) by the non-included profitable node \(x\), respectivelNote that the replacement of an included profitable TA \(p_{k}^{i}\) by a non-included one candTA, is equivalent to the removal of \(p_{k}^{i}\) followed by the insertion of candTA between \(p_{k-1}^{i}\) and \(p_{k+1}^{i}\). The Simulated Annealing procedure takes into account five parameters: the number of schemes (numberOfSchemes), the maximum temperature (maxTemperature), the number of iterations executed in each scheme (schemeIterations), the cooling factor (coolingFactor) and the iterations needed in order to update the temperature (coolingIterations). The initial solution of the Simulated Annealing procedure is obtained by the **SimultaneousWalkConstruction** function. This function derives the same solution with the ILS algorithm executed for a single iteration. Then, the Simulated Annealing method loops for numberOfSchemes schemes. In each scheme, the temperature (\(T\)) initially becomes equal to the maxTemperature and an inner loop is executed for schemeIterations iterations. In the inner loop, a non-included profitable piece (candPiece) is randomly selected as well as a walk and an included piece (inclPiece). Then, if candPiece can be inserted after inclPiece without removing any included piece, the insertion takes place. If the insertion is not feasible, then the replacement of the inclPiece by candPiece is examined.