## Appendix A  
In the table below (Table 1), we give some details on the earlier mentioned heuristics with which we compare our results (the entries in the column \"Runs\" specify the number of the reported runs of the corresponding heuristic). Figure 15: RAM vs. number of points for all the tested instances. In the tables below, each line corresponds to a particular benchmark instance. For each of these instances, we indicate the performance of Phase 2 and Phase 3, separately, and that of the other heuristics reporting the results for that instance. In addition, 85 benchmark instances were taken from TSPLIB [16] and 135 instances are from TSP Test Data [17] libraries. Tables 11, 12, and 13 include the earlier known results. In some lines of our tables (e.g., line 1, Table 13), a slight difference in the approximation errors of our algorithm and those of the algorithms from the \"Results for National TSP Benchmarks\" table can be seen due to the way the distances in the obtained solutions are represented in our algorithm (we do not round the distances represented as decimal numbers, whereas the distances in the best known solutions are rounded). \begin{table}
\begin{tabular}{c c c c c c c c c c c c c c c c c c} \hline \hline  & \multicolumn{3}{c}{**Instance**} & \multicolumn{3}{c}{**CII Heuristic (Phase 2)**} & \multicolumn{3}{c}{**CII Heuristic (Phase 3)**} & \multicolumn{3}{c}{**Other Heuristics**} \\  & \(V\) & **Opt?** & \(C(BKS)\) & \(C(T)\) & \(Error_{CII}\) & **Time** & \(C(T)\) & **Error\({}_{CII}\)** & **Time** & **RAM** & \# & \(C_{min}(T_{H})\) & \(Error_{H}\) & **Time** & **Heuristic Id** \\ \hline eil51 & 51 & yes & 426 & 454 & 6.6\% & 0.4 ms & 454 & 6.6\% & 1.0 ms & 0.5 MiB & 1 & 426 & 0.0\% & 1.0 s & DFACO \\  & & & & & & & & & & 426 & 0.0\% & 1.0 s & ACO-3 Opt \\ \hline berlin52 & 52 & yes & 7542 & 8058 & 6.8\% & 1.1 ms & 8058 & 6.8\% & 4.5 ms & 0.6 MiB & 3 & 7542 & 0.0\% & 1.0 s & DFACO \\  & & & & & & & & & & 7542 & 0.0\% & 1.0 s & ACO-3 Opt \\ \hline st70 & 70 & yes & 675 & 710 & 5.2\% & 0.6 ms & 701 & 3.8\% & 11.1 ms & 0.6 MiB & 3 & 826 & 22.3\% & 0.4 ms & NN \\ \hline eil76 & 76 & yes & 538 & 576 & 7.0\% & 0.7 ms & 556 & 3.4\% & 2.2 ms & 0.6 MiB & 3 & 538 & 0.0\% & 3.0 s & DFACO \\  & & & & & & & & & & & 538 & 0.0\% & 3.0 s & ACO-3 Opt \\ \hline pr76 & 76 & yes & 108,159 & 114,808 & 6.1\% & 0.7 ms & 112,911 & 4.4\% & 3.0 ms & 0.6 MiB & 4 & 148,348 & 37.2\% & 0.5 ms & NN \\ \hline rat99 & 99 & yes & 1211 & 1294 & 6.9\% & 1.0 ms & 1230 & 1.5\% & 9.4 ms & 0.6 MiB & 3 & 1442 & 19.1\% & 0.8 ms & NN \\ \hline kroA100 & 100 & yes & 21,282 & 23,050 & 8.3\% & 1.1 ms & 21,443 & 0.8\% & 3.5 ms & 0.6 MiB & 3 & 21,282 & 0.0\% & 2.0 s & DFACO \\  & & & & & & & & & & 21,282 & 0.0\% & 2.0 s & ACO-3 Opt \\ \hline kroB100 & 100 & yes & 22,141 & 23,247 & 5.0\% & 1.1 ms & 22,716 & 2.6\% & 3.3 ms & 0.6 MiB & 3 & 22,141 & 0.0\% & 2.0 s & DFACO \\  & & & & & & & & & 22,141 & 0.0\% & 2.0 s & ACO-3 Opt \\ \hline kroC100 & 100 & yes & 20,749 & 21,632 & 4.3\% & 1.1 ms & 20,922 & 0.8\% & 3.8 ms & 0.6 MiB & 3 & 20,749 & 0.0\% & 2.0 s & DFACO \\  & & & & & & & & & 20,749 & 0.0\% & 2.0 s & ACO-3 Opt \\ \hline kroD100 & 100 & yes & 21,294 & 21,712 & 2.0\% & 1.1 ms & 21,582 & 1.4\% & 3.4 ms & 0.6 MiB & 3 & 21,294 & 0.0\% & 3.0 s & DFACO \\  & & & & & & & & & 21,294 & 0.0\% & 3.0 s & ACO-3 Opt \\ \hline kroE100 & 100 & yes & 22,068 & 22,870 & 3.6\% & 1.0 ms & 22,528 & 2.1\% & 8.3 ms & 0.6 MiB & 3 & 22,068 & 0.0\% & 2.0 s & DFACO \\  & & & & & & & & & & 22,068 & 0.0\% & 2.0 s & ACO-3 Opt \\ \hline rd100 & 100 & yes & 7910 & 8465 & 7.0\% & 1.2 ms & 8245 & 4.2\% & 3.8 ms & 0.6 MiB & 3 & 7910 & 0.0\% & 2.0 s & DFACO \\  & & & & & & & & & & 7910 & 0.0\% & 2.0 s & ACO-3 Opt \\ \hline eil101 & 101 & yes & 629 & 679 & 7.9\% & 1.1 ms & 666 & 5.9\% & 19.5 ms & 0.6 MiB & 3 & 629 & 0.0\% & 12.0 s & DFACO \\  & & & & & & & & & & 629 & 0.0\% & 10.0 s & ACO-3 Opt \\ \hline \hline \end{tabular}
\end{table} 
Table 13: Results for **TSPLIB** benchmarks.