The landscape of the traveling salesman problem
Physics Letters APublished 1 January 1992
Peter F. Stadler, Wolfgang Schnabl
Citations131
SJR quartileQ2
SJR score0.46
SNIP0.81
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The landscape of traveling salesman problems is investigated by random walk techniques and the autocorrelation functions for different metrics on the space of tours are calculated and turns out to be AR(1) for symmetric TSPs.
Abstract
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.
Keywords
Computer ScienceMathematicsBiochemistry, Genetics and Molecular Biology
Journal of the Franklin InstituteAn introduction to probability theory and its applications
29,966 Citations1958
Journal of the American Statistical AssociationProbability, Random Variables, and Stochastic Processes.
16,350 Citations1984Julia Abrahams, A. Papoulis
Physical Review LettersSolvable Model of a Spin-Glass
4,298 Citations1975David C. Sherrington, Scott Kirkpatrick
Operations ResearchAn Effective Heuristic Algorithm for the Traveling-Salesman Problem
3,797 Citations1973Simon Lin, Brian W. Kernighan
This paper discusses a highly effective heuristic procedure for generating optimum and near-optimum solutions for the symmetric traveling-salesman problem based on a general approach to heuristics that is believed to have wide applicability in combinatorial optimization problems.
The Traveling Salesman Problem
1,622 Citations2019Lawrence Snyder, Zuo‐Jun Max Shen
Lecture notes in economics and mathematical systemsTraveling Salesman Problem
800 Citations1986H. T. Lau
The traveling salesman problem is to start from a node in G, visit every other node exactly once and return back to the starting node in such a way that the total traveled distance is minimum.
Biological CyberneticsCorrelated and uncorrelated fitness landscapes and how to tell the difference
547 Citations1990Ed Weinberger
A framework for the mathematical treatment of multi-peaked “fitness landscapes”, including an explicit mathematical model, is suggested, which might be useful in the “tuning” of combinatorial optimization algorithms, and in modelling in the experimental sciences.
Journal de physiqueConfiguration space analysis of travelling salesman problems
233 Citations1985Scott Kirkpatrick, G. Toulouse
A random distance TSP as similar as possible to the idealized infinite-ranged model of spin glasses, and evidence for freezing due to frustration and for a hierarchical, ultrametric structure of configuration space is presented.
Physical Review ALocal properties of Kauffman’s<i>N</i>-<i>k</i>model: A tunably rugged energy landscape
215 Citations1991Edward D. Weinberger
Biophysical ChemistryA computer model of evolutionary optimization
204 Citations1987Walter Fontana, Peter Schuster
A chemical reaction model which considers RNA replication including correct copying and point mutations together with hydrolytic degradation and the dilution flux of a flow reactor is analysed in order to investigate some basic features of evolutionary optimization dynamics.
ScienceExact Solution of Large Asymmetric Traveling Salesman Problems
173 Citations1991Donald L. Miller, Joseph F. Pekny
The results show that the algorithm performs remarkably well for some classes of problems, determining an optimal solution even for problems with large numbers of cities, yet for other classes, even small problems thwart determination of a provably optimal solution.
Physical review. A, General physicsPhysical aspects of evolutionary optimization and adaptation
124 Citations1989Walter Fontana, Wolfgang Schnabl +1 more
A model of an objective function based on polynucleotide folding is used to investigate the dynamics of evolutionary adaptation in finite populations and represents a realistic example of a highly ``rugged landscape.
Operations Research LettersLarge travelling salesman problems arising from experiments in X-ray crystallography: A preliminary report on computation
120 Citations1989Robert G. Bland, David Shallcross
The Lin-Kernighan heuristic consistently produces near-optimal sequences, and simple TSP heuristics give substantial improvements in utilization at small computational expense.
International Journal of Production ResearchIC insertion: an application of the travelling salesman problem
62 Citations1989Donald Chan, D. Mercier
Chip insertion problems arise naturally in electronic board assembly and are formulated as a travelling salesman problem using the TRAVEL package which provides inexpensive solutions to symmetric problems with less than 300 cities.
OPUS (Augsburg University)Polyedrische Kombinatorik und Schnittebenenverfahren
1 Citations1986Martin Grötschel