# A New Constructive Heuristic Driven by Machine Learning for the Traveling Salesman Problem
## 4 Discussion  
A new strategy to design constructive heuristics has been presented. It gives a central role to the integration of statistical, mathematical, and heuristic exploration. We introduced a new way of thinking about the generalization of ML approaches for the TSP, leading to an efficient integration between learning useful information and exploiting it through classic approaches. The objective is to learn useful skills from experience to enhance the \begin{table}
\begin{tabular}{c c c c c c c c c c c} \hline \hline
**Instances** & **MF** & **FI** & **CW** & **F** & **S** & **Y** & **AE** & **BE** & **ML-C** & **ML-SC** \\ \hline rd400 & **0.042** & 0.095 & 0.096 & 0.127 & 0.112 & 0.119 & 0.151 & 3.013 & 7.594 & 0.129 \\ fd417 & **0.048** & 0.114 & 0.108 & 0.211 & 0.190 & 0.192 & 0.221 & 4.425 & 7.020 & 0.193 \\ gr431 & **0.076** & 0.110 & 0.133 & 0.359 & 0.353 & 0.352 & 0.396 & 7.927 & 8.016 & 0.342 \\ pr439 & **0.094** & 0.123 & 0.130 & 0.231 & 0.199 & 0.194 & 0.241 & 4.817 & 7.093 & 0.197 \\ pcb442 & **0.088** & 0.133 & 0.147 & 0.193 & 0.179 & 0.151 & 0.203 & 4.055 & 8.526 & 0.157 \\ d493 & **0.144** & 0.231 & 0.210 & 0.884 & 0.898 & 0.886 & 0.907 & 18.141 & 10.235 & 0.889 \\
**att532** & **0.111** & 0.201 & 0.219 & 0.309 & 0.265 & 0.290 & 0.329 & 6.571 & 10.010 & 0.230 \\ u574 & **0.154** & 0.219 & 0.218 & 0.297 & 0.272 & 0.281 & 0.339 & 6.789 & 10.652 & 0.291 \\ rat575 & **0.105** & 0.233 & 0.225 & 0.236 & 0.223 & 0.186 & 0.282 & 5.647 & 11.079 & 0.204 \\ d657 & **0.159** & 0.332 & 0.294 & 1.025 & 1.034 & 1.003 & 1.081 & 21.617 & 12.054 & 1.028 \\ gr666 & **0.170** & 0.651 & 0.381 & 0.768 & 0.651 & 0.706 & 0.808 & 16.150 & 12.513 & 0.680 \\ u724 & **0.149** & 0.455 & 0.394 & 0.338 & 0.359 & 0.310 & 0.465 & 9.298 & 12.734 & 0.290 \\ rat783 & 0.303 & 0.504 & 0.448 & 0.383 & 0.389 & 0.314 & 0.532 & 10.647 & 14.551 & **0.299** \\ pr1002 & **0.498** & 1.042 & 0.989 & 0.879 & 0.758 & 0.766 & 1.099 & 21.974 & 20.139 & 0.747 \\ u1060 & **0.294** & 1.183 & 0.802 & 1.401 & 1.198 & 1.057 & 1.444 & 28.873 & 20.074 & 1.149 \\ vm1084 & **0.412** & 1.504 & 0.887 & 1.061 & 0.867 & 0.712 & 1.152 & 23.045 & 17.057 & 0.722 \\ pcb1173 & **0.402** & 1.657 & 0.956 & 1.109 & 1.050 & 0.997 & 1.458 & 29.156 & 22.952 & 0.947 \\ d1291 & **0.918** & 2.192 & 1.247 & 4.518 & 4.452 & 4.138 & 4.289 & 85.775 & 20.517 & 3.881 \\ rl1304 & **0.538** & 2.482 & 1.303 & 1.284 & 1.145 & 1.069 & 1.574 & 31.470 & 19.792 & 1.075 \\ rl1323 & **0.696** & 1.856 & 1.332 & 1.739 & 1.655 & 1.268 & 1.861 & 37.213 & 20.215 & 1.324 \\ nrw1379 & **0.994** & 1.942 & 1.624 & 1.270 & 1.203 & 1.107 & 1.762 & 35.249 & 29.439 & 1.113 \\ f1400 & **0.745** & 2.020 & 1.228 & 2.655 & 2.674 & 2.559 & 2.816 & 56.325 & 30.401 & 2.583 \\ u1432 & **1.050** & 2.116 & 1.917 & 1.954 & 1.760 & 1.422 & 2.104 & 42.074 & 32.086 & 1.072 \\ d1577 & **1.044** & 2.733 & 2.117 & 2.650 & 2.616 & 1.840 & 2.713 & 54.267 & 25.673 & 1.438 \\ d1655 & **1.551** & 3.229 & 2.689 & 8.131 & 7.945 & 7.751 & 8.623 & 172.450 & 30.257 & 7.624 \\ vm1748 & **0.660** & 3.914 & 2.360 & 2.525 & 1.836 & 1.914 & 2.894 & 57.884 & 28.875 & 1.967 \\ \hline
**average** & **0.219** & 0.590 & 0.428 & 0.708 & 0.665 & 0.612 & 0.769 & 15.374 & 9.822 & 0.594 \\
**std** & **0.351** & 0.971 & 0.679 & 1.364 & 1.319 & 1.251 & 1.433 & 28.660 & 9.280 & 1.217 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: _Cont._  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Position** & **Method** & **TPR** & **FPR** & **Accuracy** & **Precision** \\ \hline \multirow{3}{*}{1} & F & 98.07\% & 85.80\% & 86.68\% & 87.91\% \\  & ML-C & 93.64\% & 53.08\% & 87.29\% & 91.82\% \\  & ML-SC & 100.00\% & 3.41\% & 99.54\% & 99.47\% \\ \hline \multirow{3}{*}{2} & F & 68.28\% & 18.12\% & 73.62\% & 85.35\% \\  & ML-C & 84.74\% & 29.07\% & 79.32\% & 81.84\% \\  & ML-SC & 100.00\% & 3.01\% & 98.82\% & 98.09\% \\ \hline \multirow{3}{*}{3} & F & 44.40\  
heuristic search. Our _ML-Constructive_ is the first ML approach able to scale and show improvements at once with respect to a classic efficient constructive heuristic.