Comparação de Solvers na Resolução do Problema Integrado de Nesting de Caminho de Corte

Os problemas de corte e empacotamento constituem uma importante classe de problemas de otimização combinatória com diversas aplicações industriais, como nas indústrias têxtil, metalúrgica e de madeira. De acordo com a tipologia clássica de Dyckhoff (1990), posteriormente refinada por Wäscher et al. (2007), esses problemas podem ser classificados segundo as características dos objetos a serem cortados e das peças produzidas. O problema estudado neste trabalho pertence à classe dos problemas de corte e empacotamento bidimensionais (2D Cutting and Packing) envolvendo o posicionamento de itens irregulares em uma placa de altura fixa e comprimento ilimitado, conhecido como problema de nesting.

O problema de nesting consiste em determinar a melhor forma de posicionar um conjunto de peças de formato irregular em uma placa de modo a minimizar o desperdício de material e evitar sobreposições. Devido à alta complexidade geométrica, a literatura destaca o uso do No-Fit Polygon (NFP) como ferramenta para identificar posições viáveis e garantir a não sobreposição entre as peças (Bennell e Oliveira, 2008, 2009).

Uma vez definido o posicionamento das peças, surge na prática industrial um segundo problema crítico: a determinação do caminho que a ferramenta de corte deve seguir para separar as peças da placa. Este problema de caminho de corte busca minimizar a distância percorrida ociosa pela ferramenta, influenciando diretamente a produtividade. Tradicionalmente resolvidos de forma sequencial, estudos recentes como os de Oliveira et al. (2018,2020) propõem modelos integrados que consideram simultaneamente o posicionamento das peças e a sequência de corte, otimizando o processo global de fabricação por meio de uma abordagem exata discreta.
O modelo integrado é baseado no modelo Dotted-Board de Toledo et al.(2013), e no modelo do problema do caixeiro viajante (Travelling Salesman Problem – TSP).

Do ponto de vista da teoria da computação, o problema de nesting é classificado como NP-difícil (NP-hard), o que significa que encontrar a solução ótima global exige um esforço computacional que cresce exponencialmente com o número de peças. Toledo et al. (2013) observam que a vasta maioria das abordagens baseia-se em heurísticas e meta-heurísticas, que buscam soluções satisfatórias em tempos reduzidos, mas sem garantia de otimalidade. Entretanto, o modelo Dotted-Board, proposto por Toledo et al.(2013), utiliza uma formulação de programação inteira mista (MIP) baseada em uma grade de pontos para oferecer uma abordagem exata. Esta metodologia permite não apenas encontrar soluções de alta qualidade, mas também avaliar o gap de otimalidade, servindo como uma base rigorosa para comparar a eficiência de diferentes motores de busca (solvers).

Oliveira et al. (2018, 2020) mostram que a disposição das peças influencia diretamente a extensão do caminho a ser percorrido pela ferramenta, demonstrando que a abordagem integrada é nitidamente benéfica para a produtividade global. Entretanto, a resolução simultânea desses problemas eleva significativamente a complexidade do modelo matemático. Estudos como o de Becker et al. (2023) realizam comparações computacionais entre solvers comerciais para analisar aspectos como tempo de execução e robustez em problemas de corte, justificando a necessidade de avaliar qual ferramenta fecha o gap de otimalidade de forma mais eficiente.

 Neste contexto, o presente trabalho tem como objetivo comparar o desempenho dos software de otimização CPLEX e Gurobi para resolver instâncias do problema integrado de nesting de caminho de corte utilizando o modelo proposto por Oliveira et al. (2020). Através deste estudo computacional, podemos identificar qual ferramenta de otimização apresenta melhor desempenho frente às restrições de discretização e à complexidade combinatória do modelo integrado.