Retail steel cutting optimization: metaheuristics for cutting and packing problems

Joaquim Paul Laurens Viegas

Key information

Authors:

Joaquim Paul Laurens Viegas (Joaquim Paul Laurens Viegas)

Supervisors:

Susana Margarida da Silva Vieira (Susana Margarida da Silva Vieira)

Published in

November 21, 2013

Abstract

This work presents heuristic and metaheuristic approaches for addressing cutting and packing problems. The real-world steel cutting problem of a retail steel distributor is addressed in this thesis. In addition, cutting stock problem benchmark instances are used for validation and further algorithm development. The real-world problem was formulated as multicriteria 3-dimensional guillotine cutting problem for minimization of stock growth, scrap generation and time consumption. The data addressed is relative to 3 months of operation of the retail steel distributor. Using a daily optimization interval, the problem characteristics widely change from day to day making it more complex than classical problems. A tabu search and ant colony optimization approaches are presented for both problems and a local search approach was proposed to further improve the results for the benchmarks. A greedy algorithm was also developed, being used for result comparison and solution estimation of the retail steel distributor. The developed methods are based on the work of Silveira [44] that addressed the same real-world problem using a single objective. For the retail steel cutting problem, the tabu search algorithm was able to generate better solutions than the estimation of the retail distributor decision process and, provide insight on the benefits of joint multiple order optimization. The tabu search approach was shown not to be very suitable for the used benchmarks, obtaining slightly improved results in comparison with the constructive heuristic, however, the ant colony approach and local search were able to achieve good results. Este trabalho propõe heurísticas e metaheurísticas para problemas do tipo cutting and packing. O problema real de corte de aço de uma empresa de distribuição de aços a retalho é abordado. Instâncias de teste de problemas do tipo cutting stock são utilizadas para validar os algoritmos propostos. O problema real é formulado como um problema de corte tridimensional multi-critério minimizando o crescimento de stock, a sucata e o tempo de operação. Os dados utilizados são relativos a 3 meses de operação da empresa. Utilizando um intervalo de optimização diário, as características do problema variam de dia para dia tornando o problema mais complexo do que problemas clássicos. São propostas duas metaheurísticas tabu search e ant colony optimization para ambos os problemas. Um algoritmo local search é proposto para melhorar os resultados dos problemas de teste. Um algoritmo greedy é também desenvolvido para comparação de resultados e estimação da solução da empresa. Os métodos desenvolvidos são baseados no trabalho de Silveira [44] que aborda o mesmo problema real formulado com um objectivo único. Para o problema da empresa, o algoritmo tabu search obteve soluções melhores do que a estimação do processo da distribuidora de aços, e permitiu a compreensão dos benefícios da otimização conjunta de múltiplas encomendas. O algoritmo tabu search mostrou-se pouco adequado para os testes utilizados, alcançando resultados ligeiramente melhores do que a heurística construtiva, no entanto, as abordagens do tipo ant colony optimization e local search alcançaram bons resultados.