All paths through a weighted graph have a number representing the total distance traveled, called the “fitness” of the path. Suppose that each path’s fitness is “plotted” somehow such that the landscape produced can be visualized. Topological maps are used to visualize terrain. What would a similar plot for a traveling salesman problem (TSP) instance in an n-dimensional space look like?

The work reviewed here is an attempt to find out. It is a useful contribution.

The datasets used in the study are instances of the TSP, some taken from TSPLIB and others generated locally, including random instances and real-world instances. The goal of the TSP is to order the data points in such a way that the total distance through a simple closed path connecting all the points is a minimum. The number of such paths is of order (n - 1), a number that grows very rapidly as n increases. For all but small values of n, the number of paths is too large to be searched exhaustively.

The authors propose specialized visualization techniques that incorporate color, size, width, and 3D plots to characterize paths though the landscapes of various TSP instances. Previous studies have proposed “big valley” and “funnel” shapes for such plots. This paper suggests that the situation is much more complex with multiple valleys and funnels. Some instances demonstrate high levels of neutrality and demand new ways of visualization and analysis.