## 5 Computational Results
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline \multirow{2}{*}{
\begin{tabular}{c} **Input** \\ **instance** \\ \end{tabular} } & \multicolumn{2}{c}{**Published algorithm**} & \multicolumn{3}{c}{**Proposed algorithm**} \\ \cline{2-6}  & \multicolumn{1}{c}{**Fitness**} & \multicolumn{1}{c}{**Execution**} & \multicolumn{1}{c}{**Fitness**} & \multicolumn{1}{c}{**Execution**} \\  & \multicolumn{1}{c}{**value**} & \multicolumn{1}{c}{**time**} & \multicolumn{1}{c}{**value**} & \multicolumn{1}{c}{**time**} \\ \hline Valouvis-1 & Integer linear programming approach [32] & 160 & 15 min & **20** & 17.64 s \\ BCV3-46.2 & A shift sequence based approach with greedy & 3601 & 3 min, 4 s & **894** & 16 min \\  & local search and adaptive ordering [34] & 199 & 28.3 s & **175** & 0.12 s \\ MUSA & Single phase goal programming model [36] & 510 & 1 min, 36 s & **301** & 0.3 s \\ LLR & Two-phase hybrid approach [33] & 18 & 10 s & **100** & 3 s \\ BCV4-13.1 & A shift sequence based approach with greedy & 18 & 10 s & **100** & 3 s \\  & local search without adaptive ordering [34] & 5 & Not mentioned & 5 & 9.1 s \\ WHPP & Linear programming formulation using & 5 & Not mentioned & **129** & 29.1 s \\  & column generation approach [37] & 517 & Not mentioned & **129** & 29.1 s \\ HED01 & Genetic algorithm [35] & 517 & Not mentioned & **129** & 29.1 s \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Comparing the best timetables constructed by the proposed algorithm with the best timetables created in [32, 33, 34, 35, 36, 37]. The superiority of the proposed algorithm compared to other approaches comes mainly from the fact that the algorithm succeeds in searching the search space using a new variable neighborhood search approach. In the literature, there are three commonly used swaps, that is, simple move, simple swap and Kempe swap, each one of them leading to a search algorithm to investigate a different neighborhood [23]. The proposed algorithm uses only simple swaps, that is, swaps between cells without considering what these cells contain in order to perform the swap (_i.e._, whether they are empty or not). However, each one of the three swap procedures used by the proposed algorithm (see Sections 3.2, 3.3.1, 3.3.2) applies a different swap mechanism, which leads the algorithm to search in a different neighborhood of the search space. The application of the proposed mutation operators that implement the algorithm's swapping mechanisms, applied in this specific way and order, is innovative to our knowledge and different from the swapping mechanisms already investigated in [13]. The strongest point of this variable neighborhood search approach is the combination of a classic neighborhood search with a \"stochastic moving segment grouping swap\" (see Subsection 3.2). The \"stochastic moving segment grouping swap\" achieves exhaustive local search, since the segment is not stable, and as a result, it ensures intensification. On the other hand, since this swap is a stochastic one, it ensures diversification. To conclude, combining and applying these three swap procedures (see Sections 3.2, 3.3.1, 3.3.2) enriches the variable neighborhood search approach, since it enhances the classic neighborhood search with a \"stochastic moving segment grouping swap\". This combination ensures both intensification and diversification of the search space. Since the nature of the proposed two-phase algorithm is stochastic, different computational results may be obtained in different runs. So, in order to demonstrate its efficiency, in Table 4, we present not only the best, but also the worst and the average results (and the respective standard deviations--STDs), considering the fitness function value achieved and the execution time of the algorithm. Additionally, we present the respective coefficient of variation (CV) and the success rate for each input instance. All results presented in Table 4 concern the execution of the proposed algorithm to the seven aforementioned nurse rostering input instances for 100 Monte Carlo runs.