[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?