Premium
Solving the irregular strip packing problem via guided local search for overlap minimization
Author(s) -
Umetani Shunji,
Yagiura Mutsunori,
Imahori Shinji,
Imamichi Takashi,
obe Koji,
Ibaraki Toshihide
Publication year - 2009
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2009.00707.x
Subject(s) - polygon (computer graphics) , regular polygon , rectilinear polygon , minification , algorithm , mathematical optimization , packing problems , mathematics , position (finance) , benchmark (surveying) , monotone polygon , computer science , simple polygon , geometry , telecommunications , geodesy , finance , frame (networking) , economics , geography
The irregular strip‐packing problem (ISP) requires a given set of non‐convex polygons to be placed without overlap within a rectangular container having a fixed width and a variable length, which is to be minimized. As a core sub‐problem to solve ISP, we consider an overlap minimization problem (OMP) whose objective is to place all polygons into a container with given width and length so that the total amount of overlap between polygons is made as small as possible. We propose to use directional penetration depths to measure the amount of overlap between a pair of polygons, and present an efficient algorithm to find a position with the minimum overlap for each polygon when it is translated in a specified direction. Based on this, we develop a local search algorithm for OMP that translates a polygon in horizontal and vertical directions alternately. Then we incorporate it in our algorithm for OMP, which is a variant of the guided local search algorithm. Computational results show that our algorithm improves the best‐known values of some well‐known benchmark instances.