# Which Local Search Operator Works Best for the Open-Loop TSP?
## 3 Performance of a Single Operator
### Search Strategy
These instances are significantly larger than O-Mopsi and Dots instances, and therefore, we used a much higher number of iterations (10\({}^{8}\)) and 25 repeats. The total distribution of the improvement achieved by operators is shown in Figure 21 both for the open-loop (O-Mopsi and Dot games) and closed-loop (TSPLIB) [44] cases. From the results, we can make the following observations. Figure 19: Required number of operations increases with problem size. Figure 20: Gap variation with varied iterations and repetitions. First, we can see that the 2-opt and relocate are almost equally productive in all cases. However, the situation changes dramatically from the closed-loop to the open-loop case. While 2-opt and relocate both have about a 50% share of all improvements in the closed-loop case (TSPLIB), they are inferior to the new link swap operator in case of open-loop test sets (O-Mopsi and Dots). The link swap operator dominates by a 50% share, while 2-opt and relocate have roughly a 25% share each. The relocate operator becomes also slightly more productive than 2-opt. One question is whether all operators work equally efficiently at the beginning of the search, when there is more room for improvements, as they do at the end of the search when the improvements are harder to find. We select four typical O-Mopsi game examples and find the productivity of the operators through the total search spaces (Figure 22). We plot them in Figure 23. Similarly, Figure 24 shows the productivity of operators along the search spaces of four typical dot games. We plot those games in Figure 25. The diagrams show that there are no visible patterns to be observed. All operators remain productive at all stages of the search. Link swap is the most active and relocate is slightly more productive at the end of the search with the O-Mopsi instances. Figure 21: Share of the improvements by all three operators both with the open-loop (O–Mopsi and Dot games) and closed-loop (TSPLIB) problem instances. With TSBPLIB, we use \(10^{8}\) iterations and 25 repeats. Figure 22: Productivity of the operators during the search with for 4 different O–Mopsi instances. Figure 23: Screenshots of the 4 different O–Mopsi instances (in the same order). Figure 24: Productivity of the operators during the search with for 4 different Dots instances. ## 5 Stochastic Variants

We consider repeat to overcome the local optimum values. However, there are several other methods to overcome local optimum values using tabu search [45], simple simulated annealing and combined variants [46; 47; 48; 49; 50], genetic algorithm [51; 52; 53; 54]. Besides these, [PERSON] et al. [55] combined iterated local search and Monte Carlo simulation on vehicle routing problems. We compared our results with some of these methods; additionally, we consider two stochastic variants of the local search:

* Tabu search [45]
* Simulated annealing [47]

Tabu search is a metaheuristic first introduced by [PERSON] [45]. The idea is to allow uphill moves that worsen the solution to avoid being stuck in a local optimum. It forces the search to new directions. A tabu list of previously considered solutions, or moves, is maintained to prevent the search from going into cycles around the local optima. We incorporate the tabu search with our local search as follows. When an improvement is found in the solution, we mark the added links as tabu. These links are not allowed to be changed in the next 0.2\(\cdot N\) iterations. We use the best improvement as the search strategy. Table 4 shows results of tabu search for O-Mopsi and Dots games. Simulated annealing (SA) is another approach to make the search stochastic. Although there are a large number of adaptive simulated annealing variants, we consider a simpler one, the noising method of [PERSON] and [PERSON] [47]. The idea is to add random noise to the cost function to allow uphill moves and therefore avoid local optima. The noise is a random number between \(r\in[0,\pm r_{\max}]\), and acts as a multiplier for the noisy cost function: \(f_{\rm noise}\) = _rf_.