# Redesigning the Wheel for Systematic Travelling Salesmen
## 2 Methods
### Initial Tour Generation
#### 2.3.2 Double Local Optimization with Recursion (DoLoWire)  
In [42], a more sophisticated approach called \"double local optimization with recursion\" had been proposed which reduces the algorithmic complexity via clustering of points. Based on these clusters, first a coarse tour is generated that connects the cluster centroids. This coarse tour contains about 1500 points at default settings and defines the order of the clusters. In case a cluster contains too many points with respect to a threshold, the procedure  
\begin{table}
\begin{tabular}{|r|r|r|r|r|r|r|} \hline  & & \multicolumn{3}{c|}{GrebCap} & \multicolumn{2}{c|}{DoLoWire} \\  & best known & original set & \multicolumn{2}{c|}{enriched + merged} & & \\ instance & tour length & excess [\%] & time [s] & excess [\%] & time [s] & excess [\%] & time [s] \\ \hline rat99 & 1 211 & 25.67 & 0 & 24.10 & 0 & **2.73** & 0 \\ gil262 & 2 378 & 29.55 & 0 & 21.32 & 0 & **6.31** & 0 \\ d1291 & 50 801 & 23.11 & 0 & 20.72 & 0 & **10.69** & 1 \\ u2152 & 64 253 & 23.89 & 0 & 16.86 & 0 & **11.48** & 14 \\ pr2392 & 378 032 & 19.66 & 0 & 17.64 & 0 & **7.89** & 14 \\ fnl4461 & 182 566 & 20.46 & 0 & 18.37 & 0 & **13.33** & 12 \\ ch71009 & 4 566 506 & 21.72 & 0.2 & 17.03 & 0.4 & **9.70** & 10 \\ Thm10000 & 1 891 94 95 975 & 3.08 & 0.6 & 3.55 & 0.9 & **2.72** & 19 \\ C100k.0 & 104 617 752 & 40.53 & 0.4 & 33.52 & 0.5 & **6.97** & 18 \\ earring & 8 171 677 & 18.47 & 2.1 & 14.37 & 1.0 & **4.51** & 15 \\ ara238025 & 578 761 & 30.59 & 1.1 & 26.47 & 1.4 & **15.30** & 26 \\ C316k.0 & 186 870 839 & 40.47 & 2.7 & 33.21 & 2.1 & **8.03** & 30 \\ Ira498378 & 2 168 039 & 26.66 & 2.9 & 20.74 & 2.7 & **15.63** & 24 \\ lrb744710 & 1 611 232 & 30.00 & 10 & 25.64 & 4.2 & **20.08** & 27 \\ E1M.0 & 713 187 688 & 23.36 & 54 & 17.91 & 7.7 & **14.07** & 30 \\ santa1437195 & 108 416 878 & 45.01 & 122 & 33.98 & 12 & **10.82** & 107 \\ E3M.0 & 1 267 318 198 & 23.96 & 824 & 18.55 & 31 & **13.17** & 77 \\ E10M.0 & 2 253 088 000 & 24.73 & 8673 & 19.28 & 177 & **12.29** & 566 \\ \hline \end{tabular}
\end{table}
Table 2: Quality of initial tours dependent on chosen method (excess over best known tour) and duration for building the tour. The number of points per instance is given in the file names.  
Figure 4: Magnified region of the initial tour based on GrebCap+ for C100k.0 showing the initial tour with unfavourable long edges.  
is applied recursively. A nearest neighbour approach searches for the shortest connections between points of adjacent clusters. All points within a cluster form a subtour with fixed endpoints and these subtours are optimized by using a brute-force 3-opt optimizer with a maximum of five loops over all points. There is no random component involved, i.e., each execution results in the same tour. The rightmost columns of Table 2 contain the corresponding results.  
As the execution times for small instances suggest, the clustering of DoLoWire is somewhat more complex than the GrebCap initialization. Processing times again increase with the number of points. However, this relation is not monotonic because the processing depends on how the clusters fit the distribution of points. Most importantly, DoLoWire yields much better tours, which reduces the time for subsequent local optimization based on \(k\)-opt operations.