Extended local search and polygon grouping for 2D irregular strip packing problem

摘要

Strip Packing Problem (SPP) is a problem of laying a set of objects into a rectangular container with minimum length. Objects can be regular and irregular polygons, while the container has fixed width and length. This study used modified extended local search (ELS) and grouping polygon to solve the SPP. First, polygons are grouped based on convex hull and bounding box to produce tight combination of polygons and near to rectangular shape clusters. Second, layout initialization using a bottom-left algorithm is performed, in which each group of polygon is placed on the most left and bottom position. Then, we start the iterative ELS to change the layout by increasing/reducing the length of the container and rearrange the position of the polygons to be fit in the container. Experiments using DAGLI, DIGHE1, FU, JAKOBS2, MAO and MARQUES dataset showed that polygon grouping was able to reduce the number of polygons 37% on average and the average container efficiency using the proposed method was 77.28%.