I'm trying to solve the Travelling Salesman Problem in a non-complete graph $(G,E)$ using genetic algorithms.
My problem is that I can't find a good first approximation by the usual greedy algorithms, as long as I can't assure an arbitrary edge $(u,v)$ to be in $E$. I tried to add to $E$ new edges (with almost infinity weight) in order to make it complete, bit then it turns to be way more inefficient.
I can't find a good solution on internet. So can anyone help me?