| Revista: | Pesquisa operacional |
| Base de datos: | PERIÓDICA |
| Número de sistema: | 000313063 |
| ISSN: | 0101-7438 |
| Autores: | Boaventura-Netto, Paulo Oswaldo1 |
| Instituciones: | 1Universidade Federal do Rio de Janeiro, Programa de Engenharia de Producao, Rio de Janeiro. Brasil |
| Año: | 2003 |
| Periodo: | Sep-Dic |
| Volumen: | 23 |
| Número: | 3 |
| Paginación: | 283-401 |
| País: | Brasil |
| Idioma: | Inglés |
| Tipo de documento: | Artículo |
| Enfoque: | Experimental |
| Resumen en inglés | 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 |
| Resumen en portugués | 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 |
| Disciplinas: | Matemáticas |
| Palabras clave: | Matemáticas aplicadas, Problema cuadrático de asignación, Combinatoria, Heurística |
| Keyword: | Mathematics, Applied mathematics, Quadratic assignment problem, Combinatorics, Heuristics |
| Texto completo: | Texto completo (Ver HTML) |
