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

AUTOR(ES)

Boaventura-Netto, Paulo Oswaldo

FONTE

Pesquisa Operacional

DATA DE PUBLICAÇÃO

2003-12

RESUMO

Este trabalho discute o uso de uma estrutura de vizinhança em heurísticas específicas para o Problema Quadrático de Alocação (PQA). Esta estrutura envolve os ciclos de comprimento 4 e 6 adjacentes a um vértice do diagrama de Hasse do reticulado das permutações e pode ser particionada em subconjuntos de cardinalidade linear e quadrática em relação à ordem da instância, o que permite frequentemente uma economia de tempo de processamento. Propõem-se ainda uma estratégia de repartida e um mecanismo de geração de soluções iniciais, que constituem, ao lado da estrutura de vizinhança, uma proposta de heurística específica para o PQA. Na construção desses instrumentos foi utilizada a noção de conjunto relaxado ordenado das soluções do PQA.

ASSUNTO(S)

problema quadrático de alocação combinatória heurísticas

Documentos Relacionados

• An experimental study of variable depth search algorithms for the quadratic assignment problem
• An efficient hybrid heuristic method for the 0-1 exact k-item quadratic knapsack problem
• A heuristic for the minimization of open stacks problem
• A HYBRID HEURISTIC ALGORITHM FOR THE CLUSTERED TRAVELING SALESMAN PROBLEM
• A MODEL-BASED HEURISTIC FOR THE IRREGULAR STRIP PACKING PROBLEM