TY - GEN
T1 - Extended local search and polygon grouping for 2D irregular strip packing problem
AU - Anggraeny, Fetty Tri
AU - Suciati, Nanik
AU - Yuniarti, Anny
PY - 2013
Y1 - 2013
N2 - 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%.
AB - 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%.
KW - 2D Irregular Strip Packing Problem
KW - local search
KW - polygon grouping
KW - tabu search
UR - http://www.scopus.com/inward/record.url?scp=84884870546&partnerID=8YFLogxK
U2 - 10.1109/ICTSS.2013.6588054
DO - 10.1109/ICTSS.2013.6588054
M3 - Conference contribution
AN - SCOPUS:84884870546
SN - 9781479901456
T3 - Proceedings - International Conference on ICT for Smart Society 2013: "Think Ecosystem Act Convergence", ICISS 2013
SP - 10
EP - 15
BT - Proceedings - International Conference on ICT for Smart Society 2013
T2 - 2013 International Conference on ICT for Smart Society 2013: "Think Ecosystem Act Convergence", ICISS 2013
Y2 - 13 June 2013 through 14 June 2013
ER -