# A New Constructive Heuristic Driven by Machine Learning for the Traveling Salesman Problem
## 3 Experiments & Results  
To test the efficiency of the proposed heuristic, experiments were carried out on 54 standard instances. Such instances were taken from the TSPLIB collection [19] and their vertex set cardinality varies from 100 to 1748 vertices. Non-euclidean instances, such as the ones involving geographical distances (GEO) or special distance functions (ATT), were addressed as well. We recall that the ResNet model was trained on small (100 to 300 vertices) uniform random euclidean instances, evaluated on medium-large (500 to 1000 vertices) uniform random euclidean instances, and tested on TSPLIB instances. We emphasize that TSPLIB instances are generally not uniformly distributed, and, as mentioned, these instances were selected among all available instances in such a way to have no less than 100 total vertices, no more than 2000 total vertices and with the ability to be described in a two-dimensional space. All the experiments were handled employing python 3.8.5 [54] for the algorithmic component, and pytorch 1.7.1 [55] to manage the neural networks. The following hardware was utilized:  
* a single GPU _NVIDIA GeForce GTX 1050 Max-Q;_
* a single CPU _Intel(R) Core(TM) i7-8750H @ 2.20 GHz._  
During training, all hardware was exploited, while just the CPU was used to test. The experiments presented in Table 3 compare _ML-Constructive_ (ML-C) results--achieved employing the ResNet--to other famous strategies based on fragments, such as the MF and the CW. The first is equivalent to include all the existing edges in the list of promising edges \(L_{P}\), sort the list according to the ascending cost values--without considering the CL positions--and then substituting the ML decision taker with a rule that always inserts the considered edge. While the second strategy is equivalent to keeping the list \(L_{P}\) empty, this means that the first phase of _ML-Constructive_ does not create any fragment, while the construction is made completely in the second phase. For the sake of completeness, the FI was tested as well and added to Table 3. Even if FI is not a growing fragment approach, and therefore is not an alternative strategy of our _ML-Constructive_ heuristic, it is nevertheless a good benchmark solver to compare. To explore, evaluate and interpret the behavior of our two-phase algorithm, other strategies were investigated as well. The ML decision-taker can act in very different ways, and a comparison with expert-made heuristic rules can be significant. Deterministic and stochastic heuristic rules were created to explore the optimality gap variation. The aim was to prove that the learned ML model would produce a higher gain for the heuristic rules, as corroborated by Table 3. The heuristic rules were substituting the ML decision-taker component within the _ML-Constructive_ (lines 10 and 13 of Algorithm 1). No changes in the selecting and sorting strategies were applied to create the lists \(L_{P}\) and \(L_{D}\). The First (F) rule decides to deterministically add the \(l\) edge if one of its extremes is the first closestvertices in the CL of the other extreme. The Second (S) rule is similar, but it adds \(l\) only if one extreme is the second shortest in the CL of the other. The policy that always validates (Y) the insertion of the edges in \(L_{P}\) was examined as well. It represents with CW the extreme cases where the ML decision-taker always validates or not, respectively, the edges in \(L_{P}\). A stochastic strategy called empirical (E) was tested as well, which adds the edges in \(L_{P}\) according to the distribution seen for the evaluation data-set in Figure 2. Therefore, it inserts the edge if one of the extremes is the first with probability 0.886 or the second with probability 0.512. Twenty runs of the empirical strategy were made, and in (AE) we show the average results, while in (BE) we show the best from all runs.