Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/259721
Type: DISSERTAÇÃO
Degree Level: Mestrado
Title: Heuristica e metaheuristicas para o problema de agrupamento capacitado
Author: Maquera Sosa, Nelida Gladys
Advisor: França, Paulo Morelato, 1949-
Abstract: Resumo: As técnicas de agrupamento são aplicadas com diferentes finalidades e necessárias em muitos campos da ciência. No Problema de Agrupamento Capacitado (PAC) são dados objetos que possuem um peso associado que devem ser particionados em agrupamentos com capacidades limitadas. Apresentam-se quatro heurísticas de construção baseadas em pesos e distâncias dos objetos; uma heurística de melhoria que realiza inserções e permutações de objetos e uma aplicação de Busca Tabu (BT) simples. Além disso, é aplicado um mecanismo de abordagem adaptativa de horizonte arbitrário (HTA) baseado em BT que integra as fases de intensificação e diversificação durante a busca. Foram realizados testes computacionais mostrando que HTA obtém soluções de boa qualidade independentemente do ponto de partida e que algoritmos baseados em pesos .dos objetos têm melhor desempenho que algoritmos baseados em distâncias. Aplica-se a mesma metodologia ao Problema de Distritamento Político (PDP) que é um caso particular do PAC. É realizado um estudo preliminar de distritamento da cidade de Campinas dividindo-a em 10 distritos eleitorais. Estes resultados foram obtidos com aplicação da BT, mostrando que este problema pertencente às ciências políticas pode ser tratado pela programação matemática com erros mínimos

Abstract: Clustering techniques can be applied aiming different purposes with applications in severa! fields of science. In the Capacitated Clustering Problem (CCP) objects with distinct weights must be partitioned into clusters with limited capacity. It is presented four constructive heuristics that use weights and distances as optimization criteria. An improvement heuristic that performs insertions and interchanges of objects and a single Tabu Search (TS) application is also proposed. Moreover, it is applied an adaptive mechanism (HTA) based on TS which joins both intensifying and diversifying phases during the search. Computational tests show that HTA attains good quality solutions independent1y from the starting solution. They also show that a!gorithms based on object weights perform better than the ones based on distances. The same methodology is applied to a Political Districting Problem (PDP) which is a particular case of CCP. A preliminary study on the districting of Campinas city has shown that districting plans can be obtained with very reasonable errors
Subject: Análise por agrupamento
Otimização combinatória
Heurística
Distritos eleitorais
Language: Português
Editor: [s.n.]
Date Issue: 1996
Appears in Collections:FEEC - Tese e Dissertação

Files in This Item:
File SizeFormat 
MaqueraSosa_NelidaGladys_M.pdf3.13 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.