Polygon Nesting Using Genetic Algorithm

摘要

The nesting problem has been for many years a subject of interest to shipbuilders as continuously rising price of raw material.An optimized steel plate cutting plan saves shipyard both time and material,improves production efficiency,and in return enhances the company’s competition capability.In this paper,the author will propose a polygon nesting method using bottom left strategy with genetic algorithm.The algorithm allows parts to be nested within several steel plates which have fixed sizes by searching a suitable accommodate node among the intersection points of the no-fit polygons of previously placed parts relative to the new part following a bottom left policy.We verify this algorithm using a rectangular nesting problem from published literatures.And then give more computational experiments on polygon nesting problems.