# Which Local Search Operator Works Best for the Open-Loop TSP?
A significant amount of research developed different tour construction algorithms, such as the savings algorithm by Reference ([PERSON] _et al._, 2012), polynomial-time 3/2 approximation algorithm by Reference ([PERSON] _et al._, 2012), insertion ([PERSON] _et al._, 2012), greedy ([PERSON] _et al._, 2012), and the nearest neighbor algorithm ([PERSON] _et al._, 2012). Among these, we use the greedy algorithm and a random arrangement for the tour construction. Being an iterative process, the tour improvement step modifies the initial solution with a small improvement in each iteration. The key component in the local search is the choice of the operator, which defines how the current solution is modified to generate new candidate solutions. Most used operators are 2-opt ([PERSON] _et al._, 2012) and its generalized variant, called k-opt ([PERSON] _et al._, 2012), which is empirically the most effective local search algorithm for large TSPs ([PERSON] _et al._, 2013). [PERSON] et al. [PERSON] _et al._ (2013) analyzed the combination of 2-opt with different well-known construction heuristics. Several researchers studied local search for TSP and different optimization problems ([PERSON] _et al._, 2016; [PERSON] _et al._, 2012; [PERSON] _et al._, 2012; [PERSON] _et al._, 2012; [PERSON] _et al._, 2012; [PERSON] _et al._, 2012; [PERSON] _et al._, 2012; [PERSON] _et al._, 2012), even for vehicle routing application ([PERSON] _et al._, 2012; [PERSON] _et al._, 2012). Although existing studies have analyzed the local search algorithms extensively, it is still not known which operators are effective for open-loop cases. Besides this, the existing literature mainly presents optimization results of algorithms instead of providing a detailed study on different operators. As operators are the backbone of the local search algorithms, we need a detailed study on them to know how to increase the productivity of the algorithm and how to avoid the local minima. In this paper, we study several operators and their combinations in the context of local search. We aim at answering which of them works best in terms of the quality and efficiency. We consider four operations, of which two are existing and two are new:  
* [noitemsep,topsep=0 pt]
* Relocate (Relocate, 1990)
* 2-opt ([PERSON] _et al._, 2012)
* 3-permutation (new)
* Link swap (new)  
Between the new two operators, the former also applies to the more common closed-loop TSP, but the second is specifically tailored for the open-loop problem. We also propose an algorithm to achieve a global minimum in most problem instances of size up to 31, preferably in real-time. We study the performance of these operators when applied separately, and when mixed. We consider _random_, _best improvement_, and _first improvement_ search strategies. We first report how successful the operators are in equal conditions, and whether the choice of the best operator changes towards the end of the iterations. We study two initialization techniques: _random_ and _heuristic_, and the effect of re-starting the search. Results are reported for two open-loop datasets (O-Mopsi, Dots), see Table 1. The O-Mopsi dataset contains real-world TSP instances and the Dots dataset is a computer-generated random dataset for an experimental computer game. Since it is an outdoor dataset, generating the former one is relatively difficult. Therefore, the available number of instances are much lower than Dots. However, both datasets need real-time reference solutions. The rest of the paper is organized as follows. In Section 2, we describe the local search operators we use in this study. We define these operators with illustrations and study their abilities to produce unique improved solutions. In Section 3, we provide results of the tests carried on with these operators on Table 1 datasets. Based on these results, we introduce a new method to solve open-loop TSPs in this section. In Section 4, we evaluate the quality and efficiency of our proposed algorithm. In Section 5,we test stochastic variants, aiming to improve our algorithm.