Quadratic assignment problem variants: A survey and an effective parallel memetic iterated tabu search

Allyson Silva, Leandro C. Coelho and Maryam Darvish

European Journal of Operational Research, 2021, vol. 292, issue 3, 1066-1084

Abstract: In the Quadratic Assignment Problem (QAP), facilities are assigned to sites in order to minimize interactions between pairs of facilities. Although easy to define, it is among the hardest problems in combinatorial optimization, due to its non-linear nature. After decades of research on the QAP, many variants of this problem arose to deal with different applications. Along with the QAP, we consider four variants – the Quadratic Bottleneck Assignment Problem, the Biquadratic Assignment Problem, the Quadratic Semi-Assignment Problem, and the Generalized QAP – and develop a single framework to solve them all. Our parallel memetic iterated tabu search (PMITS) extends the most successful heuristics to solve the QAP. It combines the diversification phase of generating new local optima found after solutions modified by a new crossover operator that is biased towards one of the parents, with the intensification phase of an effective tabu search which uses a simplified tabu list structure to reduce the number of parameters and a new long-term memory that saves solutions previously visited to speed up the search. Solutions are improved concurrently using parallelism, and a convergence criterion determines whether the search stops according to the best solutions in each parallel search. Computational experiments using the hardest benchmark instances from the literature attest the effectiveness of the PMITS, showing its competitiveness when compared to the state-of-the-art methods, sequential and parallel, to solve the QAP. We also show that PMITS significantly outperforms the best methods found for all four variants of the QAP, significantly updating their literature.

Keywords: Assignment; Survey; Hybrid metaheuristic; Tabu search; Parallel computing (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720309814
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:292:y:2021:i:3:p:1066-1084

DOI: 10.1016/j.ejor.2020.11.035

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().