Combinatorial instruments in the design of a heuristic for the quadratic assignment problem

Pesquisa Operacional

Paulo Oswaldo Boaventura-netto¹ 

[1] ,Université de Versailles à St. Quentin-en-Yvelines Laboratoire PriSM ,França

关键词: quadratic assignment problem;    combinatory;    heuristics;    problema quadrático de alocação;    combinatória;    heurísticas;   

DOI  :  10.1590/S0101-74382003000300001

来源: SciELO

【 摘 要 】

This work discusses the use of a neighbouring structure in the design of specific heuristics for the Quadratic Assignment Problem (QAP). This structure is formed by the 4- and 6-cycles adjacent to a vertex in the Hasse diagram of the permutation lattice and it can be adequately partitioned in subsets of linear and quadratic cardinalities, a characteristics which frequently allows an economy in the processing time. We propose also a restart strategy and a mechanism for generating initial solutions which constitute, together with the neighbouring structure, a possible QAP-specific heuristic proposal. For the construction of these instruments we used the relaxed ordered set of QAP solutions.

【 授权许可】

CC BY   
 All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License