Um Algoritmo Baseado no Teorema das Inversões
com Path Relinking para o Problema o Quadrático de Alocação
Nome: CARLOS JONES REBELLO JUNIOR
Tipo: Dissertação de mestrado acadêmico
Data de publicação: 09/12/2013
Banca:
Nome |
Papel |
|---|---|
| LEANDRO COLOMBI RESENDO | Examinador Externo |
| MARIA CLAUDIA SILVA BOERES | Examinador Interno |
| MARIA CRISTINA RANGEL | Orientador |
Resumo: Quando o aluno enviar o resumo substituir.
O Problema Quadrático de Alocação (PQA) foi introduzido inicialmente por Koopmans e Beckmann em 1957 [14] no contexto de localização de atividades econômicas cujo objetivo era a determinação de uma alocação ótima para pares de atividades e localidades, tendo-se como
dados conhecidos as distâncias entre as localidades e o uxo entre as atividades. Trata-se de um problema de Lay-Out, como por exemplo, a disposição de componentes eletrônicos em uma placa de circuito impresso, proposta por Steinberg [7], a otimização de teclas de máquinas de escrever, proposto por McCormick [5] e a localização de departamentos de um hospital de Cairo no Egito, proposto por Elshafei [2]. O PQA é um problema pertencente a classe NP-Hard, onde instâncias de ordem 25 já são consideradas de grande porte, mesmo para a tecnologia avançada existente, desaando a ciência rincipalmente pela diculdade computacional na determinação de soluções ótimas e/ou viáveis de boa qualidade. Algumas contribuições algébricas para o PQA podem ser encontradas nos trabalhos desenvolvidos por Abreu [10] e Rangel [9]. Um conhecimento sólido da teoria na qual o problema está inserido é importante quando se deseja propor técnicas para sua resolução. As principais técnicas de resolução para este problema fazem uso de heurísticas e metaheur
ísticas, e como referência para testes de eciência destes algoritmos a QAPLIB [12], que é uma coletânea de instâncias com valores ótimos e/ou melhores valores conhecidos até o momento para o PQA, é a mais conhecida e utilizada. Como exemplo de técnicas metaheur
ística podemos citar a busca tabu proposta por Misevicius [1] para melhorar o resultado da instância Tai80a da QAPLIB [12], o simulated anneling proposto por Abreu et al. [11] usando a redução do número de inversões de permutações associadas ao PQA. Podemos citar ainda
Brown et al. [4] e Gong et al. [3] com propostas de Algoritmo Genético, apesar deste método apresentar diculdades na obtenção de soluções ótimas mesmo para instâncias de pequeno porte. Como exemplo de heurísticas podemos citar os métodos construtivos introduzidos por Gilmore [13] e Resendo [8]. Loiola et al. [6] arma que a utilização de outras técnicas juntamente com os algoritmos genéticos, os chamados algoritmos híbridos, mostraram-se mais
promissoras. As seções seguintes apresentam os objetivos deste projeto de dissertação, a base teórica para a proposta, as etapas do desenvolvimento da pesquisa, um cronograma e as referências
básicas sobre o tema.
