# Which Local Search Operator Works Best for the Open-Loop TSP?
## 3 Performance of a Single Operator
### Search Strategy
The better initialization provides significant improvement in all cases, which indicates the search gets stuck into a local minimum. The choice of the search strategy, however, has only minor influence. We, therefore, consider only the random search in further experiments. ### Combining the Operators

Our primary goal was to find an optimum solution for all game instances. The best combination (2-opt with a random search using 25 repeats) missed it for only 3% of instances. Nevertheless, these are relatively easy instances; therefore, they should all be solvable by the local search. We, therefore, consider combining different operators. We do this by applying a single run of the local search with one operator, and then continue the search with another operator. We consider all pairs and the subsequent combinations of all three operators. We tested all combinations but report only the results of 25 repeats using the random improvement (random initialization). From the results in Table 2, we can see that all combinations manage to solve a minimum of 97% of all instances and have a gap of 0.032% or less. The mixed variant with the order (2-opt + relocate + link swap) found the optimum solution for 99% cases. In this case, 2-opt solves already a 97% of all instances, then the consecutive relocate makes it 98%, and finally link swap makes it 99%. This shows that the operators have complementary search spaces; when one operator stops progressing, another one can still improve further. Examples are shown in Figure 12. \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline  & & \multicolumn{3}{c}{**Single Operator**} & \multicolumn{3}{c}{**Double Operators**} & \multicolumn{3}{c}{**Mix of Three**} \\ \cline{3-8}
**Initialization** & **Random** & **Heuristic** & \begin{tabular}{c} **Repeated** \\ **(25 times)** \\ \end{tabular} & \
\begin{tabular}{c} **Repeated \\ **(25 times)** \\ \end{tabular} &
\begin{tabular}{c} **Repeated (25 times)** \\ **Operator** \\ \end{tabular} & \multicolumn{3}{c}{**Repeated (25 times)**} \\ \hline \multirow{4}{*}{Relocate} & First & 7\% (30\%) & 1.0\% (70\%) & - & - & - & - & - \\  & Best & 6\% (34\%) & 0.9\% (72\%) & - & - & - & - & - \\  & Random & 6\% (34\%) & 0.9\% (71\%) & 0.18\% & - & 0.007\% & 0.032\% & 0.010\% & 0.005\% \\  & Random & 6\% (34\%) & 0.9\% (71\%) & (90\%) & - & (98\%) & (97\%) & (98\%) & (99.7\%) \\ \hline \multirow{2}{*}{2-opt} & First & 2\% (54\%) & 1.0\% (70\%) & - & - & - & - & - & - \\  & Best & 2\% (57\%) & 0.8\% (73\%) & - & - & - & - & - & - \\  & Random & 2\% (52\%) & 0.8\% (73\%) & 0.02\% & 0.009\% & - & 0.018\% & 0.005\% & 0.005\% \\  & Random & 2\% (52\%) & 0.8\% (73\%) & (97\%) & (98\%) & - & (97\%) & (99\%) & (99.7\%) \\ \hline Link swap & Best & 44\% (5\%) & 2.9 (59\%) & - & - & - & - & - & - \\  & Random & 11\% (31\%) & 3.0 (58\%) & 1.00\% & 0.019\% & 0.010\% & - & 0.006\% & 0.005\% \\  & & (77\%) & (98\%) & (97\%) & (99\%) & (99\%) & (99.7\%) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Combined results of single and subsequent application of random improvement with different operators averaged over O-Mopsi and Dots instances. The percentage of solved instances are shown inside the parenthesis. The number of iterations was fixed to 10000 for randomized search, whereas first and best improvements were iterated until convergence. Figure 12: Operators have complementary search spaces. After being stopped, it is also possible that a single operator can start to work again when other operators make some improvement in the meantime. Hence, these works of other operators make the first operator alive again. Figure 13 has three such examples, where the first operator entraps into a local optimum. Then, other operators recover the process from the local optimum and improvement continues. Again, the first operator starts working later. In addition, we consider also mixing the operators randomly as follows. We perform only a single run of the local search for 10,000 iterations.