Raster penetration map applied to the irregular packing problem

• Type: Article in International Scientific Journal
• Date: 2019

Authors

André Kubagawa Sato (Author) Other; Thiago Castro Martins (Author) Other; António Miguel Gomes (Author) FEUP; Marcos Sales Guerra Tsuzuki (Author) Other

Journal

Title: European Journal of Operational Research

Vol. 279 No. 2

Pages: 657-671

ISSN: 0377-2217

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 4 Citations

Scopus - 9 Citations

INSPEC

Other information

Authenticus ID: P-00Q-J2X

DOI: 10.1016/j.ejor.2019.06.008

Abstract (EN): Among the most complex problems in the field of 2-dimensional cutting & packing are irregular packing problems, in which items may have a more complex geometry. These problems are prominent in several areas, including, but not limited to, the textile, shipbuilding and leather industries. They consist in placing a set of items, whose geometry is often represented by simple polygons, into one or more containers such that there is no overlap between items and the utility rate of the container is maximized. In this work, the irregular strip packing problem, an irregular packing variant with a variable length container, is investigated. The placement space is reduced by adopting a rectangular grid and a full search is performed using preprocessed raster penetration maps to efficiently determine the new position of an item. Tests were performed using simple dotted board model cases and irregular strip packing benchmark instances. The comparison of our results with the state of the art solutions showed that the proposed algorithm is very competitive, achieving better or equal compaction in 9 out of 15 instances and improving the average density in 13 instances. Besides the contribution of the new best results, the proposed approach showed the advantage of adopting discrete placement, which can be potentially applied to other irregular packing problems.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 15