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

Auteur(s): Silva, AllysonCoelho, Leandro C.Darvish, Maryam
Résumé: 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
Type de document: Article de recherche
Date de publication: 26 novembre 2020
Date de la mise en libre accès: 26 novembre 2022
Version du document: AM
Licence Creative Commons: https://creativecommons.org/licenses/by-nc-nd/4.0
Lien permanent: http://hdl.handle.net/20.500.11794/68981
Ce document a été publié dans: European journal of operational research, Vol. 292 (3), 1066-1084 (2021)
https://doi.org/10.1016/j.ejor.2020.11.035
Autre version disponible: 10.1016/j.ejor.2020.11.035
Collection :Articles publiés dans des revues avec comité de lecture

Fichier(s) :
Description TailleFormat 
QAPVar.pdf
420.18 kBAdobe PDF    Demander une copie
Tous les documents dans CorpusUL sont protégés par la Loi sur le droit d'auteur du Canada.