A Heuristic Algorithm for Nesting Problems with Irregular Shapes

Abstract

The irregular nesting problem, also known as stock placement problem has been studied and investigated over many decades where convex/non-convex pieces have to be placed inside the main sheet such that no piece overlap and cross the boundary of sheet. Nesting problem is widely used in raw material industries, like clothing, wood, metal, leather and paper making industries. The objective is to maximize the utilization of sheet and minimize the waste of sheet keeping the sheet width constant. There are many heuristic techniques in the literature used to solve the nesting problems. In nesting problem, there are two basic categories that are used by the researchers; one is placement strategy and second one is sorting strategy. Geometric constraints are the fundamental problems in nesting problems. In this thesis, a heuristic algorithm is used to solve nesting problems which uses the concept of optimal groups of unique shapes based on placement routine which is a combination of three optimization functions, boundary overlap, convex hull and wastage. Overlap detection is performed to check the polygons overlap. Iterative method is used to generate a list of polygons placement and an objective function is measured against each placement which is again a combination of three optimization functions: boundary overlap, compaction and wastage. The polygon is placed at the placement which has maximum value of boundary overlap, maximum compaction and minimum wastage. The proposed technique is tested with few examples of convex and non convex shapes. Our proposed algorithm’s results are compared with previous benchmark algorithms already available in the literature. Our proposed algorithm’s results are superior to previous works in the literature and is a strong candidate for real industries.