# Which Local Search Operator Works Best for the Open-Loop TSP?
## 3 Performance of a Single Operator
### Search Strategy
The value for \(p\) is higher at the beginning, when the configuration is close to random and gradually decreases to zero when approaching to a saturation point (the solution that cannot be improved by any local operation). In our observations, \(p\) is small (0.002 on average for O-Mopsi and even lesser for Dots), so the time complexity reduces to O(IR), in practice. This means that the speed of the algorithm is almost independent on the problem size (see Figure 18). In contrast, optimal solvers such as Concorde [17] have exponential time complexity. We are unable to find a complexity analysis for Concorde in literature, however, we estimate it empirically by analyzing the running time required by Concorde to solve TSPLIB [44] instances. From the website ([[http://www.math.uwaterloo.ca/tsp/concorde/benchmarks/bench99.html](http://www.math.uwaterloo.ca/tsp/concorde/benchmarks/bench99.html)]([http://www.math.uwaterloo.ca/tsp/concorde/benchmarks/bench99.html](http://www.math.uwaterloo.ca/tsp/concorde/benchmarks/bench99.html))), we choose 105 instances with increasing problem sizes (\(N\) between 14 and 13509) and analyze the trend. According to this, Concorde has a complexity of (1.5e'(0.004\(N\))). This implies that for small instances (up to several thousands) the algorithm is expected to be fast. However, the analysis also reveals that some points highly deviate from the expected line. This implies that some instances are more difficult to solve (with a higher number of nodes in the search tree) and require more time, such as the instance (d1291), with 1291 targets, which has almost 8 hours of running time where another instance (rl1304) with 1304 targets has only 22 minutes of running time. In comparison to that, Random Mix finishes more predictably. Considering the repeats, we summarized the result in Table 3, which shows that a single run takes 0.8 ms and 25 repeats take 16 ms on an average, regardless of the dataset. ### Parameter Values

We investigate different values for the I and R parameters using grid-search and recorded how many operations are needed to solve different sized problems. The results are summarized in Figure 19. In this context, we want to mention, as there are not a sufficient number of samples with more than 25 targets in the O-Mopsi dataset and 30 targets in the Dots dataset, we ignore those samples. From the

Figure 18: Run time as a function of problem size. \begin{table}
\begin{tabular}{c c c} \hline \hline  & **Single Run** & **25 Repeats** \\ \hline O–Mopsi & 0.8 ms & 16 ms \\ Dots & 0.7 ms & 16 ms \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Running time. chart, we can conclude that proper parameter values to use for the O-Mopsi dataset are I = 2\({}^{13}\) and R = 2\({}^{5}\). The dots dataset requires higher values of I = 2\({}^{15}\) and R = 2\({}^{6}\). The relationship between I and R seems to stabilize for larger instances. In Figure 20, we fix the product IR to 2\({}^{18}\) (O-Mopsi) and 2\({}^{21}\) (Dots) and vary their individual values. Typically, different same-product combinations are equally effective at solving the instances. However, using too few repetitions, the algorithm typically gets stuck at a local optimum, which is not the global one. On the other hand, when the number of iterations becomes too small, it is likely that some local operations can still improve the result (not saturated). ### The Productivity of the Operators

We next analyze the productivity of the operators, as follows. We count how many times each operator found an improvement in the solution. For this case, we also evaluate our operators by closed-loop instances (TSPLIB instances) [44]. We should mention here that closed-loop instances do not contain single links to swap. Therefore, the link swap operation is not possible for them. We can only use the relocate and 2-opt operators to solve TSPLIB problems. In this context, we want to mention that we choose 12 TSPLIB instances to test with problem size of 52-3795.