# A New Constructive Heuristic Driven by Machine Learning for the Traveling Salesman Problem
## 2 Materials and Methods
### The ML-Constructive Algorithm
It takes overall \(O(n^{2})\) operations up to the final tour (proof in Appendix A). Once all the constraints of the TSP have been met, the edge \(l\) is processed by the ML decision-taker (lines 11 and 14). Even if time-consuming, such sub-routine is completed in constant time for each \(l\). Initially, the image depicting the \(l\) edge and its local information is created, then it is given as input to the neural network. To create the image, the vertices of the CLs and the existing connections in the current partial solution must be retrieved. Hash maps are used for both tasks, and since the image can include up to sixty vertices, this operation takes a constant amount of time for each \(l\) edge in \(L_{P}\). The size of the neural network does not vary with the number of vertices in the problem as well but remains constant for each edge in \(L_{P}\). To complete the tour, the second phase starts by identifying the hub vertex (line 15). It considers all the vertices in the problem (free and not), following the rule explained in Equation (6). Free vertices are selected from the partial solution, and edges connecting such vertices are inserted in the difficult edges list \(L_{D}\) (line 16). The saving for each edge in \(L_{D}\) is computed (line 17), and the list is sorted according to these values (line 18) in \(O(n^{2}\log n^{2})\). At this point (lines 20 to 27), the solution is completed employing the classical multiple fragment steps, which are known to be \(O(n^{2})\)[41]. Therefore, the complexity of the worst-case scenario for the _ML-Constructive_ is:  
\[O(n+n\log n+n^{2}+n^{2}\log n^{2})=O(n^{2}\log n^{2}) \tag{9}\]  
Note that to complete the tour we proposed the use of CW, but rather hybrid approaches that also use some sort of exhaustive search could be very promising as well, although more time-consuming. ```
1:TSP graph \(G(V,E)\)
2:a feasible tour \(X\)
3:procedureML-Constructive(\(G(V,E)\))
4: create CL for each vertex
5: insert the shortest two vertices for each CL into \(L_{P}\)
6: remove from \(L_{P}\) all duplicate edges in their higher positions
7: sort \(L_{P}\) according to the position in the CL and the ascending costs \(c_{i,j}\)
8:\(X=\mathbf{\bar{0}}\)
9:for\(l\) in \(L_{P}\)do
10: select the extreme vertices \(i,j\) of \(l\)
11:if vertex \(i\)and vertex \(j\) have exactly one connection each in \(X\)then:
12:if\(l\) do not creates a inner-loopthen:
13:if the ML agrees the addition of \(l\)then: \(x_{i,j}=1\)
14:else
15:if vertex \(i\)and vertex \(j\) have less than two connections each in \(X\)then:
16:if the ML agrees the addition of \(l\)then: \(x_{i,j}=1\)
17: find the hub vertex \(h\)
18: select all the edges that connects free vertices and insert them into \(L_{D}\)
19: compute the saving values with respect to \(h\) for each edge in \(L_{D}\)
20: sort \(L_{D}\) according to the descending savings \(s_{i,j}\)
21:\(t=0\)
22:while the solution \(X\) is not complete do
23:\(l=L_{D}[t]\), \(t=t+1\)
24: select the extreme vertices \(i,j\) of \(l\)
25:if vertex \(i\)and vertex \(j\) have less than two connections each in \(X\)then:
26:if\(l\) do not creates a inner-loopthen: \(x_{i,j}=1\)
```  
**Algorithm 1** ML-Constructive.