# Redesigning the Wheel for Systematic Travelling Salesmen
## 1 Introduction  
The history of the travelling salesman problem (TSP) dates back to a book published in 1832 which mentioned optimal routes for the first time [1]. The first person who formulated this as a mathematical optimization problem was probably [PERSON] [2]. At a mathematical colloquium in Vienna in 1930, he talked about \"the task of finding the shortest path connecting the points for a finite number of points whose pairwise distances are known.\" This problem can be stated with following cost function to be minimized:  
\[J(\mathbf{\pi},(\mathbf{p}_{i}))=d(\mathbf{p}_{\mathbf{\pi}[i]},\mathbf{p}_{\mathbf{\pi}[ N-1]})+\sum_{i=0}^{N-2}d(\mathbf{p}_{\mathbf{\pi}[i]},\mathbf{p}_{\mathbf{\pi}[i+1]}) \rightarrow\text{Minimum}\, \tag{1}\]  
where the selection of points \(\mathbf{p}_{j}=(p_{x},p_{y})_{j}\) is decided based on a permutation vector \(\mathbf{\pi}\) of length \(N\) according to \(j=\mathbf{\pi}[i]\). The cost function \(J(\mathbf{\pi},(\mathbf{p}_{i}))\) is the sum of all Euclidean distances \(d(\mathbf{p}_{\mathbf{\pi}[i]},\mathbf{p}_{\mathbf{\pi}[i+1]})=||\mathbf{p}_{\mathbf{\pi}[ i+1]}-\mathbf{p}_{\mathbf{\pi}[i+1]}||\) between pairs of neighbouring points. A tour is usually modelled as a graph \(G=(V,E)\) with nodes from the set \(V\) (a.k.a. vertices) and edges from set \(E\), where the nodes correspond to points \(\mathbf{p}_{j}\) and the edges connect the points in pairs. The distance \(d(\mathbf{p}_{\mathbf{\pi}[i]},\mathbf{p}_{\mathbf{\pi}[i+1]})\) between two points corresponds to the length of the connecting edge. This optimization problem continues to attract many researchers to this day. Originally treated as a two-dimensional problem with symmetric distances as described above, several variants of the original problem have been formulated and studied up to the present. The methods to deal with the TSP can be divided into exact solvers, which provide the global optimum (i.e., the shortest possible tour), and heuristics trying to find a solution which is at least close to the optimum. The time needed to find the exact solution grows exponentially with the number of tour points (see, for instance, [3]). Implementations for exact solvers are freely available for academic use [4] (www.math.uwaterloo.ca/tsp/concorde/ (accessed on 7 December 2022)). [PERSON] and [PERSON] have created special instances that are difficult to solve with exact solvers [5]. In contrast, suboptimal solutions can be found in reasonable time by suitable heuristics. A state-of-the-art heuristic has been developed by [PERSON] [6] ([[http://webhotel4.ruc.dk/~keld/research/LKH-3/LKH-3.0.7.tgz](http://webhotel4.ruc.dk/~keld/research/LKH-3/LKH-3.0.7.tgz)]([http://webhotel4.ruc.dk/~keld/research/LKH-3/LKH-3.0.7.tgz](http://webhotel4.ruc.dk/~keld/research/LKH-3/LKH-3.0.7.tgz)) (accessed on 7 December 2022)). Equipped with various of tour-improvement tools, it has even been able to find optimal tours for instances up to 85 900 points. [PERSON] and [PERSON] independently proposed an algorithm that guarantees solutions within a factor of 1.5 of the optimal tour length (excess \(\leq 50\%\)) if the instance is symmetric and obeys the triangle inequality [7; 8]. In [9], it was theoretically proven that a (\(1+1/c\))-approximation can be obtained in \(N^{O(c)}\)-time. This work was extended by [10]. The most successful heuristics are based on the chained Lin-Kernigham method [11], which is one of the methods that try to optimize the entire tour by local improvements. It relies on the ideas of [12; 13] and applies sequences of typically only 2-opt and 3-opt permutations. A \(k\)-opt permutation intersects a tour of connected points at \(k\) locations, i.e., \(k\) edges are removed from the graph and \(k\) other edges are inserted, ideally shorter on average than the original edges. A tour is called \(k\)-optimal if no further improvements can be obtained by using \(m\)-opt permutations with \(2\leq m\leq k\). There are also studies including 4-opt and 5-opt [14].