[akoboldfrying]

Neat!

Another benefit I see is that you could quickly generate many heuristic solutions by randomly translating, rotating and/or uniformly scaling the curve, and then choose the best.

It does look like it can produce crossing edges, which are suboptimal in Euclidean space, but these are easy to rectify -- whenever 2 edges cross, just swap their endpoints for a quick guaranteed improvement. Because doing this strictly decreases the total tour length, and every such decrease is lower-bounded by the smallest such decrease among all (nCities choose 4) possible sets of 4 cities, repeatedly doing this must eventually terminate in a crossing-free tour.

[sfink]

That's the missing part in the article. The example of the TSP solution for all cities in Germany was a pretty poor one compared to the optimal, which immediately raises the question: how good is it if you do some simple tricks to improve the heuristic? Some simple global perturbations like you suggested, and then local improvements like swaps to remove crossings, or running it at multiple scales and taking the best result for each region, or whatever.

The space-filling curve approach strikes me as a decent way to get a starting point, not something to use unmodified. But I've no idea whether that's true -- does the structure of such a solution lend itself well to simple iterative improvements or not?