## Appendix A
\begin{table}
\begin{tabular}{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**} \\  & \(\mathbf{V}\) & **Opt2** & \(C(BKS)\) & \(C(T)\) & _Error\({}_{CII}\)_ & **Time** & \(\mathbf{C(T)}\) & _Error\({}_{CII}\)_ & **Time** & **RAM** & \# & \(C_{min}(T_{H})\) & _Error\({}_{H}\)_ & **Time** & **Heuristic Id** \\ \hline wi29 & 29 & yes & 27,603 & 27,739 & 0.5\% & 0.3 ms & 27,601 & 0.0\% & 28.0 ms & 0.6 MB & 3 & 35,474 & 28.5\% & 0.2 ms & NN \\ \hline dj38 & 38 & yes & 6656 & 6863 & 3.1\% & 0.3 ms & 6659 & 0.1\% & 11.2 ms & 0.6 MB & 5 & 8165 & 22.7\% & 0.3 ms & NN \\ \hline q194 & 194 & yes & 9352 & 10,505 & 12.3\% & 3.8 ms & 9886 & 5.7\% & 37.1 ms & 0.6 MB & 7 & 12,481 & 33.5\% & 2.6 ms & NN \\ \hline zi929 & 929 & yes & 95,345 & 110,187 & 15.6\% & 73.5 ms & 100,842 & 5.8\% & 630 ms & 0.7 MB & 8 & 119,685 & 25.5\% & 36.7 ms & NN \\ \hline lu980 & 980 & yes & 11,340 & 12,834 & 13.2\% & 86.4 ms & 12,077 & 6.5\% & 404 ms & 0.6 MB & 5 & 14,284 & 26.0\% & 29.4 ms & NN \\ \hline rw1621 & 1621 & yes & 26,051 & 30,315 & 16.4\% & 233 ms & 28,771 & 10.4\% & 1.6 s & 0.7 MB & 8 & 33,493 & 28.6\% & 71.5 ms & NN \\ \hline mu1979 & 1979 & yes & 86,891 & 99,356 & 14.3\% & 350 ms & 91,684 & 5.5\% & 3.8 s & 0.8 MB & 10 & 113,362 & 30.5\% & 112 ms & NN \\ \hline nu3496 & 3496 & yes & 96,132 & 111,981 & 16.5\% & 1.1 s & 103,717 & 7.9\% & 9.2 s & 0.8 MB & 10 & 121,713 & 26.6\% & 327 ms & NN \\ \hline ca463 & 4663 & yes & 1290319 & 1,557,923 & 20.7\% & 1.9 s & 1,407,891 & 9.1\% & 18.2 s & 0.9 MB & 10 & 1,637,468 & 26.9\% & 564 ms & NN \\ \hline tz6117 & 6117 & no & 394,718 & 477,869 & 21.1\% & 3.5 s & 433,784 & 9.9\% & 40.0 s & 1 MB & 14 & 494,624 & 25.3\% & 843 ms & NN \\ \hline eg7146 & 7146 & no & 172,386 & 198,566 & 15.2\% & 4.5 s & 182,979 & 6.1\% & 57.9 s & 1.1 MB & 14 & 219,365 & 27.3\% & 1.1 s & NN \\ \hline ynn7663 & 7663 & yes & 238,314 & 285,881 & 20.0\% & 5.0 s & 259,780 & 9.0\% & 1.4 m & 1.1 MB & 18 & 308,219 & 29.3\% & 1.1 s & NN \\ \hline pm8079 & 8079 & no & 114,855 & 137,182 & 19.4\% & 5.7 s & 126,746 & 10.4\% & 55.6 s & 1.2 MB & 10 & 148,936 & 29.7\% & 1.2 s & NN \\ \hline ei8246 & 8246 & yes & 206,171 & 248,695 & 20.6\% & 6.0 s & 225,178 & 9.2\% & 1.0 m & 1.1 MB & 11 & 254,553 & 23.5\% & 1.2 s & NN \\ \hline ar9152 & 9152 & no & 837,479 & 1,014,041 & 21.1\% & 8.4 s & 927,348 & 10.7\% & 1.2 m & 1.2 MB & 10 & 1,063,376 & 27.0\% & 1.5 s & NN \\ \hline ja9847 & 9847 & yes & 491,924 & 611,959 & 24.4\% & 8.7 s & 544,411 & 10.7\% & 2.0 m & 1.2 MB & 16 & 630,169 & 28.1\% & 1.9 s & NN \\ \hline gr9882 & 9882 & yes & 300,899 & 356,753 & 18.6\% & 8.5 s & 325,599 & 8.2\% & 1.8 m & 1.3 MB & 14 & 395,267 & 31.4\% & 2.3 s & NN \\ \hline kz9976 & 9976 & no & 1,061,881 & 1,298,405 & 22.3\% & 8.9 s & 1,168,843 & 10.1\% & 1.6 m & 1.3 MB & 12 & 1,344,845 & 26.6\% & 1.8 s & NN \\ \hline fi10639 & 10639 & yes & 520,527 & 633,623 & 21.7\% & 9.8 s & 574,001 & 10.3\% & 2.1 m & 1.3 MB & 14 & 659,800 & 26.8\% & 2.0 s & NN \\ \hline \hline \end{tabular}
\end{table} 
Table 8: Results for **National TSP** benchmarks.