Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm
From MaRDI portal
We present a Monte Carlo algorithm to find approximate solutions of the travelling salesman problem. The algorithm generates randomly the permutations of the stations of the travelling salesman trip, with probability depending on the length of the corresponding route. Reasoning by analogy with statistical thermodynamics, we use the probability given by the Boltzmann-Gibbs distribution. Surprisingly enough, using this simple algorithm, one cat get very close to the optimal solution of the problem or even find the true optimum. We demonstrate this on several examples. We conjecture that the analogy with thermodynamics can offer a new insight into optimization problems and can suggest efficient algorithms for solving them.
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
Cited in
(only showing first 100 items - show all)- Global search algorithm for automated maintenance planning and scheduling of parts requests
- Stochastic protein folding simulation in the three-dimensional HP-model
- Approximate solution of a resource-constrained scheduling problem
- Comparison of non-linear optimization algorithms for yield curve estimation
- Allocation search methods for a generalized class of location-allocation problems
- The single-finger keyboard layout problem
- A fuzzy clustering method of construction of ontology-based user profiles
- A latent class multidimensional scaling model for two-way one-mode continuous rating dissimilarity data
- Randomized algorithms in combinatorial optimization: A survey
- Probabilistic exchange algorithms and Euclidean traveling salesman problems
- On the convergence of stationary distributions in simulated annealing algorithms
- Simulated annealing with noisy or imprecise energy measurements
- New approaches for heuristic search: A bilateral linkage with artificial intelligence
- Boltzmann machines for travelling salesman problems
- An application of simulated annealing to the cutting stock problem
- A method of spatial reasoning based on qualitative trigonometry
- Modified simulated annealing algorithms for the flow shop sequencing problem
- Trends in systolic and cellular computation
- A stochastic probing algorithm for global optimization
- Composite stock cutting through simulated annealing
- Large-step Markov chains for the TSP incorporating local search heuristics
- The afforestation problem: A heuristic method based on simulated annealing
- Stochastic techniques for global optimization: A survey of recent advances
- Scheduling with neural networks -- the case of the Hubble Space Telescope
- A computational procedure for part design
- A hybrid simulated annealing approach for single machine scheduling problems with non-regular penalty functions
- Simulated annealing - to cool or not
- General local search methods
- Determining dominant wind directions
- Discrete-continuous scheduling to minimize the makespan for power processing rates of jobs
- Fuzzy rule base learning through simulated annealing
- The stochastic traveling salesman problem: finite size scaling and the cavity prediction
- Best-so-far vs. where-you-are: Implications for optimal finite-time annealing
- Bin-packing by simulated annealing
- Simulated annealing procedures for forming machine cells in group technology
- Large-scale layout of facilities using a heuristic hybrid algorithm
- Stochastic approximation of global minimum points
- Simulated annealing and tabu search approaches to unidirectional flowpath design for automated guided vehicle systems
- Homogeneous grouping of nuclear fuel cans through simulated annealing and tabu search
- DSS for multiobjective project scheduling
- Boolean query optimization and the 0-1 hyperbolic sum problem
- Scaling features in complex optimization problems
- Constructing efficient simulated annealing algorithms
- Modelling constant weight codes using tabu search
- Job-shop scheduling: Computational study of local search and large-step optimization methods
- Simulated annealing for manufacturing systems layout design
- A systematic procedure for setting parameters in simulated annealing algorithms
- Cost analysis of alternative formulations for personnel scheduling in continuously operating organizations
- Improvement heuristics for the vehicle routing problem based on simulated annealing
- Simulated annealing for complex portfolio selection problems.
- Product line selection and pricing under a share-of-surplus choice model.
- Solving the continuous flow-shop scheduling problem by metaheuristics.
- Convergence of the simulated annealing algorithm for continuous global optimization
- Nature's way of optimizing
- The discrete lot-sizing and scheduling problem: Complexity and modification for batch availability
- Heuristics for cardinality constrained portfolio optimization
- P-vortices and drama of Gribov copies
- Local search algorithms for the multiprocessor flow shop scheduling problem
- Modeling distributed concept representation in Hopfield neural networks.
- Optimal annealing schedules for a modified Tsallis statistics
- On the statistical detection of clusters in undirected networks
- A comparison of simulated annealing algorithms for variable selection in principal component analysis and discriminant analysis
- Equivalent microstructure problem: mathematical formulation and numerical solution
- Solving multifacility Huff location models on networks using metaheuristic and exact approaches
- A variable neighborhood search and simulated annealing hybrid for the profile minimization problem
- Efficient simulated annealing based solution approaches to the competitive single and multiple allocation hub location problems
- On selection of statistics for approximate Bayesian computing (or the method of simulated moments)
- A simulated annealing algorithm for the capacitated vehicle routing problem with two-dimensional loading constraints
- Identification of effective implementations of simulated annealing for optimizing thinning schedules for single forest stands
- The air traffic controller work-shift scheduling problem in Spain from a multiobjective perspective: a metaheuristic and regular expression-based approach
- Revisiting simulated annealing: a component-based analysis
- Variants of the AES key schedule for better truncated differential bounds
- A modified cloud particles differential evolution algorithm for real-parameter optimization
- A computational approach inspired by simulated annealing to study the stability of protein interaction networks in cancer and neurological disorders
- Quantile and mean value measures of search process complexity
- Monte Carlo hyper-heuristics for examination timetabling
- Development of a fuel consumption optimization model for the capacitated vehicle routing problem
- Simulated annealing and tabu search for multi-mode resource-constrained project scheduling with positive discounted cash flows and different payment models
- Hybrid heuristics for examination timetabling problem
- Solution quality of random search methods for discrete stochastic optimization
- Two simulated annealing-based heuristics for the job shop scheduling problem
- Some new results on simulated annealing applied to the job shop scheduling problem
- On efficient use of simulated annealing in complex structural optimization problems
- Quantum stochastic optimization
- Simulated annealing with threshold accepting or Tsallis statistics
- Application of heuristic methods for conformance test selection
- Threshold accepting as limit case for a modified Tsallis statistics
- Comparison of metaheuristic algorithms for examination timetabling problem
- Joint determination of machine cells and linear intercell layout
- An adaptive simulated annealing algorithm for global optimization over continuous variables
- Strategies with memories: Local search in an application oriented environment. Applied local search -- a prologue
- Easily searched encodings for number partitioning
- Divide and conquer strategies for parallel TSP heuristics
- Simulated annealing metaheuristics for the vehicle routing problem with time windows
- Combining simulated annealing with local search heuristics
- Focused simulated annealing search: An application to job shop scheduling
- Genetic algorithms for the traveling salesman problem
- Metaheuristics: A bibliography
- The construction of antipodal triple systems by simulated annealing
- Tabu search for the BWC problem
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)
