Anais do Simpósio Brasileiro de Pesquisa Operacional
Anais do Simpósio Brasileiro de Pesquisa Operacional

Problemas de empacotamento irregular compõem uma classe de desafios de otimização que buscam determinar a posição (layout) de peças irregulares sobre um objeto, visando minimizar o espaço ocupado. Visto a complexidade combinatória intrínseca dessa situação, além da dificuldade em eliminar sobreposições entre as peças e mantê-las no interior do objeto, este trabalho tem como proposta a utilização de aprendizado por reforço como alternativa para busca de soluções, onde, na modelagem deste problema: o ambiente é o objeto; as peças são as ações; e a posição das peças sobre o objeto é a posição. Para isso, será utilizada uma variação do algoritmo Q-learning, onde a matriz Qi, j é substituída por um tensor Qn, i, j, onde n representa o número de peças a serem alocadas, i a discretização do objeto no eixo x, e j a discretização no eixo y. Dessa forma, a verificação de factibilidade de uma solução será facilitada, pois basta somar os valores de cada entrada i e j de uma submatriz com a de outra; se o resultado for diferente de ambas as entradas, então há sobreposição. Portanto, devido ao fato das submatrizes qi, j do tensor Qn, i, j serem maiores do que é tradicionalmente encontrado na literatura, além de serem dependentes entre si, esse método é computacionalmente custoso, porém são esperados resultados muito satisfatórios em comparação com os já existentes. Os resultados preliminares obtidos ainda não são ótimos, porém isso apenas indica que ainda há ampla possibilidade para trabalhos futuros. A técnica de representação utilizada, circle covering, auxiliou também na obtenção dos resultados. Para metrificar a solução obtida, foi calculada a razão entre a área do menor retângulo que envolve a solução por completo e a área do objeto. O melhor resultado encontrado até o momento (devido as dimensões, o tensor não converge completamente) foi uma proporção de 0.4043. Financiamento CNPq e FAPESP.