On the performance of heuristics on finite and infinite fractal instances of the Euclidean Traveling Salesman Problem

We show how, by a constructive process, we can generate arbitrarily large instances of the Traveling Salesman Problem (TSP) using standard fractals such as those of Peano, Koch, or Sierpinski. We show that optimal solutions for these TSPs can be known a priori, and thus, they provide us with new nontrivial TSP instances offering the possibility of testing heuristics well beyond the scope of testbed instances which have been solved by exact numerical methods. Furthermore, instances may be constructed with different features, for example, with different fractal dimensions. To four of these fractal TSPs we apply three standard constructive heuristics, namely Multiple Fragment, Nearest Neighbor, and Farthest Insertion from Convex-Hull, which have efficient general-purpose implementations. The ability of different algorithms to solve these different fractal TSPs gives us significant insight into the nature of TSP heuristics in a way which is complementary to approaches such as worst-case or average-case analysis.