## 3 Addressing the Dynamic Traveling Salesman Problem
### Adapting in Dynamic Environments
Whenever a dynamic change occurs, the solutions represented by the current ants in the population list may become invalid (e.g., when existing nodes are removed and replaced with new nodes). Therefore, these solutions are repaired heuristically using the _KeepElite_ principle [33]. Specifically, the affected nodes are removed from the solution, reconnecting the successor and predecessor nodes. The new nodes are inserted in the best possible position of the solution, causing, in this way, the least increase in the solution quality. At the same time, the corresponding pheromone trails associated with the arcs of the affected nodes are updated. When \(pop(t)\) is full, the current iteration-best ant needs to replace an existing ant, say \(r\), in \(pop(t)\), following a negative constant update to its corresponding pheromone trails, which is defined as follows:  
\[\tau_{ij}\leftarrow\tau_{ij}-\Delta\tau,\forall\ (i,j)\in s^{r}, \tag{8}\]  
where \(\Delta\tau=(\tau_{max}-\tau_{0})/K\) is the constant deducted pheromone value (the same with the added value) and \(s^{r}\) is the solution of the ant to be replaced, typically the oldest entry of the population list \(pop(t)\). Note that pheromone evaporation is not used in the P-ACO algorithm. However, it is able to adapt to the changes because outdated pheromone trails are removed directly from the population list. The overall application of \(\mathcal{MM}\)AS and P-ACO algorithms for the DTSP is described in Algorithm 3. It is worth mentioning that in both \(\mathcal{MM}\)AS and P-ACO, the solution of the best-so-far ant is repaired using _KeepElite_, and the heuristic information is updated, reflecting the newly generated distances as in Equation (2), whenever a dynamic change occurs (see Algorithm 3, lines 16-33). Figure 1: Offline performance results (averaged over 50 runs) of \(\mathcal{MM}\)AS without pheromone re-initialization (Adapting) and of \(\mathcal{MM}\)AS with pheromone re-initialization (Restarting) for each environmental change on kroA100 with nodes with small dynamic changes (**left**) and severe dynamic changes (**right**). ```
1:\(t\gets 0\)
2:\(\mathcal{C}^{bs}\leftarrow\infty\)
3:for\(\forall(i,j)\in A\)do
4:\(\tau_{ij}\leftarrow\tau_{0}\)
5:\(\eta_{ij}\gets 1/d_{ij}(0)\)
6:endfor
7:while termination condition not met do
8: Construct Solutions(\(t\)) % Algorithm 1
9:\(s^{ib}\leftarrow\) find best ant at iteration \(t\)
10:if\(\phi(s^{ib},t)\) is better than \(\phi(s^{bs},t)\)then
11:\(s^{bs}\gets s^{ib}\)
12:\(\mathcal{C}^{bs}\gets C^{ib}\)
13:endif
14: Pheromone Update(\(t,s^{ib},s^{bs}\)) % Algorithm 2
15:if dynamic change occurs then
16:if\(\mathcal{M}\)MAS \(\mid\) P-ACO then
17: Repair \(s^{bs}\)
18:for\(\forall(i,j)\in A\)do
19:\(\eta_{ij}\gets 1/d_{ij}(T)\)
20:endfor
21:if P-ACO then
22:for\(\forall(i,j)\in A\)do
23:\(\tau_{ij}\leftarrow\tau_{0}\)
24:endfor
25:for each ant \(k\in pop(t)\)do
26: Repair \(s^{k}\)
27:for each arc\((i,j)\in s^{k}\)do
28:\(\tau_{ij}\leftarrow\tau_{ij}+\Delta\tau\)
29:endfor
30:endfor
31:endif
32:endif
33:endif
34:\(t\gets t+1\)
35:endwhile
```  
**Algorithm 3** ACO for DTSP