# Which Local Search Operator Works Best for the Open-Loop TSP?
## 3 Performance of a Single Operator
### Search Strategy
The noise starts from \(r_{\max}\) = 1 and decreases at every iteration by a constant 2/\(T\), where \(T\) is the number of iterations. The noise reaches \(r\) = 0 halfway, and the search then reduces back to normal local search by using normal cost function (_f_) for the remaining iterations. We apply a random mixed local search with 25 repeats. Table 4 also shows simulated annealing results for O-Mopsi and Dots instances. Figure 25: Screenshots of 4 different dots instances (in the same order). Finding the productivity of the operators as in Figure 21 for random mixed local search, we consider finding out the same in case of tabu search and simulated annealing. From a random mixed local search, we found that link swap was the most effective operation. Figure 26 illustrates that in tabu search, link swap is the least effective. However, link swap is again the most effective for the simulated annealing, as shown in Figure 19:0 We mark the added links as forbidden for tabu search, so link swap becomes too restrictive in this case. This makes link swap often non-working. We compare the performance of random mixed local search, tabu search, and simulated annealing for O-Mopsi and dots games in Figure 19:1 We study the gap value and execution time for every method. Results show that neither tabu nor simulated annealing improved the performance of the random mixed local search algorithm. \begin{table}
\begin{tabular}{c c c c} \hline \hline  & & \multicolumn{2}{c}{**Repeated (25 times)**} \\ \cline{3-4}  & & **Gap (avg.)** & **Not Solved** \\ \hline \multirow{3}{*}{**O–Mopsi**} & Random mixed local search & 0\% & 0 \\  & Tabu search & 0\% & 0 \\  & Simulated annealing (SA) & 0\% & 0 \\ \hline \multirow{3}{*}{**Dots**} & Random mixed local search & 0.001\% & 1 \\  & Tabu search & 0.0003\% & 3 \\ \cline{1-1}  & SA & 0.007\% & 10 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Comparison of Tabu search and simulated annealing (SA) result with random mixed local search with the same iteration and repetition for O-Mopsi and dot instances. Figure 26: Share of improvement by all three methods for Tabu search. Figure 27: Share of improvement by all three methods for simulated annealing (SA). ## 6 Discussion

We have studied the open-loop variant of TSP to find out which operators work best. Two new operators were proposed: link swap and 3-permute. The link swap operator was shown to be the most productive. Even though 2-opt works best as a single operator, the best results are obtained using a mixture of all three operators (2-opt, relocate, link swap). The new operator, link swap, provides, 50% of all the improvements, while 2-opt and relocate have roughly a 25% share each. To sum up, the link swap operator is the most efficient operator in the mix. For our problem instances up to size 31, the proposed combination of the local search (random mixed local search) finds the optimum solution in all O-Mopsi instances, and in all except one, Dots problem instances. Iterations and repetitions are the most significant parameters of the proposed method. Additionally, a suitable number of iterations and repetitions are essential with respect to the problem size, which is \(2^{13}\) and \(2^{5}\) for the O-Mopsi dataset, and \(2^{15}\) and \(2^{6}\) for the Dots dataset. For O-Mopsi instances, processing times are 0.8 ms (single) and 16 ms (repeats). For Dots instances, processing times are 0.7 ms (single) and 16 ms (repeats). The overall complexity of the algorithm mainly depends on the number of iterations and repeats. Furthermore, considering the multi-threaded platform, different repeats can work simultaneously to decrease the processing time by a factor of a number of threads. Tabu search and simulated annealing were also considered but they did not provide further improvements in our tests. The productivity of the operators was consistent with those of the local search.