# Redesigning the Wheel for Systematic Travelling Salesmen
## 2 Methods
### Local Optimization Using \(k\)-Opt Permutations
#### 2.4.4 Optimization with 6-Opt Permutations
To satisfy this condition, the author proposes to complement the set of points with a virtual point that is connected to both endpoints and is positioned at \((x,y)=(\infty,\infty)\). Let us take a look at the example tour in Figure 5(a). It consists of an arbitrary large set of points, from which seven points (\(0\;1\;2\;3\;4\cdots 14\;15\)) are drawn. The edges are annotated with the distances between the points and the total tour length is currently \(len=8+5+4+3+r+3+10=r+33\). Using a 2-opt permutation which arranges P and Pc as direct neighbours, the order of points can be changed to (\(0\;2\;1\;3\;4\cdots 14\;15\)) and the tour length decreases to \(len=5+5+3+3+r+3+10=r+29\). Assuming that the points 1 and 15 are the endpoints of a subtour, the permutation discussed would be forbidden, because point 1 is now hidden between points 2 and 3. In Figure 5(b), the point 0 is considered a virtual point augmenting the subtour from point 1 to point 15. The location of this virtual point is purposively defined as \((x,y)=(\infty,\infty)\). The distances to all other points automatically become infinite. The discussed permutation is no longer possible because it would substitute two edges (0-1 and 2-3) of common length \(\infty+4\) by two new edges (0-2 and 1-3) with a joint length of \(\infty+3\). Both lengths are infinite and this permutation is not considered as an improvement. In other words, the edges between the virtual point and the two endpoints remain untouched. After the subtour is optimized, the virtual point is removed and the endpoints can be reconnected with the endpoints of the adjacent subtours. Nevertheless, it is still possible to make P and Pc neighbours by replacing edges (1-2 and 3-4) with common length \(5+3=8\) by two new edges (1-3 and 2-4) with a joint length of \(3+4=7\). The new order would be \((0\;1\;3\;2\;4\cdots 14\;15)\). #### 2.5.2 Multithreading

Having discussed how to handle subtours without changing their endpoints, now their integration into the global optimization will be described. The complete algorithm is shown in Listing 3. Depending on the number \(N_{\text{jobs}}\) of jobs to be executed in parallel, the number \(N_{\text{s}}\) of points per segment is derived from the total number \(N\) of points. The last segment is slightly shorter if \(\text{modulo}(N,N_{\text{jobs}})\
eq 0\) (line 20). All \(N_{\text{jobs}}\) segments are independently optimized by using a virtual point as described

Figure 6: Example with virtual point explaining subtour optimization: (a) closed-loop tour; (b) open-loop subtour with virtual point at infinite location. Black, grey, and dashed lines show current edges, possible edges after permutation, and arbitrary sequence of points, respectively. See text for further details. above (lines 16-38). After execution, the modified order of points has to be mapped back to the global permutation vector (line 39). Obviously, for each subtour, separate candidate sets have to be determined, which do not contain any relations between subtours. This represents some computational overhead. The establishment of edges between different subtours is only possible if the segmentation of the entire tour is varied. For this reason, the segment borders are shifted by 10% of the segment length in each round (line 23). As this exchange between subtours is essential for finding best neighbours for all points, the subtours are not fully optimized but a single loop is performed over all points P.

In the first round, all jobs commonly start with 2-opt operations only. After a round is completed, a check is made to see if the next \(k\)-opt mode has been activated in at least one of the jobs. If so, this mode is also enabled for all other jobs in next round. The main reason for using a common mode is to maximize the utilization of all CPU cores, which is achieved when all jobs take approximately the same time. As an example, consider a vector of 10 points, the current order of which is given by \(\pi=(4\;2\;1\;9\;7\;8\;6\;5\;0\;3)\).