Comparative performance of tabu search and simulated annealing heuristics for the quadratic assignment problem

DOI10.1016/J.ORL.2010.09.009MaRDI QIDQ614047zbMATH OpenOpenAlexFDO

Authors Gerald Paul

Publication date 23 December 2010

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1010.0157

zbMATH Keywords

combinatorial optimizationcomputing scienceheuristicssimulated annealingtabu search

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: For almost two decades the question of whether tabu search (TS) or simulated annealing (SA) performs better for the quadratic assignment problem has been unresolved. To answer this question satisfactorily, we compare performance at various values of targeted solution quality, running each heuristic at its optimal number of iterations for each target. We find that for a number of varied problem instances, SA performs better for higher quality targets while TS performs better for lower quality targets.

Recommendations

• Tabu search vs. simulated annealing as a function of the size of quadratic assignment problem instances
• scientific article; zbMATH DE number 1532439
• Simulated annealing and tabu search in the long run: A comparison on QAP tasks
• Heuristics for the generalised assignment problem: Simulated annealing and tabu search approaches
• Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem
• scientific article; zbMATH DE number 2112207
• Tabu Search Applied to the Quadratic Assignment Problem
• Comparison of tabu/2-opt heuristic and optimal tree search method for assignment problems
• A tabu search algorithm for the quadratic assignment problem
• Extensions of a tabu search adaptation to the quadratic assignment problem

Cites work

• A survey for the quadratic assignment problem
• A tabu search algorithm for the quadratic assignment problem
• An improved annealing scheme for the QAP
• Assignment Problems and the Location of Economic Activities
• scientific article; zbMATH DE number 124500 (Why is no real title available?)
• scientific article; zbMATH DE number 1203289 (Why is no real title available?)
• scientific article; zbMATH DE number 714526 (Why is no real title available?)
• scientific article; zbMATH DE number 714533 (Why is no real title available?)
• scientific article; zbMATH DE number 2112207 (Why is no real title available?)
• Probability distribution of solution time in GRASP: an experimental investigation
• QAPLIB - a quadratic assignment problem library
• Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods
• Recent advances in the solution of quadratic assignment problems
• Simulated annealing and tabu search in the long run: A comparison on QAP tasks
• Solving large quadratic assignment problems on computational grids
• Tabu Search Applied to the Quadratic Assignment Problem
• The quadratic assignment problem. Theory and algorithms

Cited in

(9)

• Algodesk: An experimental comparison of eight evolutionary heuristics applied to the quadratic assignment problem
• Simulated annealing and tabu search in the long run: A comparison on QAP tasks
• Fast simulated annealing for single-row equidistant facility layout
• Revisiting simulated annealing: a component-based analysis
• Heuristics for the generalised assignment problem: Simulated annealing and tabu search approaches
• Tabu search vs. simulated annealing as a function of the size of quadratic assignment problem instances
• scientific article; zbMATH DE number 1532439 (Why is no real title available?)
• Comparative study of simulated annealing, genetic algorithms and tabu search for solving binary and comprehensive machine-grouping problems
• An experimental study of variable depth search algorithms for the quadratic assignment problem

Describes a project that uses

Uses Software

• QAPLIB
• Algorithm 769

This page was built for publication: Comparative performance of tabu search and simulated annealing heuristics for the quadratic assignment problem

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