## 5 Heuristic Approaches
### Dynamic Island Model
#### 5.2.1 Principle
Moreover, the DIM metaheuristic has been developed in C++17. The tests have been performed on a desktop computer with Intel i5 2 GHz CPU processor and 4 GB RAM. Solving time is limited to 3600 s for each instance. According to the Taguchi analysis performed on the FR TI Pulse, the best setting is the following : \(\sigma=3\times p_{\max}\), \(\delta=50\%\), \(\tilde{s}_{j}\) = Max. With regard to the TI On/Off model, the most performant setting is \(\sigma=2\times p_{\max}\), \(\delta=25\%\), \(\tilde{s}_{j}\)= Max. For the FR heuristics, the solving time of the subproblem at each step has been limited to \(nT/3600\) s. For the DIM, the best tuning is the following: \(popsize=100\), \(\alpha=0.8\), \(\beta=0.1\), \(itmax=1000\), \(p_{c}=0.9\) and \(p_{m}=0.7\). ### Results

First, results of the FR heuristics TI Pulse and TI On/Off are presented in comparison with the best known solution (BKS) found (either ATI or [PERSON] et al. [12], which is shown in Table A8 in the Appendix A), then with the most efficient FR heuristic and the best and the average performance of the DIM among 10 runs. In Tables 7 and 8, each line represents an instance with its setting \(n\), \(\tau\), \(R\) and \(T\). Objective value, CPU time (s) and deviation from the BKS (%) are given for each approach. The last line presents the average performances across the benchmark. Figure 9: Influence of \(R\) on instance characteristics (with \(\tau\) fixed). \begin{table}
\begin{tabular}{c c c c c c c c c c c} \hline \hline  & & & & & \multicolumn{4}{c}{**FR TI Pulse**} & \multicolumn{4}{c}{**FR TI On/Off**} \\ \hline \multirow{2}{*}{_n_} & \multirow{2}{*}{\(\mathbf{\tau}\)} & \multirow{2}{*}{\(\mathbf{R}\)} & \multirow{2}{*}{\(\mathbf{T}\)} & \multirow{2}{*}{**BKS**} & \multirow{2}{*}



\begin{table}
\begin{tabular}{c c c c c c c c c c c c c c} \hline \hline  & & & & & \multicolumn{3}{c}{**FR TI Pulse**} & \multicolumn{3}{c}{**DIM Best**} & \multicolumn{3}{c}{**DIM Avg**} \\ \hline \multirow{2}{*}{\(n\)} & \multirow{2}{*}{\(\tau\)} & \multirow{2}{*}{\(R\)} & \multi



Table 7 displays a comparison between the BKS and the two FR heuristics. The FR Pulse heuristic obtains 2% deviation on average from the best solutions found by the models in [12; 13], with reasonable solving time. For small to medium instances, the heuristic finds solutions with 13% deviation on average. For large instances from \(n=50\) to 100, the heuristic finds better solutions than the exact approaches (10/45). This is particularly true on instances with \(\tau=0.1\) and \(R=0.1\). The FR Pulse heuristic is able to improve up to 91% of the objective. The FR TI On/Off heuristic has 22% deviation from the BKS with an average solving time of 30 s. On average, the solution founds are of lower quality for this heuristic compared to the TI Pulse. However, this heuristic can find solutions with less computational effort (10 times less). The FR TI On/Off finds better solutions than the exact approaches for 7 instances with \(n=50,100\) and specific \(\tau\) and \(R\) values. FR heuristics are better for small values of \(\tau\) on average. This is probably because the FR heuristic is guided by the accumulation of information in the OW to make selecting and sequencing decisions. When \(\tau=0.1\), orders are available from the beginning, therefore, the local choices (in the OW) better match the global choice and thus the optimal solution. If \(\tau\) is large, orders are available at different points of the horizon making the decision in the OW much more local. Consequently, the heuristic will possibly be led to make a succession of bad choices, without being able to backtrack. When \(\sigma\) is larger, FR heuristic benefits from more information to make decisions but it increases the computational effort. Table 8 displays a comparison between the BKS, the FR TI Pulse heuristic, and the best and average solution found by DIM. The DIM metaheuristic (best) obtains \(-14\%\) deviation on average from the BKS for a resolution time of 26 s on average.