Indeed, the comparison with the 110-processor 6-month effort to solve the 15112-cities problem is a bit misleading, because most of that time was spent proving that a solution with length 1573084 was optimal.
The team behind that effort has made their software available (CONCORDE - http://www.tsp.gatech.edu//concorde/index.html), and includes a few standard heuristics that are already quite fast:
- for the record, the space-filling curve approach takes less than a second and produces a tour 33% larger than the optimal, which is roughly 1573084*4/3=2097445
- the "greedy" heuristic takes less than a second and computes a solution with length 1803479, which is already better than the space-filling curve
- the "quick boruva" heuristic is even faster and produces a solution with length 1789519 (less than 14% larger than optimal)
- the "Lin Kernighan" heuristic takes a few minutes and produces a solution with length 1577339 (less than 0.3% larger than optimal)
So, while this is an interesting application of space-filling curves, it cannot really be considerered to be competitive with the state-of-the-art in TSP heuristics.
The team behind that effort has made their software available (CONCORDE - http://www.tsp.gatech.edu//concorde/index.html), and includes a few standard heuristics that are already quite fast:
- for the record, the space-filling curve approach takes less than a second and produces a tour 33% larger than the optimal, which is roughly 1573084*4/3=2097445
- the "greedy" heuristic takes less than a second and computes a solution with length 1803479, which is already better than the space-filling curve
- the "quick boruva" heuristic is even faster and produces a solution with length 1789519 (less than 14% larger than optimal)
- the "Lin Kernighan" heuristic takes a few minutes and produces a solution with length 1577339 (less than 0.3% larger than optimal)
So, while this is an interesting application of space-filling curves, it cannot really be considerered to be competitive with the state-of-the-art in TSP heuristics.