An algorithm for the strip packing problem using collision free region and exact fitting placement

Autor(es)

Sato, Andre Kubagawa ^[1] ; Martins, Thiago Castro ^[1] ; Guerra Tsuzuki, Marcos Sales ^[1]

Afiliação do(s) autor(es)

^[1] Univ Sao Paulo, Computat Geometry Lab, Dept Mechatron & Mech Syst Engn, Escola Politecn, BR-05508 Sao Paulo - Brazil

• Tipo de documento: Artigo Científico
• Fonte: COMPUTER-AIDED DESIGN; v. 44, n. 8, p. 766-777, AUG 2012.
• Citações Web of Science: 17

Resumo

The irregular shape packing problem is approached. The container has a fixed width and an open dimension to be minimized. The proposed algorithm constructively creates the solution using an ordered list of items and a placement heuristic. Simulated annealing is the adopted metaheuristic to solve the optimization problem. A two-level algorithm is used to minimize the open dimension of the container. To ensure feasible layouts, the concept of collision free region is used. A collision free region represents all possible translations for an item to be placed and may be degenerated. For a moving item, the proposed placement heuristic detects the presence of exact fits (when the item is fully constrained by its surroundings) and exact slides (when the item position is constrained in all but one direction). The relevance of these positions is analyzed and a new placement heuristic is proposed. Computational comparisons on benchmark problems show that the proposed algorithm generated highly competitive solutions. Moreover, our algorithm updated some best known results. (C) 2012 Elsevier Ltd. All rights reserved. (AU)

• Processo FAPESP: 10/18913-4 - Estudo sobre translações aplicadas a polígonos de obstrução para que operações booleanas não regularizadas criem regiões de obstrução degeneradas
• Beneficiário: Marcos de Sales Guerra Tsuzuki
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Processo FAPESP: 09/14699-0 - Aplicação do Recozimento Simulado com Vizinhança Adaptativa à Tomografia de Impedância Elétrica para Obtenção de Imagens Absolutas
• Beneficiário: Thiago de Castro Martins
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 10/19646-0 - Translações Aplicadas a Polígonos de Obstrução para que Regiões Livres de Colisão Degeneradas Sejam Criadas por Operações Booleanas Não Regularizadas
• Beneficiário: André Kubagawa Sato
• Modalidade de apoio: Bolsas no Brasil - Doutorado