Artículos de revistas
An algorithm for the strip packing problem using collision free region and exact fitting placement
Fecha
2012-08Registro en:
COMPUTER-AIDED DESIGN, OXFORD, v. 44, n. 8, supl. 1, Part 4, pp. 766-777, AUG, 2012
0010-4485
10.1016/j.cad.2012.03.004
Autor
Sato, Andre Kubagawa
Martins, Thiago Castro
Tsuzuki, Marcos Sales Guerra
Institución
Resumen
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.