| |
| Acadêmico(a): Denise Brandt |
| Título: Distribuição Otimizada de Polígonos em um Plano Bidimensional |
| |
| Introdução: |
Muitas indústrias deparam-se com o desafio de encontrar soluções para o problema de cortar grandes objetos para produzir pedaços menores específicos. O problema de corte consiste em posicionar objetos de formatos diferentes em uma área com dimensões conhecidas a fim de economizar matéria-prima.
Este tipo de problema possui uma enorme gama de aplicação para pesquisa operacional na atualidade. Uma característica marcante é a existência de um grande impacto econômico, pois qualquer decisão tomada significa custos fixos elevados (GOLDBARG; LUNA, 2000, p. 478).
A utilização de ferramentas que realizam a geração de planos de corte é de interesse de indústrias de diversos ramos, como a de móveis, vidros, metais, confecções, espumas, papelões e outras (MARIANO et al., 2009).
Um dos mais importantes aspectos de qualquer rotina de empacotamento automático é o uso de geometria. Isso não é importante apenas por uma perspectiva funcional, mas pode também afetar a qualidade da solução (WHITWELL, 2004, p. 131). Um recurso utilizado para o problema de corte e empacotamento é o conceito de polígono sem encaixe, o qual pode ser usado entre pares de formas para lidar com problemas geométricos. O conceito de polígono sem encaixe pode simplificar significantemente o teste de intersecção entre as duas formas. Este conceito define o caminho que uma forma toma quando está orbitando ao redor de outra forma fixa. Na geração deste caminho, as duas formas sempre se encostam. O polígono gerado a partir desta operação reflete o estado de intersecção entre os dois polígonos (WHITWELL, 2004, p. 129). Pode-se restringir a rotação das formas com o intuito de diminuir a quantidade de rotações, tornando o processo de construção da solução mais rápido.
Diante do exposto, este trabalho desenvolve uma ferramenta que organiza polígonos em um espaço bidimensional, buscando ocupar a menor área possível. Os polígonos podem ser rotacionados de acordo com a parametrização passada para cada problema. São usados algoritmos geométricos para calcular a disposição dos polígonos de forma otimizada. Além disso, são usados algoritmos combinatoriais que buscam uma sequência de polígonos que geram um bom resultado.
|
| |
|
