The solution to this problem is not very hard : you just use a combination of two kinds of technique
You use a combination of search and non search , the idea is to limit the search to a managable level, a clever technique of limiting the search by using a convex hull is applied, and you do partition the search space in to a set of layered convex hulls where the computation to find the optimisation is done one step at a time, please see my algorithm description :
or just type NEW ALGORITHM FOR THE TSP in youtube search
