A Heuristic Approach Based on Shape Similarity for 2D Irregular Cutting Stock Problem - Intelligent Computing for Sustainable Energy and Environment - page 276

1. All pieces must be within the object (closeness);
2. Pieces must not overlap with each other (disjoint);
3. In this research, rotation of piece is allowed. And each piece has eight
orientations: 0°, 45°, 90°, 135°, 180°, 225°, 270° and 315°.

This paper is organized as follows. A brief review of previous work in the field is
presented in Section 2. The outline of our method is introduced and a novel heuristic
placement strategy based on shape similarity is presents in detail in section 3. Section
4 gives experimental results on benchmark problems from the literatures that
demonstrate the capabilities of the proposed approach. In Section 5 the research is
concluded and possible issues for future work are suggested.

2 Literature Review

The Cutting and Packing problem involving irregular shape is also called nesting
problem. A number of approaches have been proposed to tackle different nesting
problems. We only give a brief discussion on some of the most interesting approaches
previously presented in the literature.
The most visible attribute of nesting problems and the first obstacle researchers
come up against is the geometry. As a result, developing a set of tools to assimilate
the geometry is a non-trivial task and potentially a barrier that stifles academic
research in this area. There exist a couple of solutions to this problem such as
Rectangle Enclosure, Orbital Sliding of No Fit Polygon, Minkowski Sum of No Fit
Polygon, and Phi Function [3-7].
In terms of solution methods a number of approaches are proposed depending on
the type and the size of the problem. There have been many different strategies for
producing solutions to the irregular cutting stock problem. These include exact
algorithm (e.g. linear programming, dynamic programming, column generation etc.),
heuristic placement strategy, meta-heuristic search techniques, and other novel
approaches. For less constrained and simpler packing tasks, exact algorithms are
developed along with problem-specific heuristic procedures [8]. For more complex
packing tasks, heuristic search methods have been applied successfully for their
solution. Heuristic placement strategy such as bottom-left (BL), bottom-left-fill is
proposed to supply a rule for pieces to be placed on sheet [9-11]. Furthermore, this
research utilizes techniques of shape similarity drawn from computer vision and
artificial intelligence, and achieves high-quality solutions with shorter computational
times [12].
The 2DCSP is NP hard due to the combinatorial explosion encountered as the size
of problem increases. As a result, a number of published solution approaches focus on
heuristic and meta-heuristics methodologies. Meta-heuristics are general frameworks
for heuristics in solving combinatorial optimization problems. These meta-heuristic
approaches include simulated annealing, tabu search, neural networks and genetic
algorithms [13-16].
Although numerous approaches based on computational geometric description
have obtained good performance, computational complexity for large and complex