# Which Local Search Operator Works Best for the Open-Loop TSP? [PERSON]  
1 Machine Learning Group, School of Computing, University of Eastern Finland, 80101 Joensuu, Finland; [EMAIL_ADDRESS] (R.M.-I. ); [EMAIL_ADDRESS] (P.F. )1 Machine Learning Group, School of Computing, University of Eastern Finland, 80101 Joensuu, Finland; radum@cs. In O-Mopsi, players are not required to solve the optimum tour, but finding a good tour is still an essential part of the game. Experiments showed that, among the players who completed a game, only 14% had found the optimum tour, even if the number of targets was about 10, on average [3]. The optimum tour is still needed for reference when analyzing the performance of the players. This is usually made as a post-game analysis but can also happen during real-time play. A comparison can be made with the tour length or with the visiting order. The game creator also needs an estimator for the tour length, as it will be published as a part of the game info. If the game is created automatically on the demand, TSP must be solved real-time. The optimality is highly desired, but can sometimes be compromised for the sake of fast processing. The number of targets in the current O-Mopsi instances varies from 4 to 27, but larger instances may appear. For the smaller instances, the relatively simple branch-and-bound algorithm is fast enough to produce the optimum tour. However, for the longer instances, it might take from minutes to hours. Along with the exact solver, a faster heuristic algorithm is therefore needed to find the solution more quickly, in spite of the danger of occasionally resulting in a sub-optimal solution. Besides O-Mopsi, TSP arises in route planning [6], orienteering problems [7], and automated map generation [8]. An example of O-Mopsi play is shown in Figure 2, with a comparison to the optimum tour (reference). For analyzing, we calculate several reference tours: _optimum_, _fixed-start_, and _dynamic_. The optimum tour takes into account the fact that the players can freely choose their starting point. Since selecting the best starting point is challenging [9], we also calculate two alternative reference tours from the location where the player started. Fixed-start is the optimum tour using this starting point. The dynamic tour follows the player's choices from the starting point but re-calculates the new optimum every time the player deviates from optimum path. Three different evaluation measures are obtained using these three tours: _gap_, _mismatches_, and _mistakes_; see [10]. Figure 1: Difference between open- and closed-loop traveling salesman problem (TSP). Figure 2: Examples of [PERSON]–Mopsi playing (left), the final tour (middle) and comparison to optimum tour (right). Being NP-hard, exact solvers of TSPs are time-consuming. Despite the huge time consumption, exact solvers were prime attractions to researchers in earlier days. [PERSON], [PERSON], and [PERSON] [PERSON] _et al._ (2011), [PERSON] and [PERSON] [PERSON] and [PERSON] (2012), [PERSON] and [PERSON] [PERSON] and [PERSON] (2013), [PERSON] and [PERSON] _et al._ (2014), [PERSON] et al. [PERSON] _et al._ (2015), and others developed different algorithms to produce exact solutions. [PERSON] _et al._ (2016) surveyed exact algorithms for TSP. By the year 2006, the Concorde solver solved a TSP instance with 85900 cities ([PERSON] _et al._, 2017). Along with these, different heuristic algorithms have been developed to find very fast near-optimal solutions. The local search is one of the most common heuristics to produce near-optimum results ([PERSON] and [PERSON], 2012). It has two parts: tour construction and tour improvement. The tour construction generates an initial solution that can be far beyond the optimum.