Effective heuristics and meta-heuristics for the quadratic assignment problem with tuned parameters and analytical comparisons

Artikel

Quadratic assignment problem (QAP) is a well-known problem in the facility location and layout. It belongs to the NP-complete class. There are many heuristic and meta-heuristic methods, which are presented for QAP in the literature. In this paper, we applied 2-opt, greedy 2-opt, 3-opt, greedy 3-opt, and VNZ as heuristic methods and tabu search (TS), simulated annealing, and particle swarm optimization as meta-heuristic methods for the QAP. This research is dedicated to compare the relative percentage deviation of these solution qualities from the best known solution which is introduced in QAPLIB. Furthermore, a tuning method is applied for meta-heuristic parameters. Results indicate that TS is the best in 31%of QAPs, and the IFLS method, which is in the literature, is the best in 58 % of QAPs; these two methods are the same in 11 % of test problems. Also, TS has a better computational time among heuristic and meta-heuristic methods.

Angaben zum Objekt

• Sprache: Englisch

Verweise und Beziehungen

• Erschienen in: Journal: Journal of Industrial Engineering International ; ISSN: 2251-712X ; Volume: 8 ; Year: 2012 ; Pages: 1-9 ; Heidelberg: Springer

Klassifikation und Themen

• Klassifikation: Management
• Thema: quadratic assignment problem ; heuristics ; meta-heuristics ; tuning method

Beteiligte, Orts- und Zeitangaben

• Ereignis: Geistige Schöpfung
• (wer): Bashiri, Mahdi ; Karimi, Hossein
• Ereignis: Veröffentlichung
• (wer): Springer
• (wo): Heidelberg
• (wann): 2012

Weitere Informationen

• DOI: doi:10.1186/2251-712X-8-6
• Handle: http://hdl.handle.net/10419/78571
• Letzte Aktualisierung: 10.03.2025, 11:44 MEZ