Comparative Performance of Tabu Search and Simulated Annealing Heuristics for the Quadratic Assignment Problem

Sep 4, 2026

Uploaded by Stanley

For nearly two decades, whether tabu search (TS) or simulated annealing (SA) is superior for the quadratic assignment problem has remained unresolved. This study compares their performance across multiple target solution-quality levels, running each heuristic for the optimal number of iterations required to reach each target. Results show SA achieves better outcomes at higher-quality targets, while TS performs better at lower-quality targets across varied problem instances.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages8

Reading Time20 min

AccessFree to download

Introduction

Background

Approach

Performance Metric

arXiv : 1010 .0157v1 [ cs .DS] 1 Oct 2010 Comparative Performance of Tabu Search and Simulated Annealing Heuristics for the Quadratic Assignment Problem Gerald Paul Center for Polymer Studies and Dept. of Physics, Boston University, Boston, MA 02215, USA 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 􀀌nd that for a number of varied problem instances, SA performs better for higher quality targets while TS performs better for lower quality targets. Keywords: Combinatorial optimization, Computing science, Heuristics, Tabu search, Simulated annealing 1. Introduction The quadratic assignment problem (QAP) is a combinatorial optimization problem 􀀌rst introduced by Koopmans and Beckman [12] . It is NPhard and is considered to be one of the most di􀀎 -cult problems to be solved optimally. The problem is de􀀌ned in the following context: A set of N facilities are to be located at N locations. The distance between locations i and j is Di,j and the quantity of materials which 􀀍ow between facilities i and j is Fi,j . The problem is to assign to each location a single facility so as to minimize the cost N N C = X X Fi,j Dp (i),p (j) . i=1 j=1 where p(i) represents the location to which facility i is assigned. There is an extensive literature which addresses the QAP and is reviewed in [19, 7, 2, 11, 13] . With the exception of specially constructed cases, optimal algorithms have solved only relatively small instances (N 􀀔 36) . Various heuristic approaches have been developed and applied to problems typically of size N 􀀙 100 or less. Two of the most successful heuristics to date for the QAP are tabu search (TS) and simulated annealing (SA) . They Email address: [gerryp@bu.edu](gerryp@bu.edu) (Gerald Paul) are basic heuristics which are used alone or as components in hybrid and iterative metaheuristics. Comparisons of the performance of SA and TS for the QAP have been inconclusive. In this work, we are able to successfully characterize the relative performance of these heuristics by performing the comparisons for various values of solution quality and by setting the number of iterations for each heuristic to the optimal one for the target solution quality. As is common practice, we de􀀌ne the quality, Q of a solution C 􀀀 Cbest Q 􀀑 Cbest , where C is the value of the objective function for the solution and Cbest is the best known value of the objective function for the instance. The lower the value of Q, the higher the quality. We 􀀌nd that for each problem instance, there is a value of Q, Q􀀃 , above which (lower quality) tabu search performs better—requires less time—than simulated annealing and below which (higher quality) simulated annealing performs better. 2. Background The tabu search heuristic for the quadratic assignment problem consists of repeatedly swapping locations of two nodes. A single iteration of the heuristic consists of making the swap which most Preprint submitted to Elsevier August 20, 2018 decreases the total cost. Under certain conditions, if a move which lowers the cost is not available, a move which raises the cost is made. To ensure that cycles of the same moves are avoided, the same move is forbidden (taboo) until a speci􀀌ed later iteration; we call this later iteration the eligible iteration for a given move. This eligible iteration is traditionally stored in a tabu list or tabu table. The process is repeated for a speci􀀌ed number of iterations. The simulating annealing heuristic also consists of swapping locations of two facilities. In the simulated annealing approach used here [8], each possible swap is considered in turn and 􀀎, the change in cost for

FAQs

What is the main objective of the comparison between TS and SA?

To determine which heuristic performs better for the quadratic assignment problem by comparing them at various target solution-quality levels with optimal iteration counts.

How is performance compared fairly between tabu search and simulated annealing?

By using a performance metric that accounts for both solution quality and computation time, and by running each heuristic for the optimal number of iterations for each target quality.

Which heuristic is better at higher vs. lower solution quality targets?

For higher-quality targets, simulated annealing performs better; for lower-quality targets, tabu search performs better.

Sep 4, 2026

Uploaded by Stanley