Defesa de Mestrado de Raí Caetano de Jesus

Título do Trabalho
Formulações e Algoritmos para o Problema da Poligonização de Área Máxima
Candidato(a)
Raí Caetano de Jesus
Nível
Mestrado
Data
Add to Calender 2018-01-30 00:00:00 2018-01-30 00:00:00 Defesa de Mestrado de Raí Caetano de Jesus Formulações e Algoritmos para o Problema da Poligonização de Área Máxima Sala 85 - IC 2 INSTITUTO DE COMPUTAÇÃO mauroesc@ic.unicamp.br America/Sao_Paulo public
Horário
14:00 h
Local
Sala 85 - IC 2
Orientador(a)
Fabio Luiz Usberti
Banca Examinadora

Titulares  -  Professores Doutores

Unidade/Instituição

Fábio Luiz Usberti

IC/UNICAMP

Pedro Henrique Del Bianco Hokama

DEP/UFScar

Cid Carvalho de Souza

IC/UNICAMP

 

Suplentes  -  Professores Doutores

Unidade/Instituição

Mário César San Felice

IC/UNICAMP

José Federico Vizcaino González

FEG/UNESP

Resumo

O problema do caixeiro viajante euclidiano (Traveling Salesman Problem - TSP) do ponto de vista geométrico tem por objetivo encontrar um polígono simples sobre um dado conjunto de vértices cujo perímetro é mínimo. É possível derivar o problema de modo que o objetivo seja encontrar um polígono simples cuja área interna seja máxima: tal problema é conhecido como Poligonização de Área Máxima (Maximum Area Polygonization - MAXAP). O MAXAP é um problema de otimização combinatória NP-difícil com aplicações práticas em segmentos como reconhecimento de padrões, reconstrução de imagens, clusterização e robótica. Este trabalho propõe novas metodologias de solução e formulações matemáticas para o MAXAP, visando a implementação de algoritmos para metodologias exata, aproximada e heurística, bem como um estudo computacional para avaliar o desempenho das metodologias para o conjunto de instâncias desenvolvido. São propostos neste trabalho dois modelos matemáticos de programação linear inteira, duas heurísticas construtivas, uma metaheurística GRASP e uma matheuristic aplicada sobre um dos modelos matemáticos. Experimentos computacionais foram executados para comparar as metodologias propostas entre si e com um algoritmo 1/2-aproximado da literatura. Análises comparativas de desempenho foram realizadas sobre os resultados obtidos mostrando que o GRASP obteve o melhor desempenho no critério de qualidade das soluções. As heurísticas construtivas propostas por sua vez obtiveram um desempenho superior sobre o algoritmo aproximado. Finalmente, os modelos matemáticos propostos mostram a dificuldade de resolver de maneira exata o MAXAP, encontrando soluções ótimas em uma hora somente para as instâncias de 10 pontos, em um conjunto de instâncias de até 100 pontos.