# Redesigning the Wheel for Systematic Travelling Salesmen
## 3 Investigations
### Parallel Processing of Tour Segments  
As described in Section 2.5, the search for suitable permutations can be accelerated by parallelization. The influence of the number \(N_{\text{jobs}}\) of parallel jobs on the course of the tour-length reduction has been investigated. The results for C316k.0 are shown in Figure 15.  
The comparison now becomes somewhat more difficult because the order of permutations depends on the size of segments, which is, of course, a function of the chosen number of parallel jobs. It can be clearly seen that the optimization process distinctly benefits from the use of multiple threads within the first three minutes (Figures 15a,b). After that, all variants converge to different local minima which is due to the varying order of permutations performed (Figure 15c). The maximum number of threads is set to 30 because the CPU has 32 physical cores. Two cores are reserved for background processes of the operating system so that they do not influence the time measurement too much. By using at least eight parallel jobs for this instance, the local minimum can be reached within 60 min. With 30 jobs, the shortest tour can be attained after approximately half an hour. A similar minimum is obtained with 16 jobs, but in this example it takes almost 60 min to reach the point of convergence. When using eight parallel jobs, the minimum is reached after 35 min. Unfortunately, the sequence of permutations here steers the optimization into an unfavourable local minimum. Figure 14: Comparison of tour length depending on elapsed time when using different initial-tour generators in application to ara238025.tsp. Figure 15: Progress of optimization dependent on the number of parallel jobs in application to C316k.0: (**a**) over full duration, (**b**) first six minutes, (**c**) last 55 min. Most interesting is the influence of multithreading on the largest instance in the TSPs set used. Figure 16 depicts the optimization progress for E10M.0 containing ten million points as a function of the number of parallel jobs. The optimization starts with an initial tour of length \(2\,529\,955\,468\) provided by DoLoWire. Reading the corresponding coordinates and permutation files takes eight seconds. For the single-job case (solid curve), the determination of candidates takes additional 61 s before the actual optimization can begin. When 2-opt and 3-opt permutations have exhausted their potential (after about 210 s), 5-opt operations are enabled. The tour is then steadily improved until the time limit is reached. When using two parallel jobs, the preparation time increases to 150 s due to an unfortunate point configuration for the triangulation algorithm used. This computational overhead is needed after each round of parallel processing causing the stair-stepped curve up to about 11 min. The following plateau is a consequence of the chosen scheduling mechanism which switches back to single-job processing too early in this situation. After 30 min, the first round of parallel processing with 5-opt permutations is activated, and it continues until the specified time expires. The more jobs are used in parallel, the fewer points are contained in each sequence, and the triangulation overhead becomes less pronounced. The curves now appear to be piecewise linear. This is simply a consequence of the uniform distribution of points in E10M.0. Each round of parallel processing corresponds to exactly one loop over all points P. The chance of improvement is evenly distributed in this course. With each new round, the probability of successful permutations decreases; the curves flatten accordingly. A similar progression is observed for E3M.0, the second largest instance of the test set (Figure 17). Figure 16: Progress of optimization dependent on the number of parallel jobs in application to E10M.0. This instance is highly clustered, and different parts of the tour have different optimization potential.