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

DOI10.1007/BF00940812zbMATH Open0534.90091WikidataQ55967971 ScholiaQ55967971MaRDI QIDQ790720FDOQ790720

Authors: V. Černý 

Publication date: 1985

Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)

Recommendations

• The N-City Travelling Salesman Problem: Statistical Mechanics and the Metropolis Algorithm
• Optimization by simulated annealing
• Approximate algorithms for the traveling salesman problem. II
• Traveling Salesman Problem and Statistical Physics
• Travelling salesman problem solved with simulation techniques

zbMATH Keywords

importance samplingapproximate solutionstravelling salesmanMonte Carlo algorithmBoltzmann-Gibbs distributionanalogy with thermodynamics

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Programming involving graphs or networks (90C35) Integer programming (90C10) Classical and relativistic thermodynamics (80A10)

Cited In (only showing first 100 items - show all)

• The Convergence of Markov Chain Monte Carlo Methods: From the Metropolis Method to Hamiltonian Monte Carlo
• An optimization model for minimizing systemic risk
• Discrete-continuous scheduling to minimize the makespan for power processing rates of jobs
• Principle of equivalent microstructure in micromechanics and its connection with the replacement relations. Thermal conductivity problem
• Determining the number of kanbans and lotsizes in a generic kanban system: a simulated annealing approach
• An Improved Simulated Annealing Algorithm with Genetic Characteristics and the Traveling Salesman Problem
• Trends in systolic and cellular computation
• Asymptotic convergence of a simulated annealing algorithm for multiobjective optimization problems
• Variants of the AES key schedule for better truncated differential bounds
• A controlled search simulated annealing method for the single machine weighted tardiness problem
• Quantile and mean value measures of search process complexity
• Simulated annealing for manufacturing systems layout design
• Decentralized multi-level uncapacitated lot-sizing by automated negotiation
• A simulated annealing based solution approach for the two-layered location registration and paging areas partitioning problem in cellular mobile networks
• Hub interdiction problem variants: models and metaheuristic solution algorithms
• A method of spatial reasoning based on qualitative trigonometry
• Global search algorithm for automated maintenance planning and scheduling of parts requests
• Large-scale layout of facilities using a heuristic hybrid algorithm
• Application of heuristic methods for conformance test selection
• Composite stock cutting through simulated annealing
• Probabilistic exchange algorithms and Euclidean traveling salesman problems
• Stochastic local search for the FEATURE SET problem, with applications to microarray data
• A binomial approximation method for the Ising model
• Simulated Simulated Annealing
• A quantitative analysis of the simulated annealing algorithm: A case study for the traveling salesman problem.
• Simulated annealing with noisy or imprecise energy measurements
• Best-so-far vs. where-you-are: Implications for optimal finite-time annealing
• A hybrid simulated annealing approach for single machine scheduling problems with non-regular penalty functions
• A combined multistart-annealing algorithm for continuous global optimization
• Survey: finite-state technology in natural language processing
• A model for the convective cooling of electronic components with application to optimal placement
• The single-finger keyboard layout problem
• Comparison of non-linear optimization algorithms for yield curve estimation
• Simulated annealing with threshold accepting or Tsallis statistics
• Numerical treatment of nonlinear Emden-Fowler equation using stochastic technique
• Calibration of GARCH models using concurrent accelerated random search
• Tabu search for the BWC problem
• Homogeneous grouping of nuclear fuel cans through simulated annealing and tabu search
• Weak convergence of Markov chain sampling methods and annealing algorithms to diffusions
• On the convergence of stationary distributions in simulated annealing algorithms
• Rank aggregation using latent-scale distance-based models
• The physicist's approach to the travelling salesman problem. II
• Golden ratio versus pi as random sequence sources for Monte Carlo integration
• Simulated annealing for the bounds of Kendall's τ and Spearman's ρ
• Local search heuristics for two-stage flow shop problems with secondary criterion
• Equivalent microstructure problem: mathematical formulation and numerical solution
• Approximate solution of a resource-constrained scheduling problem
• Some results characterizing the finite time behaviour of the simulated annealing algorithm.
• A stochastic probing algorithm for global optimization
• An adaptive simulated annealing algorithm for global optimization over continuous variables
• A stopping criterion for logarithmic simulated annealing
• Statistical mechanics methods and phase transitions in optimization problems
• A comparison of heuristic procedures for minimum within-cluster sums of squares partitioning
• Simulated annealing for single minimum optimization problems
• Jet analysis by deterministic annealing
• Stochastic approximation of global minimum points
• Positive role of glassy dynamics in finite-time optimization by threshold algorithms
• On solving the forward kinematics of 3RPR planar parallel manipulator using hybrid metaheuristics
• New approaches for heuristic search: A bilateral linkage with artificial intelligence
• On the statistical detection of clusters in undirected networks
• Simulated annealing versus Metropolis for a TSP instance
• Comparing descent heuristics and metaheuristics for the vehicle routing problem
• MULTISCALE COMPUTATIONS ON NEURAL NETWORKS: FROM THE INDIVIDUAL NEURON INTERACTIONS TO THE MACROSCOPIC-LEVEL ANALYSIS
• VERY STRONGLY CONSTRAINED PROBLEMS: AN ANT COLONY OPTIMIZATION APPROACH
• A fuzzy clustering method of construction of ontology-based user profiles
• Detecting irregular orbits in gravitational N-body simulations
• Randomized algorithms in combinatorial optimization: A survey
• Boolean query optimization and the 0-1 hyperbolic sum problem
• Constructing efficient simulated annealing algorithms
• Metaheuristics approach to the aircrew rostering problem
• Simulated annealing based artificial bee colony algorithm for global numerical optimization
• A computational procedure for part design
• Equation-free multiscale computational analysis of individual-based epidemic dynamics on networks
• Similarities between meta-heuristics algorithms and the science of life
• A heuristic for the label printing problem
• Determining dominant wind directions
• Strategies with memories: Local search in an application oriented environment. Applied local search -- a prologue
• Title not available (Why is that?)
• The museum visitor routing problem
• Determination of initial temperature in fast simulated annealing
• Mathematical and metaheuristic applications in design optimization of steel frame structures: an extensive review
• Efficient simulated annealing based solution approaches to the competitive single and multiple allocation hub location problems
• A simulated annealing algorithm for transient optimization in gas networks
• An asymptotical study of combinatorial optimization problems by means of statistical mechanics
• A direct search variant of the simulated annealing algorithm for optimization involving continuous variables
• The effect of the density of states on the Metropolis algorithm
• New concepts for activity float in resource-constrained project management
• Large-time behavior of perturbed diffusion Markov processes with applications to the second eigenvalue problem for Fokker-Planck operators and simulated annealing
• Solution quality of random search methods for discrete stochastic optimization
• Simulated annealing with extended neighbourhood
• Improving simulated annealing with variable neighborhood search to solve the resource-constrained scheduling problem
• A systematic procedure for setting parameters in simulated annealing algorithms
• Multi-way graph partition by stochastic probe
• Metaheuristics in combinatorial optimization
• Convergence of the simulated annealing algorithm for continuous global optimization
• Optimal annealing schedules for a modified Tsallis statistics
• Simulated annealing procedures for forming machine cells in group technology
• Simulated annealing - to cool or not
• An application of simulated annealing to the cutting stock problem
• Interactive diffusions for global optimization

This page was built for publication: Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q790720)