The Landscape of the Traveling Salesman Problem

Peter F. Stadler, Wolfgang Schnabl

The landscapes of Traveling Salesman Problems are investigated by random walk techniques. The autocorrelation functions for different metrics on the space of tours are calculated. The landscape turns out to be AR(1) for symmetric TSPs. For asymmetric problems there can be a random contribution superimposed on an AR(1) behaviour.

Return to 1992 working papers list.