# Redesigning the Wheel for Systematic Travelling Salesmen
## 2 Methods
### Candidates Selection  
As pointed out in the previous subsection, an increasing number of cuts (increasing \(k\) for \(k\)-opt) leads to exponential explosion of possible permutations making this approach too time-consuming. An intelligent approach would ignore those permutations which are most unlikely to lead to an improvement. It should consider only permutations which connect points that are close to each other. In other words, a set of good candidates has to be determined for each point.  
[PERSON] had proposed a so-called \(\alpha\)-measure which evaluates the cost increase when a minimum 1-tree is required to contain the edge [46; 47]. The five \(\alpha\)-nearest points proved to be an excellent set of candidates. [PERSON] [48] suggested using the least costly edges in each of the four geometric quadrants (for 2-dimensional instances) around a point, which may also be helpful for clustered instances in addition to the \(\alpha\)-measure [6].  
The proposed method does not maintain any trees such a minimum 1-tree or similar; instead it uses Delaunay triangulation to find suitable candidates. This approach had been proposed by [PERSON] for the first time [49] and was also recently adopted in [50]. It has the advantage that neighbours in all directions are automatically considered, even though one or more close neighbours might be missed. We apply the [PERSON]'s sweepline algorithm described in [51] by adapting the software written and provided by [PERSON] himself. Delaunay triangulation leads to an average of six candidates per point, Table 1.  
\begin{table}
\begin{tabular}{|c|c|c|c|} \hline
**Instance** & **Minimum** & **Average** & **Maximum** \\ \hline rat99.tsp & 3 & 5.64 & 9 \\ d1291.tsp & 3 & 5.96 & 96 \\ u2152.tsp & 3 & 5.87 & 21 \\ pr2392.tsp & **2** & 5.96 & 22 \\ fnl4461.tsp & 3 & 5.99 & 14 \\ ch71009.tsp & 3 & 6.00 & 18 \\ Tnm100000.tsp & 3 & 5.40 & 66 \\ C100k.0 & 3 & 6.00 & 17 \\ C316k.0 & 3 & 6.00 & 20 \\ earring200k.tsp & **2** & 6.00 & 21 \\ ara238025.tsp & 3 & 6.00 & 46 \\ Ira498378.tsp & 3 & 6.00 & 115 \\ hrb744710.tsp & 3 & 6.00 & 77 \\ santa1437195.tsp & 3 & 6.00 & 29 \\ E1M.0 & 3 & 6.00 & 28 \\ E3M.0 & 3 & 6.00 & 31 \\ E10M.0 & 3 & 6.00 & 37 \\ \hline \end{tabular}
\end{table}
Table 1: Number of candidates per point determined via Delaunay triangulation.  
However, extremal points that are far from all other points can have many more candidates assigned to them as can be seen for d1291 and lra498378. Figure 1 shows two special cases of many and few candidates per point.  
The use of candidate sets can greatly reduce the number of permutations to be examined per point, but it is also likely that the procedure will miss good neighbours and, accordingly, will not find some connections (edges) that belong to the optimal tour. The implemented software allows us to determine the maximum number \(maxC\) of allowed candidates per point to be used. Then only the closest \(maxC\) neighbours are taken into account. When the set of candidates is limited to \(maxC=5\), for example, then some edges remain unconsidered as can be seen in Figure 2 in comparison to Figure 1a. Interestingly, the point at the bottom left is still connected to many other points. This is just because the point is itself one of the five Delaunay candidates for these other points.  
As the points and their assigned candidate neighbours are frequently inspected during the optimization process, the corresponding distances between them are precomputed, leading to a very sparse distance matrix that can be stored efficiently.  
Figure 1: Triangulation of point clouds: (**a**) d1291 showing a high number of candidates for the bottom left point; (**b**) close-up of pr2392 showing the top left point with only two edges, i.e., two candidates.