# Redesigning the Wheel for Systematic Travelling Salesmen
## 2 Methods
### Initial Tour Generation
#### 2.3.1 Greedy Tour Based on Candidates Paths (GrebCap)  
The first implemented method belongs to the group of greedy tour generators. It starts at an arbitrary point. Its candidate set is examined, and the closest candidate is chosen as the next point. After inserting a point into the tour, it is marked to avoid multiple consideration. This continues, always taking the closest available candidate. When the procedure reaches a point whose candidates have all already been integrated into the tour, the path is saved and any available point is taken as the starting point of the next path. This procedure results in a certain number of paths which have to be connected to form a complete tour. Starting from an endpoint of any first path, a nearest-neighbour approach looks for an end point of another path which has the shortest distance. Both paths are linked to form a joint path. This is repeated until all paths constitute a Hamiltonian circle. The nearest neighbour method has a complexity of \(O(N\log(N))\). Obviously, building the paths accelerates the whole process of finding near neighbours, because the number of path endpoints is much lower than the total number of tour points. It has been observed that the average path length depends on the chance that a path can be extended by a free point from the candidates set. On average, such a set consists of six adjacent points as shown in Table 1. However, if one increases the number of candidates, the average path length becomes longer, the number of paths decreases, and the number \(N\) of points to be compared for nearest neighbour search also decreases, speeding up the tour-generation process. Therefore, an enrichment of the candidates sets is proposed, which considers not only the neighbours from the Delaunay triangulation but additionally the neighbours of all Delaunay candidates. This is illustrated for a particular point in Figure 3. After triangulation, only four neighbouring points (in brown) are candidates of the black point in the centre of the figure. This set is extended by also including the candidates (shown in yellow) of the brown points, so that in total of 13 candidates are available. This augmentation of the Delaunay set also had been mentioned in [49]. Figure 2: Resulting mesh when considering only the five closest candidates per point for TSP instance d1291. If the black point in Figure 3 were the endpoint of a constructed intermediate path when taking only the original candidates set into account, then the additional candidates drastically increase the chance that the path can be continued in the near vicinity without a time-consuming search for the nearest neighbour. This candidate enrichment increases the number of candidates per point from an average of six to approximately 20. The creation of paths as described above sometimes results in very short segments. For these snippets, it is beneficial to individually insert their points into existing paths. The selection of suitable insertion positions is achieved based on the closest candidates of the point to be inserted. Based on systematic tests, it has been found that the integration of snippets with a maximum of 25 points not only fasten the entire procedure but additionally shorten the length of the initial tour. Table 2 contains the results of initial tour generation with GrebCap for different TSP instances with increasing number of points. Because the initial tour varies slightly depending on the chosen starting point when connecting points to paths, the program was executed 10 times for each instance and the average was taken as the result. The excess is computed as  
\[E=\left(\frac{average\_length}{best\_length}-1\right)\cdot 100\%. \tag{2}\]  
It is mostly between 20% and 30% if the points are more or less randomly distributed. For clustered datasets, the excess even rises to over 45% for santa1437195. For Tnm100000, the excess is rather small because the points are arranged along six straight lines, which also facilitates the greedy initial tour generation.