TY - JOUR
T1 - A computational comparison of local search heuristics for solving quadratic assigment problems
AU - Pardalos, Panos M.
AU - Murthy, Kowta A.
AU - Harrison, Terry P.
PY - 1993
Y1 - 1993
N2 - It is well known that, in general, exact algorithms for the Quadratic Assignment Problem (QAP) cannot solve problems of size N > 15. Therefore, it is necessary to use heuristic approaches for solving large-scale QAPs. In this paper, we consider a class of heuristic approaches based on local search criteria. In particular, we selected four algorithms; CRAFT, Simulated Annealing, TABU search and the Graph Partitioning (GP) approach and studied their relative performance in terms of the quality of solutions and CPU times. All of these algorithms performed roughly the same, based on the results of two sets of test problems Executed on an IBM ES/3090-600S computer.
AB - It is well known that, in general, exact algorithms for the Quadratic Assignment Problem (QAP) cannot solve problems of size N > 15. Therefore, it is necessary to use heuristic approaches for solving large-scale QAPs. In this paper, we consider a class of heuristic approaches based on local search criteria. In particular, we selected four algorithms; CRAFT, Simulated Annealing, TABU search and the Graph Partitioning (GP) approach and studied their relative performance in terms of the quality of solutions and CPU times. All of these algorithms performed roughly the same, based on the results of two sets of test problems Executed on an IBM ES/3090-600S computer.
UR - http://www.scopus.com/inward/record.url?scp=84974762207&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84974762207&partnerID=8YFLogxK
U2 - 10.3233/INF-1993-41-212
DO - 10.3233/INF-1993-41-212
M3 - Article
AN - SCOPUS:84974762207
SN - 0868-4952
VL - 4
SP - 172
EP - 187
JO - Informatica (Netherlands)
JF - Informatica (Netherlands)
IS - 1-2
ER -