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

• Processo: 11/18366-6
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de dezembro de 2011
• Data de Término da vigência: 31 de julho de 2012
• Área de 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 Programação linear inteira Heurística Otimização combinatória Controle numérico computadorizado
• Palavra(s)-Chave do Pesquisador: Geometria Computacional | heuristicas | Otimização Combinatória | Problema do recorte com custo nas conversões | programação linear inteira | Otimização Combinatória

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 os 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.(AU)