# Redesigning the Wheel for Systematic Travelling Salesmen
## 3 Investigations
### Comparison with a State-of-the-Art Method  
The proposed method Sys2 to6 is now compared to LKH [56], which is widely known as a state-of-the-art heuristic for finding excellent TSP tours. The performance of Sys2 to6 is mainly influenced by the values usedfor the number of candidates \(maxC\), the maxEdgeDist value, the number of parallel jobs, and the maximal duration of processing. The latter is set to a limit of 30 min (including the initial tour generation), in combination with \(N_{\text{jobs}}=30\). The other two parameters have been varied (\(6\leq maxC\leq 10\), \(5\leq\text{maxEdgeDist}=100\)). A good compromise could be found by using \(maxC=8\) and maxEdgeDist\(\leq 50\). Note that without time constraints, larger values for both parameters would typically lead to shorter tours. The default LKH settings are geared toward small and medium-sized instances. For large instances, the preparation of initial values already takes more than an hour even without outputting an initial tour. To force LKH to output results within 30 min also for E10M.0 requires special options (see Table 10). The generation of sets of candidates by using the default settings is too time-consuming and must be replaced by the Delaunay method. The corresponding implementation enriches the set of Delaunay candidates as described in Section 2.3.1 with respect to Figure 3. Finally, the five Delaunay candidates with the smallest \(\alpha\) value are used [57]. It has to be mentioned that LKH can result in better tours for smaller instances when manually optimized settings are used. The time limit is set to a maximum of 30 min. However, because LKH does not include preprocessing in the time measurement, this limit must be adaptively reduced for each instance. Because the initial tour generation of LKH is dependent on seeding the random number generator, the optimization process is started 10 times with different seed values bu using the keyword SEED. The average tour length is chosen for the comparison. Running LKH on instance Thm100000 causes the program to abort. This can be prevented by additional use of the option 'PRECISION = 1' [57]. Table 11 compares the results in terms of final tour length obtained within 30 min of optimization. \begin{table}
\begin{tabular}{c c} \hline \hline
**Parameter** & **Value** \\ \hline CANDIDATE\_SET\_TYPE & DELAUNAY \\ INITIAL\_PERIOD & 10 \\ INITIAL\_TOUR\_ALGORITHM & GREEDY \\ MAX\_SWAPS & 10 \\ MAX\_TRIALS & 100 \\ TIME\_LIMIT & \textless{}1800 \\ SEED & [1...10] \\ \hline \hline \end{tabular}
\end{table} 
Table 10: Required parameter settings for LKH for solving large instances within half an hour. When processing very large instances with LKH, it is not possible to get a tour-length value close to 30 min, the actual calculation times are about 32 min for E3M.0 and about 38 min for E10M.0. The instances ExM.0 contain uniformly distributed points. As can be concluded from the results in Table 11, LKH does an excellent job for theses instances. The achieved excesses are less than 0.5% whereas the tours obtained with Sys2 to6 are significantly longer. Something similar can be observed for the VLSI instances. Here, Sys2 to6 performs worst with excess values above 8%. For the instances Cxk.0, which contain many clusters of points, the proposed method can outperform LKH. The best performance of Sys2 to6 in relation to LKH can be observed for the instance santa1437195. It contains 1 437 195 two-dimensional coordinates of households (Finnish National Coordinate System) distributed all over Finland (see for example [42]). These coordinates also show distinct clusters in large Finnish cities. With the given settings and constraints, LKH has problems dealing with this dataset, resulting in an excess of 7.32%, whereas Sys2 to6 only has an excess of 3.69%. As the performance of Sys2 to6 might depend on the initial-tour generation chosen, additional investigations have been conducted by using GrebCap+ instead of DoLoWire.