I'm curious if somebody has already figured this out. Is there an efficient algorithm that will generate (in $\mathbb{R}^2$) a sequence of points in such a way that the solution to the travelling salesmen problem is known a priori, and such that we have a uniform distribution on the set of points? For example, I can think of an algorithm that will generate such a sequence by plotting a polygon, and the minimum distance would be the points going around the outside of the polygon, but the distribution on point-sets from this algorithm is highly biased.
So I would hope for an efficient algorithm that generates a set of points in $[0,1]^2$ (and its corresponding TSP solution), with equal probability to any set of points, i.e., each point has iid uniform distribution on $[0,1]^2$. You could interpret "efficient" as "polynomial time".
PS: I strongly suspect that no algorithm could exist because if so, I imagine the problem would be solvable, so in this case, is there a database somewhere with a large number of solutions for randomly generated sets of points?