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

Authors: Silva, AllysonCoelho, Leandro C.Darvish, Maryam
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-ofthe-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
Document Type: Article de recherche
Issue Date: 26 November 2020
Open Access Date: 26 November 2022
Document version: AM
Creative Commons Licence: https://creativecommons.org/licenses/by-nc-nd/4.0
Permalink: http://hdl.handle.net/20.500.11794/68981
This document was published in: European journal of operational research, Vol. 292 (3), 1066-1084 (2021)
https://doi.org/10.1016/j.ejor.2020.11.035
Alternative version: 10.1016/j.ejor.2020.11.035
Collection:Articles publiés dans des revues avec comité de lecture

Files in this item:
Description SizeFormat 
QAPVar.pdf
420.18 kBAdobe PDF    Request a copy
All documents in CorpusUL are protected by Copyright Act of Canada.