Busca avançada
Ano de início
Entree

Heurística para o problema do recorte ortogonal discreto com custo nas conversões

Processo: 11/18366-6
Linha de fomento:Bolsas no Brasil - Iniciação Científica
Vigência (Início): 01 de dezembro de 2011
Vigência (Término): 31 de julho de 2012
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Pesquisador responsável:Cid Carvalho de Souza
Beneficiário:Bruno Espinosa Crepaldi
Instituição-sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
Assunto(s):Geometria computacional   Otimização combinatória   Programação linear inteira   Heurística

Resumo

Este projeto de Iniciação Científica tem por objetivo estudar o Problema do Recorte com Custonas Conversões (MTTC), e criar uma heurística para uma de suas variantes conhecida como Problema do Recorte Ortogonal Discreto (ODMP). Neste problema deseja-se encontrar uma curva fechada que, ao ser percorrida por um objeto de formato retangular, cubra todos os pontos de um polígono retilinear dado e, além disso, minimize o custos das conversões efetuadas no percurso.Trata-se de um problema NP-difícil com forte apelo geométrico, e que possui aplicações diversas, como na usinagem de peças metálicas por máquinas de controle numérico, na inspeção automática de produtos, na pintura ou cobertura de superfícies utilizando spray, no roteamento de veículos e até na resolução de origamis matemáticos.