Algoritmos de posicionamento de figuras irregulares: aplicação a um caso real da indústria automóvel

Abstract

Esta tese aborda o problema de posicionamento de figuras irregulares (PFI) em peles de couro derivado de uma indústria nacional do ramo automóvel (Coindu) que se dedica à produção de estofos de couro. Este problema consiste em determinar o plano de corte que minimiza o desperdício resultante do posicionamento de peças que compõem os estofos no interior de peles de couro que poderão conter zonas de qualidade e buracos. O problema abordado envolve fortes componentes combinatória e geométrica e está sujeito a restrições relativas à não sobreposição e a zonas de qualidade. A relevância prática deste problema e os potenciais ganhos financeiros provenientes de soluções de qualidade contrastam com o reduzido número de contribuições presentes na literatura. Um novo algoritmo construtivo é apresentado para a resolução de problemas de posicionamento de figuras irregulares (PFI) em peles de couro. Este algoritmo é constituído por quatro conjuntos sucessivos de estratégias, designadamente: agrupamento de peças, selecção da próxima peça a posicionar, selecção de região de posicionamento admissível e avaliação de posicionamento. Duas fases de experiências computacionais foram realizadas, envolvendo peças e peles retiradas de instâncias reais da indústria automóvel. A fase preliminar teve como objectivo destacar os conjuntos de estratégias que originaram os melhores resultados. A segunda fase de testes computacionais avaliou o desempenho do algoritmo desenvolvido relativamente aos níveis da eficiência e do tempo de geração de um plano de corte. A utilização original de informações inerentes à região de posicionamento admissível para a colocação de peças permitiu a obtenção de favoráveis níveis de eficiência do aproveitamento de matéria-prima. Foi desenvolvida uma nova meta-heurística baseada em Pesquisa de Vizinhança Variável (VNS, do inglês: Variable Neighborhood Search) para o problema de PFI em peles de couro. Este algoritmo parte de uma solução inicial gerada pela heurística construtiva desenvolvida e faz uso de estruturas de vizinhança originais baseadas na sequência de posicionamento das peças na pele e correspondente valor da qualidade de posicionamento. Duas fases de experiências computacionais foram realizadas. A primeira fase consistiu procedimento de afinação dos parâmetros do algoritmo VNS com vista a aperfeiçoar o seu desempenho. A segunda fase de experiências computacionais envolveu um amplo conjunto de instâncias reais, e consistiu na avaliação do desempenho geral do algoritmo VNS. Esta fase revela a capacidade deste algoritmo na melhoria da solução inicial, em iguais condições relativamente a operadores manuais de corte de couro. A meta-heurística GRASP (da literatura anglo-saxónica, Greedy Randomized Adaptive Search Procedure) serviu de base para o desenvolvimento de um terceiro algoritmo para a resolução do tipo de problemas que motiva esta tese. O algoritmo GRASP constrói iterativamente uma solução inicial, com base numa lista restrita de candidatos formada pelas peças cujo posicionamento é considerado mais vantajoso para o plano de corte actual. São apresentados resultados computacionais, provenientes de uma série de experiências, que visaram a avaliação do desempenho deste algoritmo. A discussão dos resultados permite salientar os benefícios resultantes da aplicação deste algoritmo para a resolução de problemas de PFI em peles de couro.

This thesis addresses the leather nesting problem, focused in a national automotive company (Coindu) that produces car seat covers. This problem consists in finding the best layouts for a set of irregular shapes within large natural leather hides with highly irregular contour, which may have holes and quality zones. This problem, which has strong geometrical and combinatorial components, is subject to non-overlapping and quality zones related constraints. The practical relevance of this problem, and the potential financial value of savings that good solutions may generate, contrast with the very small number of contributions that have been reported in literature. A new constructive algorithm for dealing with leather nesting problem is presented. This algorithm consists in four successive sets of strategies, namely: grouping the pieces, selecting the next piece to place, selecting a feasible placement region and evaluating a placement position. Two sets of computational experiments using real instances were presented. Preliminary results allowed to determine the sets of strategies that had the potential to generate the best results. The second set of computational results assessed the algorithm performance in terms of time and efficiency to generate a layout. The original approach to use information provided by the no-fit-polygons allowed us to achieve optimistic quality raw-material usage results. A new Variable Neighborhood Search algorithm for general leather nesting problem is proposed. This algorithm uses an initial solution generated by the developed constructive heuristic. New neighborhood structures are described, which are based on the pieces placement sequence on the hide and on the quality of the fitness of these pieces in the current layout. To evaluate the performance of these approaches, two extensive sets of computational experiences on real instances were conducted. The purpose of the first set was to compare possible strategies for the VNS algorithm and to tune the involved parameters. The second set of computational experiments used a large collection of real instances, and evaluated the overall performance of the VNS algorithm. This last stage expressed the competence of this algorithm to improve the initial solution, in equivalent conditions than those used by human leather nesting operators. A GRASP meta-heuristic inspired the development of a third algorithm for the class of problems that motivates this thesis. The GRASP algorithm generates an initial solution, based on a restrictive candidate list formed by the pieces which placements are considered to be the most beneficial to the actual layout. Some computational results were presented, from a set of experiments that addressed the algorithm performance evaluation. The analysis of these results allowed emphasizing the benefits of the GRASP algorithm application for dealing with the leather nesting problem.