## 3 Addressing the Dynamic Traveling Salesman Problem
### Adapting in Dynamic Environments  
ACO algorithms have proven effective in addressing dynamic optimization problems because they are very robust algorithms, according to [PERSON] et al. [30]. However, when a dynamic change occurs, the ACO's pheromone trails of the previous environment will become outdated because they will be associated with the previous optimum. A straightforward way to tackle the dynamic changes in the DTSP using a conventional ACO, such as the \(\mathcal{MM}\)AS, is to restart the optimization process whenever changes occur. In particular, the pheromone trail limit values \(\tau_{max}\) and \(\tau_{min}\) are reset back to their initial values, and all the pheromone trails are re-initialized to the initial \(\tau_{0}\) value, as in Equation (5), whenever a dynamic change is detected. There are two concerns when restarting an ACO: (1) the dynamic changes are not always detectable [31], and (2) a portion of the previous pheromone trails that can help discover the new optimum faster is erased [32]. For the first concern, the changes in the DTSP can be detected by re-evaluating a constant solution (or detector) on every iteration (note that more than one detector can be used). If a change occurs in the quality of the detector, then a dynamic change is recorded. In this way, a change is always detected for the DTSP with node changes but not for the DTSP with weight changes. This is because the weights affected by the dynamic change may not belong to that particular detector, and hence, its quality will not be affected [10]. For the second concern, the pheromone trails of the previous environment will be most probably useful when the changing environments are correlated, e.g., when the dynamic changes are small to medium, the new environment is more likely to be similar to the previous environment. As a consequence, some of the previous pheromone trails will still be useful to the new environment. Therefore, a more efficient way is to allow the pheromone evaporation defined in Equation (5) to remove the useless pheromone trails and utilize the useful pheromone trails of the previous environment. Specifically, the useless pheromone trails will reach the \(\tau_{min}\) value due to the constant deduction of pheromone evaporation, whereas the useful pheromone trails will be reinforced up to the \(\tau_{max}\) due to the pheromone deposit in Equation (6). In other words, ACO will be able to adapt to the newly generated environment. Figure 1 demonstrates the performance of \(\mathcal{MM}\)AS with and without pheromone re-initialization and proves our claims above. Specifically, it can be easily observed that when the dynamic changes are small (i.e., \(m=0.1\)), adapting to the changes maintains better offline performance (see Equation (9)) in most environmental changes (except when \(T=3\)), whereas when the dynamic changes are severe (i.e., \(m=0.75\)), re-initializing the pheromone trails maintains better offline performance in most environmental changes (except when \(T=7\) and \(T=9\)). More details regarding the experimental setup of Figure 1 are given later in Section 4. A more advanced way is to use the pheromone update policy of the population-based ACO (P-ACO) that has been specifically designed to address optimization problems with dynamic environments [13]. The overall P-ACO pheromone procedure is presented in Algorithm 2, lines 21-33. In particular, an archive, i.e., \(pop(t)\), of iteration-best ants is maintained. For every iteration \(t\), the iteration-best ant enters \(pop(t)\), and a positive constant pheromone update is added to the trails associated with the arcs that belong to its solution as follows:  
\[\tau_{ij}\leftarrow\tau_{ij}+\Delta\tau,\forall\ (i,j)\in s^{ib}, \tag{7}\]  
where \(\Delta\tau=(\tau_{max}-\tau_{0})/K\) is the constant pheromone value added, \(s^{ib}\) is the solution of the iteration-best ant, \(K\) is the size of \(pop(t)\), and \(\tau_{max}\) and \(\tau_{0}\) are the maximum and initial pheromone trail values, respectively.