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
• MULTISCALE COMPUTATIONS ON NEURAL NETWORKS: FROM THE INDIVIDUAL NEURON INTERACTIONS TO THE MACROSCOPIC-LEVEL ANALYSIS
• 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
• Equation-free multiscale computational analysis of individual-based epidemic dynamics on 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
• 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
• A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem
• ParadisEO-MO: from fitness landscape analysis to efficient local search algorithms
• A comparison of general-purpose optimization algorithms for finding optimal approximate experimental designs
• Local search algorithms for political districting
• CHAOS SYNTHESIS BY MEANS OF EVOLUTIONARY ALGORITHMS
• A hybrid SAGA algorithm for the construction of \(E(s^2)\)-optimal cyclic supersaturated designs
• On the Weibull cost estimation of building frames designed by simulated annealing
• Selective inference for latent block models
• The generation of random equilateral polygons
• Traveling solitary waves for doubly-resonant media: computation via simulated annealing
• Selected topics on assignment problems
• A probabilistic construction of model validation
• Improving the performance of metaheuristics: an approach combining response surface methodology and racing algorithms
• Allocation search methods for a generalized class of location-allocation problems
• A dual latent class unfolding model for two-way two-mode preference rating data
• Genetic local search for multicast routing with pre-processing by logarithmic simulated annealing
• Forecasting nonstationary time series based on Hilbert-Huang transform and machine learning
• Local search and lower bounds for the patient admission scheduling problem
• Title not available (Why is that?)
• A latent class multidimensional scaling model for two-way one-mode continuous rating dissimilarity data
• Large-step Markov chains for the TSP incorporating local search heuristics
• Estimating the parameters of a Gompertz-type diffusion process by means of simulated annealing
• HSAGA and its application for the construction of near-Moore digraphs
• Models and algorithms for the heterogeneous dial-a-ride problem with driver-related constraints
• A theoretical framework for simulated annealing
• A genetic algorithm methodology for complex scheduling problems
• On the classification of NP-complete problems in terms of their correlation coefficient
• A nested simulated annealing algorithm
• Heuristic algorithms for the maximum diversity problem
• Stochastic techniques for global optimization: A survey of recent advances
• \(E(s^{2})\)-optimal and minimax-optimal cyclic supersaturated designs via multi-objective simulated annealing
• Stratified sampling for the Ising model: A graph-theoretic approach
• Cost analysis of alternative formulations for personnel scheduling in continuously operating organizations
• Improvement heuristics for the vehicle routing problem based on simulated annealing
• The application of the simulated annealing algorithm to the solution of the \(n/m/C_{\max}\) flowshop problem
• General local search methods
• A survey on optimization metaheuristics
• A new hybrid descent method with application to the optimal design of finite precision FIR filters
• Design of automated negotiation mechanisms for decentralized heterogeneous machine scheduling
• A selective adaptive large neighborhood search heuristic for the profitable tour problem with simultaneous pickup and delivery services
• Monte Carlo hyper-heuristics for examination timetabling
• Nature's way of optimizing
• Heuristics for multi-attribute vehicle routing problems: a survey and synthesis
• Simulated annealing metaheuristics for the vehicle routing problem with time windows
• Ant colony optimization theory: a survey
• A hybrid vendor managed inventory and redundancy allocation optimization problem in supply chain management: an NSGA-II with tuned parameters
• Simulated annealing for the machine reassignment problem
• Methods for the one-dimensional space allocation problem
• Good solutions to discrete noxious location problems via metaheuristics
• Simulated annealing for financing cost distribution based project payment scheduling from a joint perspective

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)