Last Name :  
Member ID :  
Password :
Forgot Password?
  You are logged in as Guest Home Contact Us Tech Support ETocS My Journal/Searches Help
  INFORMS Homepage
  Editor-in-Chief Homepage
  Society link
  PubsOnLine - Library Access
  INFORMS Publications
  Copyright and Permissions
   
  Journals
Decision Analysis
Information Systems Research
INFORMS Journal on Computing
Interfaces
Management Science
Manufacturing and Service Operations Management
Marketing Science
Mathematics of Operations Research
Operations Research
Organization Science
Transportation Science
International Abstracts in Operations Research
  Electronic Journal
INFORMS Transactions on Education
  Membership Magazines
OR/MS Today
Analytics
OR/MS Tomorrow
  Request for Subscription
   




 
 
 
 

INFORMS Journal on Computing
 
     
  Volume Number 2   Issue Number 1   First Page 33   Last Page 45   Cover Date December 01, 1990

 
 
 
Email to a friend

Add to Favorites

Full Text

Abstract PDF
 
 
     
  Tabu Search Applied to the Quadratic Assignment Problem
Jadranka Skorin-Kapov
 
 

This paper describes an adaptation of Tabu Search, a recent technique to overcome local optimality, to the Quadratic Assignment Problem (QAP). Computational experiments with different parameter values and different strategies have been performed for some QAPs from the literature and some randomly generated QAPs of dimensions varying between 42 and 90. The method is implemented in a flexible form which allows the user to interact and change the parameters (tabu list size, the iteration limit, a search diversification parameter and the number of new starting solutions) during the run. The results suggest that good tabu list sizes increase with dimension of the problem. The algorithm appears to be a very efficient method for QAPs: for the standard problems tested, the best known solutions were obtained using less CPU time than previously reported in the literature. For Steinberg's problem (n = 36) with rectangular distances, a better solution than previously known in the literature was obtained. In addition, in comparison with simulated annealing, tabu search appears to be superior with respect to the solution quality.

 
   

   
   
   
     
  Featured Sites
 
 
Copyright © Informs 2008. All rights reserved.