# Redesigning the Wheel for Systematic Travelling Salesmen
## 1 Introduction
Such \(k\)-opt permutations steer the solution to a minimum, which is typically not the global one. [PERSON] gave a concise tour of the subject in [15]. In addition to the classical TSP, optimization problems with special constraints have also been studied, such as the vehicle-routing problem, in which not only the distances between points count, but also time constraints and multiple agents with varying capacities have to be considered [16; 17]. A comprehensive overview is given in [18]. Time-dependent TSPs were investigated by [19; 20], wherein the costs depend not only on the distances between points but are also a function of the position within the tour. A generalized TSP was presented in [21], wherein points are clustered and the tour to be optimized consist of exactly one point of each cluster. This problem was addressed with a genetic algorithm. Several applications of clustered TSPs were discussed in [22]. Time constraints have also been an issue recently in solving TSPs with constraint programming [23]. The authors of [24] proposed a technique allowing permutations that do not directly lead to a shorter tour and thus can avoid getting stuck in local minima. It can compete with the Lin-Kernigham-Helsgaun (LKH, [6]) method for difficult problems when starting from a random tour i.e., without creating an initial tour. As already pointed out above, the local optimisation by \(k\)-opt permutations and similar operations runs the risk of getting stuck in a local minimum. There are different strategies to overcome this problem. In [25], for example, a \"breakout local search\" was proposed to jump from one local minimum to the next and hopefully better local minimum, which of course requires several attempts. A very successful recombination technique initially generates many suboptimal tours converging at different local minima (see for example [26; 27]). In [26], this is described as \"principle of backbone edges\". These are connections between points that are present in all quickly solved tours. The entire tour can then be collapsed into a smaller tour that considers only the remaining missing connections, whereas a path of backbone edges is taken into account as a single edge. A comparison of techniques can be found in [28] and the literature cited therein. These ideas of combining information from different trials are closely related to so-called \"ant colony optimization\" methods whereby the decision-making mimics the use of pheromone trails of ants. Recent developments and relevant citations can be found in [29]. However, such recombination techniques and other metaheuristics are not practical for very large instances with more than one million points, because even finding the first local minimum can be very time consuming. Many proposed heuristics only deal with small or medium-sized instances [30; 31; 32; 33; 34; 35; 36; 37; 38], whereas in [39] problems with even billions of cities are tackled. In the last decade, heuristics based on the idea of swarm intelligence like ant colonization and others have been become quite popular [33; 35; 37; 38; 39; 40; 29]. However, so far they cannot really compete with state-of-the-art methods like LKH when applied to classical TSP problems. The processing of large instances can be accelerated by decomposing the tour into shorter subtours which remain connected by using fixed edges [41; 42]. This could be combined by using multiple threads and parallel processing on multicore processors [29; 42] or by taking advantage of graphical processing units [43]. The method described in this paper draws on many ideas proposed by various researchers and combines them with new ideas. It aims at optimizing very large instances (up to 10 million points, symmetric Euclidean two-dimensional distances) in a single pass in limited time. To achieve this goal, various techniques are implemented to speed up the processing. The vast number of possible permutations is reduced by a suitable candidate selection based on Delaunay triangulation [44].