Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm

1985/01/01 by V. Černý · 3,406 citations
Mathematics · Physics and Astronomy · #2-opt #Algorithm #Analogy #Bottleneck traveling salesman problem #Combinatorial optimization #Combinatorics #Computer science #Conjecture #Cross-entropy method #Lin–Kernighan heuristic #Mathematical optimization #Mathematics #Monte Carlo method #Opinion Dynamics and Social Influence #Quadratic assignment problem #Simple (philosophy) #Statistical Mechanics and Entropy #Theoretical and Computational Physics #Theory of computation #Travelling salesman problem

paper · doi:10.1007/bf00940812

published in Journal of Optimization Theory and Applications 45(1), 41-51 (Springer Science+Business Media)

openalex publication_date 1985/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Cited by

• Enhanced simulated annealing for globally minimizing functions of many-continuous variables
• An approximate Itô-SDE based simulated annealing algorithm for multivariate design optimization problems
• Scaling Limit for the Diffusion Exit Problem, a Survey
• A Perspective on Conventional High-Temperature Superconductors at High Pressure: Methods and Materials
• Hyper-heuristics: a survey of the state of the art
• New class of compounds - variators - are reprogramming substrate specificity of H4K12Ac, H4K16Ac and H4K20Ac epigenetic marks reading bromodomain of BPTF protein
• Quantum stochastic optimization
• Statistical Algorithms and a Lower Bound for Detecting Planted Clique
• Ant colony optimization theory: A survey
• Gradient Flow from a Random Walk in Hilbert Space
• Position Paper: Towards Transparent Machine Learning
• A Brief Review on Results and Computational Algorithms for Minimizing the Lennard-Jones Potential
• SANA: Simulated Annealing Network Alignment Applied to Biological Networks
• The performance of the quantum adiabatic algorithm on spike Hamiltonians
• A simulated annealing approach to optimal storing in a multi-level warehouse
• An Evolutionary Algorithm for Error-Driven Learning via Reinforcement
• Parallel and Interacting Stochastic Approximation Annealing algorithms for global optimisation
• Mixing time and simulated annealing for the stochastic cellular automata
• The Traveling Salesman and Related Stochastic Problems
• Self-paced Data Augmentation for Training Neural Networks
• Noisy Expectation-Maximization: Applications and Generalizations
• Fractals2019: Combinatorial Optimisation with Dynamic Constraint Annealing
• Finding optimal solutions by stochastic cellular automata
• Black-box optimization using factorization and Ising machines
• Multimodal Optimization by Sparkling Squid Populations
• A Two-step Heuristic for the Periodic Demand Estimation Problem
• Detecting Irregular Orbits in Gravitational N-body Simulations
• Stochastic Annealing for Variational Inference
• A dynamic optimization model for school network planning
• SynC: A Unified Framework for Generating Synthetic Population with Gaussian Copula
• An Approach to the High-level Maintenance Planning for EMU Trains Based on Simulated Annealing
• New class of compounds - variators - are reprogramming substrate specificity of H3K4me3 epigenetic marks reading PHD domain of BPTF protein
• Energy minimization for the flow in ducts and networks
• Vehicle Routing with Drones
• Athos-Graphene: Computational Discovery of an Art-Inspired 2D Carbon Anode for Lithium-Ion Batteries
• Continuous approximation of the Ising Hamiltonian: Exact ground states and applications to fidelity assessment in Ising machines
• Upper bound inequality for calculation time in simulated annealing analogous to adiabatic theorem in quantum systems
• The Thermodynamics of the Travelling Salesman Problem
• Integrating car path optimization with train formation plan: a non-linear binary programming model and simulated annealing based heuristics
• Selective Inference for Latent Block Models
• A Sequential Descent Method for Global Optimization
• An Analysis of a Simple Local Search Algorithm for Graph Colouring
• Generation of high-resolution a priori Y-chromosome phylogenies using “next-generation” sequencing data
• New algorithm for gauge fixing in SU(2) lattice gauge theory
• Convergence of simulated annealing using the generalized transition probability
• Jet analysis by Deterministic Annealing
• Plasticity-rigidity cycles: A general adaptation mechanism
• Simulated annealing — to cool or not
• Cooling down Lévy flights
• Genetic algorithms and supernovae type Ia analysis
• Search for the PN coefficients for the Energy flux through Gravitational Waves from Black-Hole Binaries using Markov Chain Monte Carlo
• Optimization by record dynamics
• Ultrametricity for physicists
• The Impact of Move Schemes on Simulated Annealing Performance
• Multicriteria global optimization for biocircuit design
• Mpemba Index and Anomalous Relaxation
• Density functionals and Kohn-Sham potentials with minimal wavefunction preparations on a quantum computer
• Machine-learning-based sampling method for exploring local energy minima of interstitial species in a crystal
• Magnetic straintronics: Manipulating the magnetization of magnetostrictive nanomagnets with strain for energy-efficient applications
• Efficient Post-Processors for Improving Error-Correcting Performance of LDPC Codes
• Planning a Sequence of Base Positions for a Mobile Manipulator to Perform Multiple Pick-and-Place Tasks
• Theory of Quantum Annealing of an Ising Spin Glass
• Modeling brain dynamics using computational neurogenetic approach. [europepmc]
• A hybrid approach to protein folding problem integrating constraint programming with local search. [europepmc]
• Synthesis of a novel fluorescent sensor bearing dansyl fluorophores for the highly selective detection of mercury (II) ions. [europepmc]
• Dual-phase evolution in complex adaptive systems. [europepmc]
• Investigation of spectral interferences on the accuracy of broadband CW-NIRS tissue SO(2) determination. [europepmc]
• Multicriteria global optimization for biocircuit design. [europepmc]
• SubClonal Hierarchy Inference from Somatic Mutations: Automatic Reconstruction of Cancer Evolutionary Trees from Multi-region Next Generation Sequencing. [europepmc]
• List-Based Simulated Annealing Algorithm for Traveling Salesman Problem. [europepmc]
• Signatures of a globally optimal searching strategy in the three-dimensional foraging flights of bumblebees. [europepmc]
• Structure Prediction of RNA Loops with a Probabilistic Approach. [europepmc]
• Numerical algebraic geometry for model selection and its application to the life sciences. [europepmc]
• graph-GPA: A graphical model for prioritizing GWAS results and investigating pleiotropic architecture. [europepmc]
• Molecular Dynamics Simulations of the [2Fe-2S] Cluster-Binding Domain of NEET Proteins Reveal Key Molecular Determinants That Induce Their Cluster Transfer/Release. [europepmc]
• The mechanisms of crystal growth inhibition by organic and inorganic inhibitors. [europepmc]
• Phoenics: A Bayesian Optimizer for Chemistry. [europepmc]
• Optimal Coarse-Grained Site Selection in Elastic Network Models of Biomolecules. [europepmc]
• Optimizing Selection of the Reference Population for Genotype Imputation From Array to Sequence Variants. [europepmc]
• Prediction of Hydrophobic Reagent for Flotation Process Using Molecular Modeling. [europepmc]
• A Comparison of Metaheuristic Optimization Algorithms for Scale Short-Form Development. [europepmc]
• An Information-Theory-Based Approach for Optimal Model Reduction of Biomolecules. [europepmc]
• Uncertainty Quantification of Regional Cardiac Tissue Properties in Arrhythmogenic Cardiomyopathy Using Adaptive Multiple Importance Sampling. [europepmc]
• Green inhibitor of carbon steel corrosion in 1 M hydrochloric acid: Eruca sativa seed extract (experimental and theoretical studies). [europepmc]
• Current Approaches for Image Fusion of Histological Data with Computed Tomography and Magnetic Resonance Imaging. [europepmc]
• State-of-the-Art on Brain-Computer Interface Technology. [europepmc]
• Artificial intelligence-based screening for amblyopia and its risk factors: comparison with four classic stereovision tests. [europepmc]