# Which Local Search Operator Works Best for the Open-Loop TSP?
## 3 Performance of a Single Operator
### Search Strategy
However, instead of fixing the operator beforehand, we choose it randomly at every iteration. The pseudocode of the mixed variant is demonstrated in Algorithm 3. This random mixing solves all instances with having a 0% gap if we repeat the process for 25 times. ```
RandomMixing( NumberOftteration, Path ) FOR i \(\leftarrow\) 1 TO NumberOfIteration DO operation \(\leftarrow\)Random( NodeSwap, 2 opt, LinkSwap ) NewPath \(\leftarrow\)NewRandomSolution( Path, operation ) IF Length ( NewPath) \(<\)Length ( Path ) THEN Path \(\leftarrow\) NewPath RETURN Path
```

**Algorithm 3**Finding a solution by mixing local search operators

[PERSON] et al. [43] stated that local search algorithms get trapped in sub-optimal points. Here, we find that the operators, even when mixed, could not solve all the instances from any random initial solution. Figure 14 shows three examples where the search was stuck to a local optimum from where none of

Figure 13: A single operator can re-work after being stuck with the help of other operators’ improvement. the operators can process further. In these cases, the repeated random mixed local search was needed to solve these instances. ## 4 Analysis of Repeated Random Mixed Local Search

We next analyze the performance of the repeated local search in more detail. We use both the 145 O-Mopsi instances and the larger Dots dataset, which contains 4226 computer-generated TSP instances. Here problem size varies from 4 to 31. ### Effect of the repetitions

Figure 15 reports how many of the instances are solved when we increase the number of repeats. In the case of O-Mopsi, most instances (144) are solved already with 15 repeats, and all with 25 repeats. The results with the Dots instances are similar: 15-25 iterations are reasonably good, after which only 100 instances were not solved optimally. After 150 repeats, only one instance remains unsolved. Figure 16 demonstrates the effect of repetition for a single (typical) instance as the average path length. We portray all improving steps from a random start in the first run. There is a similar kind of improving steps from different random starts in the consecutive runs. However, we only show more improved steps than the previous run. Thus, we can see there are very few better steps in higher runs, and three or four repeated runs are usually enough to achieve the optimum result. The gap values

Figure 14: Examples of local optima. Repeats overcome these. Figure 15: Instances solved as a function of the number of repetitions. are also shown to demonstrate the closeness of our outcomes to the optimum result. In the first run, we usually achieve a result that is already very close to the optimum. The repetitions push the result to the global optimum, but they act merely as a fine tuner for the results. If we can settle the sub-optimal result very close to the global optimum, then a local search with only a few repeats would be sufficient for these datasets. Next, we evaluate the total work based on the number of iterations and the number of repeats. We plot four different curves with random start repeated 1, 5, 15, and 25 times for the O-Mopsi instances. Figure 17 shows how close the path length becomes to the optimum during 10,000 iterations. A similar plot is also drawn for the Dots instances with 1, 5, 15, 25, 50, 100, and 150 repeats. All the curves coincide on each other so they appear as only one line in Figure 17.

Figure 16: Typical example of the effect of repetition. Figure 17: Total amount of work. ### Processing Time

The time complexity of the method can be analyzed as follows. At each iteration, the algorithm tries to find improvement by a random local change. The effect of this change is tested in constant time. Only when improvement is found, the solution is updated accordingly, which takes O(N) time. Let us assume probability \(p\) for finding an improvement. The time complexity is, therefore, O(IR + pNIR), where I and R are the number of iterations and repetitions, respectively.