Spacefilling curves and the planar travelling salesman problem

Reviewer: Benjamin L. Schwartz

For the travelling salesman problem (TSP) on <__?__Pub Fmt italic>N<__?__Pub Fmt /italic> cities the authors introduce a heuristic based on space-filling curves. They claim this is the first combinatorial application of fractal geometry. In practice, they implement the heuristic with finite precision. Cities on the tour are visited in the order that the space-filling curve encounters the points (or their finitely truncated approximations). The curve chosen preserves Euclidean closeness (it is continuous and “almost” invertible) and is homogeneous: subcurves of equal arc length fill regions of equal area. The algorithm is amenable to solution in <__?__Pub Fmt italic>O<__?__Pub Fmt /italic>(<__?__Pub Fmt italic>N<__?__Pub Fmt /italic> log <__?__Pub Fmt italic>N<__?__Pub Fmt /italic>) operations. This is highly efficient in competition with other proposed TSP heuristics. The results obtained are competitive with the nearest neighbor and spanning tree heuristic algorithms for TSP. A theoretical statistical analysis based on exact distribution, without truncation, establishes very tight bounds on the ratio of the expected length of the heuristic solution<__?__Pub Caret> to the optimal length. For a uniformly distributed set of cities, the optimal tour may be 25 to 35 percent shorter than the one given by the space-filling heuristic. For general (deterministic) location of cities, the ratio of the heuristic length <__?__Pub Fmt italic>L<__?__Pub Fmt /italic> to the optimal length <__?__Pub Fmt italic>L<__?__Pub Fmt /italic>* satisfies <__?__Pub Fmt italic>L<__?__Pub Fmt /italic>/<__?__Pub Fmt italic>L<__?__Pub Fmt /italic>* = <__?__Pub Fmt italic>O<__?__Pub Fmt /italic>(log <__?__Pub Fmt italic>N<__?__Pub Fmt /italic>), a relation that is known to be sharp. Large <__?__Pub Fmt italic>L<__?__Pub Fmt /italic>/<__?__Pub Fmt italic>L<__?__Pub Fmt /italic>* can occur only when both variables are relatively small, since L?2 N .