# Which Local Search Operator Works Best for the Open-Loop TSP?
## 3 Performance of a Single Operator
### Search Strategy  
For the search strategy we consider the following three choices:  
* Best improvement
* First improvement
* Random search  
Figure 11: Three neighboring solutions created by link swap, of which the one connecting the terminal nodes is unique. Best improvement studies the entire neighborhood and selects the best one among all solutions. This can be impractical, especially if the neighborhood is large. The first improvement studies the neighborhood only until it founds any solution that provides improvement. It can be more practical as it moves on with the search quicker. Random search studies the neighbors in random order, and similar to the first improvements, accepts any new solution that improves. We also consider repeated (multi-start) local search, which simply re-starts the search from scratch several times. This helps if the search is susceptible to getting stuck into a local minimum [39]. Moreover, every repeat is essentially a random attempt to converge to a local optimum; parallelization can be applied by running different repeats on different execution threads. [PERSON] & [PERSON] [40] and [PERSON] et al. [41] preferred repeated local search, for [PERSON] and [PERSON] et al. [42] for matrix multiplication to overcome local optima. A pseudocode that covers all the search variants with all the operators is given in Algorithm 2. The only parameter is the number of iterations for which the search continues. First and best improvement searches can also be terminated when the entire neighborhood is searched without further improvement. This corresponds to the hill-climbing strategy. ```
LocalSearch(InitialPath,OperationType) Path \(\leftarrow\) InitialPath SWITCH SearchType CASE RANDOM FOR i \(\leftarrow\) 1 TO Iterations DO NewPath \(\leftarrow\) NewRandomSolution(Path, OperationType ) IF Length ( NewPath ) \(<\)Length ( Path ) THEN Path \(\leftarrow\) NewPath CASE FIRST Path \(\leftarrow\)NewFirstSolution(Path ) CASE BEST Path \(\leftarrow\)NewBestSolution(Path ) RETURN Path _NewRandomSolution_(Path, OperationType ) SWITCH OperationType CASE RELOCATE Target \(\leftarrow\)Random(1,N) Destination \(\leftarrow\)Random(1,N) NewPath \(\leftarrow\)relocate(Path, Target, Destination ) CASE 2 OPT FirstLink \(\leftarrow\)Random(1,N) SecondLink \(\leftarrow\)Random(1,N) NewPath \(\leftarrow\)2 Opt(Path, FirstLink, SecondLink ) CASE LINKSWAP Link \(\leftarrow\)Random(1,N) NewPath \(\leftarrow\)linkSwap(Path, Link ) RETURN NewPath _NewFirstSolution_(Path, OperationType ) FOR i \(\leftarrow\) 1 TO N DO FOR j \(\leftarrow\) 1 TO N DO SWITCH OperationType CASE RELOCATE NewPath \(\leftarrow\)relocate(Path,i,j) CASE 2 OPT NewPath \(\leftarrow\)2 Opt(Path,i,j)

### Results With A Single Operator

We first study how close the operators can improve paths to the optimum solutions using O-Mopsi and Dots datasets. Optimum paths were computed by branch-and-bound. Two results are reported:

* Gap (%)
* Instances solved (%)

The gap is the length of the optimum path divided by the length of the tour found by the local search (0% indicates optimum). The second result is the number of instances for which an optimum solution is found by the local search. We also express it in a percentage value, which indicates 100% means that the method finds the optimum solutions for all instances. We execute every operator individually with all search strategies on all O-Mopsi game instances. Repeated search is applied only for the random search with random initialization. We combine the results of O-Mopsi and Dots datasets and report those in Table 2. In the table, we first write the gap values, and the percentage values of solved instances are written inside the parentheses. The 2-opt is the best individual operator. It reaches a 2% gap and solves 57% of all instances when starts from a random initialization, and 0.8% (73% instances) using the heuristic initialization. The repeats are important. With 25 repeats, the 2-opt solves 97% of all instances, and the mean gap is almost 0%.