# A New Constructive Heuristic Driven by Machine Learning for the Traveling Salesman Problem
## 2 Materials and Methods
### Constructive Heuristics  
Constructive heuristics are employed to create TSP solutions from scratch, when just the initial formulation described in Section 1.1 is available. They exploit intrinsic features during the solution creation, generally provide quick solutions with modest quality, and exhibit low polynomial computational complexity [1; 24; 41].  
In this paper, we further develop constructive heuristics. Particularly, those that take their decisions on edges are addressed. These approaches grow many fragments of the tour, in opposition to NN that grows just a single fragment (Figure 1). Since at each addition the procedure must avoid inner-loops and no vertex can be connected with more than two other vertices, they take an extra effort concerning the NN to preserve the TSP constraint. However, the computational time needed to construct a tour remains limited [26].  
As introduced by [42; 43], two main choices are required to design an original constructive heuristic driven by edge choices: the order for the examination of the edges, and the constraints that ensure a correct addition. Note that to construct an optimal TSP solution the examination order of the edges must be optimal as well (there are more optimal orders). So, theoretically, the objective of an efficient constructive is to examine the edges in the best possible order.  
The examination order is arranged according to the relevance that each edge of the instance exhibits. The relevance of an edge is related to the probability that we expect that such an edge is in the optimal solution. The higher is the relevance the earlier that edge should be examined. Different strategies are possible to measure the edges' relevance, the most famous ones are the MF and the CW policies. The MF relevance is expressed by the cost values, the smaller is the cost, the higher is the probability of being added. Instead, the CW relevance depends on the saving value, which was designed on purpose to rethink the examination order. Saving is the gain obtained when rather than passing through a hub node \(h\), the salesman uses the straight connection between vertex \(i\) and vertex \(j\). Note that the hub vertex is chosen to exhibit the shortest Total Distance (TD) from the other vertices. Equation (6) describes the formulas used to find the hub, while Equation (7) shows the function employed to compute the saving values.  
\[h=\operatorname*{arg\,min}_{i\in V}\;TD[i],\qquad TD[i]=\sum_{j=0}^{n-1}c_{ij},\qquad\forall i\in V \tag{6}\]  
\[s_{ij}=c_{ih}+c_{hj}-c_{ij},\qquad\forall i,j\in V,\text{ with }i\
eq j \tag{7}\]  
The second important choice is to define simple constraints that ensure correct additions. The edge's addition checker is the algorithm the allows to add feasible edges at each iteration. For both approaches (MF and CW), it is checked that the examined edge does not exhibit extremes vertices with already two connections (Equations (2) and (3)),  
Figure 1: (**A**) Single fragment constructor that operates similarly to NN. (**B**) Constructor that growths multiple fragments similarly to MF and CW.  
and that does not create inner-loops (Equation (4)) with the current partial solution. _Tracker_ is called the subroutine that checks if the examined edge can create an inner-loop, and it uses a quadratic number of operations for the worst-case scenario in our implementation (Appendix A). Note that there exist more efficient data structures and algorithms for the tracker subroutine that even runs in \(O(n\log n)\)[43].