## 3 Implementation and Results  
_CII_-algorithm was coded in C++ and compiled in g++ on a server with processor 2x Intel Xeon E5-2650 0 @ 2.8 GHz (Cuernavaca, Mor., Mexico), 32 GB in RAM and Ubuntu 18.04 (bionic) operating system (we have used only one CPU in our experiments). We did not keep the cost matrix in computer memory, but we have rather calculated the costs using the coordinates of the points. This does not increase the computation time too much and saves considerably the required computer memory. We have tested the performance of _CII_-algorithm for 85 benchmark instances from TSPLIB [16] library and for 135 benchmark instances from TSP Test Data [17] library. The detailed results are presented in the Appendix. In our tables, parameter \"Error\" specifies the approximation factor of algorithm \(H\) compared to cost of the best known solution (C(BKS)):  
\[Error_{H}=\left|\frac{C(BKS)-C(T_{H})}{C(BKS)}\right|100\%. \tag{13}\]  
In Table 7 below, we give the data on the average performance of our heuristics. The average error percentage of our heuristics is calculated using Formula (13). It shows, for each group of instances, the average error of the solutions delivered by Phase 2 and, at Phase 3, the number of cycles at Phase 3 and the average decrease in the cost of the solution decreased at Phase 3 compared to that Phase 3. In the diagrams below (on the left hand-side), we illustrate the dependence of the approximation given by our algorithm on the size of the tested instances, and the dependence of the execution time of our algorithm on the size of the instances (right hand-side diagrams). We classify the tested instance into three groups: the small ones (from 1 to 199 points in Figure 12), the middle-sized ones (from 200 to 9999 points in Figure 13), and large instances (from 10,000 to 250,000 in Figure 14). We do not include the data for the largest two problem instances _1 ra498378_ and _1 rb744710_ because of the visualization being technically complicated. The error for these instances is 12.5% and 15.9%, respectively, and the CPU time was limited to two weeks for both instances. As we can see, at Phase 3, there is an improvement in the quality of the solutions delivered by Phase 2. \begin{table}
\begin{tabular}{l c c c c c} \hline \hline
**Description** & **TSPLIB** & **NATIONAL** &
\begin{tabular}{c} **ART** \\ **GALLERY** \\ \end{tabular} & **VLSI** & **All** \\ \hline Number of instances & 83 & 27 & 6 & 102 & 218 \\ \hline Average error percentage of the solutions at Phase 2 & 11.8\% & 17.7\% & 6.7\% & 18.4\% & 15.4\% \\ \hline Average number of cycles & 7 & 11 & 11 & 10 & 9 \\ performed at Phase 3 & 6.5\% & 9.6\% & 3.1\% & 9.8\% & 8.3\% \\ Final average error percentage & 5.3\% & 8.2\% & 3.6\% & 8.6\% & 7.2\% \\ Average memory usage & 0.8 MiB & 1.6 MiB & 10.9 MiB & 2.3 MiB & 1.88 MiB \\ \hline \hline \end{tabular}
\end{table} 
Table 7: Statistics about the solutions delivered by _CII_. Table 8 shows the summary of the comparison statistics of the solutions delivered by our algorithm _CII_ with the solutions obtained by the heuristics that we have mentioned in the introduction (namely, DFACO [10], ACO-3 Opt [10], ESACO [7], PACO-3 Opt [8], DPIO [12], ACO-RPMM [9], Partial ACO [6], and PRNN [11]). We may observe in Table 9 that algorithm _CII_ has attained an improved approximation for 17 instances. At the same time, in terms of the execution time, our heuristic dominates the other heuristics. Figure 14: (**a**) error vs. number of points, and (**b**) processing time vs. number of points, where \(10,000\leq|V|<250,000\). Figure 12: (**a**) error vs. number of points, and (**b**) processing time vs. number of points, where \(1\leq|V|<200\). Figure 13: (**a**) error vs. number of points, and (**b**) processing time vs. number of points, where \(200\leq|V|<10,000\). In the Table 9, we specify the problem instances for which our algorithm provided a better relative error than some of the earlier cited algorithms.