92-01-003
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.