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

DC FieldValueLanguage
dc.contributor.authorSilva, Allyson-
dc.contributor.authorCoelho, Leandro C.-
dc.contributor.authorDarvish, Maryam-
dc.description.abstractIn 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 literaturefr
dc.subjectHybrid metaheuristicfr
dc.subjectTabu searchfr
dc.subjectParallel computingfr
dc.titleQuadratic assignment problem variants : a survey and an effective parallel memetic iterated tabu searchfr
dc.typeCOAR1_1::Texte::Périodique::Revue::Contribution à un journal::Article::Article de recherchefr
dcterms.bibliographicCitationEuropean journal of operational research, Vol. 292 (3), 1066-1084 (2021)fr
dc.subject.rvmRecherche avec tabousfr
dc.subject.rvmProblème d'affectation quadratiquefr
rioxxterms.versionAccepted Manuscriptfr
rioxxterms.project2019-00094 ; 2020-00401fr
rioxxterms.project.funder_nameNatural Sciences and Engineering Research Council of Canada (NSERC)fr
ali.license_refAttribution - Pas d'Utilisation Commerciale - Pas de Modification CC BY-NC-NDfr
bul.rights.periodeEmbargo24 moisfr
Collection:Articles publiés dans des revues avec comité de lecture

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