# Redesigning the Wheel for Systematic Travelling Salesmen
## 3 Investigations
### Comparison with a State-of-the-Art Method
Taking the random component of GrebCap+ into account, the optimization has been performed 10 times for each instance. Table 12 lists the corresponding results in terms of worst, best, and median tour. \begin{table}
\begin{tabular}{|c|r|r|r|r|r|r|} \hline  & \multicolumn{3}{c|}{Time Length} & \multicolumn{3}{c|}{\% Excess} \\ Instance & \multicolumn{1}{c|}{shortest} & \multicolumn{1}{c|}{median} & \multicolumn{1}{c|}{longest} & \multicolumn{1}{c|}{median} & \multicolumn{1}{c|}{DoLoWire} \\ \hline E1M.0 & 728 938 609 & 729 615 811 & 730 071 141 & **2.30** & 2.47 \\ E3M.0 & 1 300 823 927 & 1 301 169 118 & 1 301 481 802 & 2.67 & 2.56 \\ E10M.0 & 2 344 824 745 & 2 345 496 436 & 2 349 035 290 & 4.10 & 3.09 \\ \hline Tnm100000 & 1 891 964 990 & 1 891 980 407 & 2 004 219 465 & 0.0018 & 0.0007 \\ earring200k & 8 228 256 & 8 228 990 & 8 229 393 & **0.70** & 0.71 \\ \hline C100k.0 & 108 212 016 & 108 424 800 & 108 662 851 & 3.64 & 2.51 \\ C316k.0 & 194 341 360 & 194 873 454 & 195 259 635 & 4.28 & 2.51 \\ \hline ara238025.tsp & 628 149 & 628 448 & 628 762 & **8.59** & 8.65 \\ Ira498378.tsp & 2 268 652 & 2 271 075 & 2 273 365 & 4.75 & 4.73 \\ lrb744710.tsp & 1 743 045 & 1 743 800 & 1 744 990 & 8.23 & 8.23 \\ \hline santa1437195 & 114 130 515 & 114 244 662 & 114 653 702 & 5.38 & 3.69 \\ \hline \end{tabular}
\end{table} 
Table 12: Results for different instances after 30 min of processing for Sys2 to6 in combination with GrebCap+. Results in bold face are better than Sys2 to6 in combination with DoLoWire. \begin{table}
\begin{tabular}{|c|r|r|r|r|r|r|} \hline  & \multicolumn{3}{c|}{Time Length} & \multicolumn{3}{c|}{\% Excess} \\ Instance & \multicolumn{1}{c|}{shortest} & \multicolumn{1}{c|}{median} & \multicolumn{1}{c|}{longest} & \multicolumn{1}{c|}{median} & \multicolumn{1}{c|}{DoLoWire} \\ \hline E1M.0 & 728 938 609 & 729 615 811 & 730 071 141 & **2.30** & 2.47 \\ E3M.0 & 1 300 823 927 & 1 301 169 118 & 1 301 481 802 & 2.67 & 2.56 \\ E10M.0 & 2 344 824 745 & 2 345 496 436 & 2 349 035 290 & 4.10 & 3.09 \\ \hline Tnm10000 & 1 891 964 990 & 1 891 980 407 & 2 004 219 465 & 0.0018 & 0.0007 \\ earring200k & 8 228 256 & 8 228 990 & 8 229 393 & **0.70** & 0.71 \\ \hline C100k.0 & 108 212 016 & 108 424 800 & 108 662 851 & 3.64 & 2.51 \\ C316k.0 & 194 341 360 & 194 873 454 & 195 259 635 & 4.28 & 2.51 \\ \hline ara238025.tsp & 628 149 & 628 448 & 628 762 & **8.59** & 8.65 \\ Ira498378.tsp & 2 268 652 & 2 271 075 & 2 273 365 & 4.75 & 4.73 \\ lrb744710.tsp & 1 743 045 & 1 743 800 & 1 744 990 & 8.23 & 8.23 \\ \hline santa1437195 & 114 130 515 & 114 244 662 & 114 653 702 & 5.38 & 3.69 \\ \hline \end{tabular}
\end{table} 
Table 11: Results for different instances after 30 min of processing. Values of column ’Best known length’ are copied from [58] for DIMACS (*.0) and from [59] for VLSI (*.tsp) instances. The best-known results for Tnm100000 and santa1437195 have been reported in [29] and [42], respectively. In only three cases is the performance improved when using GrebCap+ instead of DoLoWire for initial tour generation. In addition, the tour lengths significantly increase for the clustered instances C100k, C316k, and santa1437195, which obviously benefit from using DoLoWire as initial tour generator. The chosen settings maxEdgeDist\(=50\), \(maxC=8\) are a compromise between fast processing and large permutation search space with respect to the chosen time constraint. Additional investigations have shown that with respect to the limited time span of 30 min, the largest two instances in the studied set would benefit from smaller values for these two parameters, because the local improvements contribute more to the reduction of the tour length than the larger search space. Fine-granular modification of the parameters results in different optimal settings for different instances. This is mainly due to the modified order of permutation selection, which directs the optimization process to different region in the hyperspace of tour lengths.