1. Introduction

Cutting and packing problems involving irregular shapes arise in a wide variety of industries, including garment manufacturing, sheet metal cutting, furniture making and shoe manufacturing. Figure 1 provides an example of a layout from the garment manufacturing industry. As a result, the range of problem variants involving irregular shapes, referred to here as nesting problems, is a core area of research in the field of cutting and packing. The problem is NP-complete (Fowler et al, 1981) and as a result, solution methodologies predominantly utilize heuristics. A further defining characteristic of nesting problems is the requirement to develop powerful geometric tools to handle the wide variety and complexity of shapes that need to be packed. In this paper, we propose to provide detailed explanations of the most common solution representations and solution approaches for solving nesting problems. Our aim is not to provide an exhaustive review of the literature but to draw on the literature to describe and evaluate the various approaches.

Figure 1.

An example layout from garment manufacturing.

Full figure and legend (77K)

Published approaches to nesting problems cover a wide range of techniques and application areas. However, with a few notable exceptions they are firmly grounded in the field of heuristics. There are a number of ways of classifying the various types of solution approaches. Here we propose to take the first cut by dividing the approaches into those methods that work with partial solutions building up to a final layout (Section 4) and those methods that work with complete solutions where changes are made in order to find improvements (Section 5). It is worth noting that both approaches mimic how humans might tackle the problem, that is, building a solution by selecting the most appropriate piece to place next, known as a constructive heuristic, or swapping and moving pieces to improve a complete solution, known as an improvement heuristic. Nesting problems are a good example of problems humans have a natural aptitude for solving, and therefore modelling their behaviour is a reasonable proposition. We divide our discussion of construction heuristics into the placement rules (Section 4.1) and the piece sequencing (Section 4.2), and we divide our discussion of working with complete solutions by approaches that use a representation of the problem such as a sequence (Section 5.1) and those that use the physical layout (Section 5.2).

Before discussing the solution approaches it is necessary to define briefly some key concepts with respect to the geometric aspect of nesting problems (Section 3). The geometry is a key research topic within nesting problems and many researchers have published papers describing their approaches. We refer the reader to Bennell and Oliveira (2008) which provides a tutorial on the main geometric methodologies and further references for each method. In the next section, we provide a definition of the problem.

2. Problem definition

Researchers use a variety of terms to identify the group of problems that we will discuss. Some commonly used terms are irregular shape stock cutting, irregular strip packing, nesting, polygon placement, marker making, non-convex cutting stock, 2D packing problems or some combination of any of these terms. We adopt the term nesting problems, which we define as follows:Problems in which a set of pieces that contain at least one piece of irregular shape must be placed in a non-overlapping configuration within a given placement area in order to optimise an objective. The placement area may include one or more fully or partially constrained stock sheets. A piece is irregular if it requires a minimum of three parameters to identify it. For example, a circle needs just a single parameter, the radius, and a rectangle needs two parameters, its length and width. Irregular shapes are usually simple polygons, and in some cases, polygons that contain holes. When pieces include curved edges, it is common to approximate them by an enclosing polygon, where a series of tangents to the curve form the polygonal edges. Recently, new research has emerged that retains the curved edges in their original form. Of course, nesting problems may contain some pieces that are regular.

The above definition is clearly very general and covers many variants of the problem. These can be identified through a number of key characteristics; homogeneity/heterogeneity of the pieces; stock sheet size, shape, number and quality (with respect to the homogeneity of the stock sheet surface); and single or multi objective. Dyckhoff (1990) proposed a useful classification of cutting and packing problems, which was revised recently by Wäscher et al (2007). Their classification partitioned the problems by dimensionality (one-, two- and three-dimensional), objective of the assignment (minimize waste or maximize profit), large objects (single, multiple and identical, or multiple and different) and small items (homogeneity and shape). Using Wäscher, Hauner and Schumann's typology, nesting problems, in general, are open-dimension problems, with the refinement of being two-dimensional and irregular. The new typology provides a useful progression towards a consistent nomenclature for cutting and packing problems.

3. The geometry

The most visible attribute of nesting problems and the first obstacle researchers come up against is the geometry. Specifically this means answering the question: given the position of two pieces on the stock sheet, do they overlap, touch or are they separated? There exists a number of solutions to this problem ranging from simple to complex, these include the raster method, direct trigonometry, the no-fit polygon (NFP) and the phi-function. See Bennell and Oliveira (2008) for a tutorial in these methodologies.

Raster methods are approaches that divide the continuous stock sheet into discrete areas, hence reducing the geometric information to coding the data by a grid represented by a matrix. Three different interpretations of this approach are Segenreich and Braga (1986); Oliveira and Ferreira (1993) and Babu and Babu (2001). In each case the process of eliminating overlap between pieces or identifying non-overlapping placement positions is just a matter of counting cells in the grid. Also raster representations are simple to code, can represent non-convex and complex pieces as easily as simple polygons and are reasonably fast when checking the geometric feasibility of the layouts. However, the disadvantages are that these methods are memory intensive and cannot exactly represent pieces with non-orthogonal edges.

When representing pieces as polygons, researchers can use direct trigonometry, which provides well-known tests for edge intersection in order to identify whether pieces partially overlap each other, and point inclusion in order to identify whether one piece is contained inside another. The accuracy of the representation is better than the raster methods but the time to check feasibility is exponential in the number of edges of the pieces. The D-function (Konopasek, 1981) has been demonstrated as an efficient tool for characterizing the relationship between two edges and can be used to identify edge intersection. Ferreira et al (1998) describe additional tests that significantly reduce the number of direct edge intersection tests required.

The NFP has become an increasingly popular option for dealing with the geometry since it is more efficient than direct trigonometry and equally accurate. In addition, the concept opens up new options for placement strategies. Art (1996) first used the NFP in its most basic form as the placement envelope. However, the potential of the NFP was not fully exploited until the work of Milenkovic et al (1992). Since the NFP is an important building block for some of the solution approaches we describe later in the paper, we will provide a more detailed explanation of this geometric concept.

In essence, the NFP is a polygon derived by combining the two component polygons in such a way that the interior of the NFP represents the relative positions of the two polygons that result in overlap, the boundary represents the touching positions of the two polygons and the exterior represents their separation. Consider the polygons illustrated in Figure 2(a), where A has fixed position and B slides around A in such a way that B is always touching A and never intersects with A. Given a reference point on B (selected as the bottom vertex), the locus of the reference point forms a closed path that forms the boundary of NFP_AB. Figure 2(b) provides examples of the three scenarios the NFP represents. If the reference point of B is inside NFP_AB, then A and B overlap (see B1); if the reference point of B is on the boundary of NFP_AB, then A and B touch without overlap (see B2), and if the reference point of B is outside NFP_AB, then A and B will neither touch nor overlap (see B3). Hence, the NFP reduces the computational burden of identifying if two polygons overlap to a simple point-inside test. Most applications using the NFP will calculate the NFPs for all pairs of pieces during a pre-processing stage.

Figure 2.

(a) B slides around A tracing the boundary of the NFP; (b) B1 has reference point inside NFP B2 has reference point touching NFP B3 has reference outside NFP.

Full figure and legend (43K)

A significant drawback of this approach is the non-trivial task of developing a robust NFP generator for general non-convex polygons. Alternative methodologies can be found in Agarwal et al (2002), Bennell and Song (2008b) and in Burke et al (2007). A related concept is the inner-fit polygon (IFP) which represents the containment of one polygon inside another. Here, it must be possible to place the sliding polygon (B) so it is entirely contained within the fixed polygon (A). The IFP is the closed path formed by tracing the reference point of B as it slides around A while remaining contained within A. This is commonly used to ensure pieces do not extend beyond the edges of the stock sheet.

The phi-function proposed by Stoyan et al (2001) is a tool with great potential for dealing with the geometric issues for nesting problems. Phi-functions are mathematical expressions that represent the mutual positions of two objects. Specifically, the value of the phi-function is greater than zero if the objects are separated, equal to zero if their boundaries touch and less than zero if they overlap. When the phi-function is normalized the actual value is the Euclidean distance between the two objects, otherwise it is an estimate of the distance. Bennell et al (2008) derive the phi-function for primary objects; these are circles, rectangles, regular polygons, convex polygons and the complement of these shapes. Shapes that are not primary objects are represented as a union or intersection of the primary objects. Currently there is no algorithmic process published in the literature for generating the phi-function for all types of arbitrary shapes.

4. Working with partial solutions

Working with partial solutions represents the construction of a layout piece by piece. In the case of a single-pass construction heuristic, the approach can often produce reasonable quality solutions with little computational cost. In addition, feasibility is embedded into the heuristic since each piece is placed in a feasible position on the stock sheet and not moved. The quality of the solution is reliant on two key features of the heuristic. First, the placement order of the pieces, for example, in a random order or in order of decreasing size. Second, the placement rule adopted, for example, bottom left (BL) or minimum enclosing area. Further there is scope to enhance the performance by allowing dynamic sequencing with respect to the evolution of the partial solution and/or backtracking. We will explore these decisions in more detail in the following two sections.

4.1. Placement rules

Independent of which piece we are placing, a placement position on the stock sheet must be found. The most popular and widely used placement rule is BL. This rule iteratively moves each piece horizontally as far to the left as possible and then vertically until it is able to move horizontally again or touches another piece or the bottom of the stock sheet. This rule may equally apply to other directions such as top right. The final piece position is constrained to be inside the stock sheet and should not overlap previously placed pieces. This placement strategy was first applied to nesting problems by Art (1996), and the same principles are still applied in more recent solution approaches (eg Dowsland et al, 2002; Gomes and Oliveira, 2002).

The implementation of the BL placement heuristic will depend on the geometric representation adopted for the pieces. If the raster or polygonal representations are adopted, then we must employ a strategy of moving the pieces in steps over the layout while checking for feasibility at each step. If overlap is detected after a movement to the left, then the previous position is resumed and a movement towards the bottom is tried. If this move is feasible, then the algorithm returns to movements towards the left and the algorithm continues. The piece finds its final position when it cannot move to the left or towards the bottom (Figure 3). This implementation of the BL strategy basically imitates the sliding of a piece over the layout.

Figure 3.

BL strategy based on piece sliding.

Full figure and legend (37K)

Another issue that should be considered when choosing a placement heuristic is its ability to fill holes. Holes are defined as portions of the stock sheet, surrounded by already placed pieces, where smaller pieces may fit. A few authors (eg Segenreich and Braga, 1986; Dowsland et al, 1998; Burke et al, 2006) propose searching from the left side of the layout through the infeasible positions until a feasible position is found. As a result of this placement strategy, holes will show up first and be occupied before the right side of the stock sheet. In order to move through the infeasible positions, some researchers superimpose a grid over the stock sheet to define discrete positions for testing. While Segenreich and Braga (1986) rely completely on a grid representation for both the layout and an approximation of the pieces, and use a pure BL strategy, Dowsland et al (1998) only reduce the stock sheet to a grid and search starting from the left (x=0) and alternating between the top and bottom working inwards. Burke et al (2006) use a more sophisticated strategy in which the horizontal movement of the pieces is discrete, as in the previous approaches, but the vertical movement is continuous and obtained by geometric functions that not only verify the feasibility of a specific placement point but also computes the vertical displacement that leads to a feasible placement. This implementation relies on the geometric concept of the NFP for evaluating overlapping placement positions. For all these approaches, computational effort can be reduced by defining the starting point for the sliding as the last point an equivalent piece was successfully placed (Figure 4).

Figure 4.

A BL implementation with pieces sliding from infeasible positions.

Full figure and legend (33K)

If using the NFP, the BL placement strategy with hole filling can be executed without the use of a grid. Given a partial solution containing pieces P_i, i=1,...,m, the next piece to be placed P_k, the NFP of P_i and P_k, and the IFP of the stock sheet and P_k, we can find the set of all feasible placement positions for piece P_k. This set, A, can be stated as follows:

where NFP_i,k is the NFP of piece P_k and P_i, when P_i is placed at coordinates (x_i,y_i). Set A is an infinite and non-convex feasible region. Gomes and Oliveira (2002) reduce this set using the observation that when looking for the BL placement we only need to consider the vertices of the feasible regions. These vertices are a subset of the NFP vertices, the intersection of edges among all NFPs and the intersection of all NFPs and the IFR. Each of these points is tested to identify whether it lies in the interior of any other NFP and therefore is not part of the feasible regions. Once all the vertices are checked for feasibility, finding the BL placement point for piece P_k becomes a trivial sort operation over a discrete and finite set of points. Figure 5(a) identifies the feasible points and highlights the BL point. Dowsland et al (2002) follow an 'edge-oriented' strategy to determine the set of feasible placement points. For each edge of each NFP they slide along the edge, starting from the left most vertex, and stop at the first point that is not part of the interior of any of the other NFPs. In Figure 5(b) when analysing edge AB, which belongs to NFP_jk, the approach would slide from point A until point C, where it leaves the interior of NFP_ik. Hence, C is the leftmost feasible position. They further improve the algorithm efficiency by sorting the edges and differentiating front and back edges. In addition to reducing a continuous placement area to a set of discrete points, using the NFP has the advantage that with BL implementations hole filling is automatic and natural.

Figure 5.

BL placement using NFP: (a) vertex-oriented; (b) edge-oriented.

Full figure and legend (44K)

Oliveira et al (2000) suggest an alternative placement rule to BL. In this case the positions of the pieces are not fixed on the stock sheet. Instead, a floating origin is used where the pieces' relative positions are fixed and the width of the partial solution is constrained to be less than or equal to the stock sheet width. The partial solution is described by its frontier along which the next piece is added (Figure 6). Oliveira et al investigate three placement rules for growing the solution with the aim of keeping the layout as compact as possible while trying to avoid an increase in length. These are:

• Minimization of the area of the rectangular enclosure of the newly generated partial solution.
• Minimization of the length of the rectangular enclosure of the newly generated partial solution.
• Maximization of the overlap between the rectangular enclosure of the actual partial solution and the rectangular enclosure of the piece to be placed, without allowing overlap between the pieces themselves.

Figure 6.

An alternative placement rule to BL.

Full figure and legend (38K)

Each piece added to the partial solution is merged with the pieces already placed and any enclosed gaps between pieces are assumed as waste. As a result the approach does not take advantage of holes in the layout. Oliveira et al (2000) use the NFP to identify the potential placement positions. Since the partial solution changes shape after each placement, a new NFP between the next piece and the partial solution must be calculated at each step. However, advances in the use of the NFP mean that both gaps can be used and recalculation is not required; see Bennell and Song (2008a). It is also worthwhile noting that this approach can easily be adapted to an irregular shape (non-rectangular) stock sheet and that there is considerable flexibility in the placement rule selected.

Ribeiro and Carravilla (2004) propose a unique approach that overcomes the need for a placement rule by incorporating backtracking mechanisms for each placement point. They work over a discretized stock sheet and use constraint logic programming (CLP) to efficiently try each feasible placement point for each piece given the previously placed pieces. The intrinsic CLP mechanisms to deal with constraints plus specific rules proposed by the authors lead to an algorithm able to solve small problems to optimality efficiently.

4.2. Placement sequences

The order in which the pieces are placed on the stock sheet has a significant influence on the resulting quality of the solution. Defining this order is difficult since irregular shapes do not have common characteristics that can give insight into how they might best fit together. When considering the order, researchers need to decide between randomization, ordering according to a fixed rule, dynamic selection and whether backtracking is permitted.

The simplest approach is random selection, which is often used when embedded in any kind of Monte Carlo algorithm. It is also used to generate initial solutions for algorithms that search over complete solutions, discussed in Section 5.1. Such an approach produces highly variable solutions and could only be considered under multiple runs. If the solution approach is to construct a single solution using a construction heuristic, we can employ better reasoning then random selection. Pre-defined sequences can be used. Dowsland et al (2002) use eight static orderings, illustrated in Figure 7. All these rules have the common strategy of trying to place the difficult-to-place pieces first. Depending on the criteria, the difficult pieces may be the largest, the longest, the most irregular or simply those that exist in larger quantities.

Figure 7.

Metrics used by Dowsland et al (2002) to determine the static order of pieces.

Full figure and legend (78K)

Dynamic selection permits all piece types to be available to be placed next. A piece type is only excluded once all the pieces of that type have already been placed. Figure 8 illustrates this process for a problem with three piece types and two fixed orientations of 0° and 180°. Note that since two pieces are symmetric, the number of piece types is only increased by one. At each level, each available piece type is placed using the placement rule creating a number of candidate partial solutions. Each partial solution is evaluated using the given criteria and the piece generating the best partial solution is selected. Figure 8 shows that at level 0 piece 2 (0° orientation) is selected, followed by piece 1 at level 1 and piece 3 at a level 2.

Figure 8.

Dynamic piece selection.

Full figure and legend (58K)

The criterion for measuring the partial solution is not straightforward to formulate. Although the objective of nesting problems is in general to minimize the length of the layout, this metric is too greedy to lead to good solutions. Oliveira et al (2000) compare the partial solutions using one of the following seven criteria, these are, relative waste, overlap, relative distance, waste minus overlap, relative waste plus relative distance, distance minus overlap, and waste minus overlap plus distance. Bennell and Song (2008a) use similar measures and experiment with different aggregation methods. Albano and Sapuppo (1980) select the next piece according to the amount of waste generated by the placement and an estimate of the future waste.

Albano and Sapuppo (1980) and Bennell and Song (2008a) expand the dynamic selection approach by modelling the problem as a search tree. Each node in the search tree corresponds to a partial solution and a branch from a node represents the decision to add a piece to the partial solution. Hence, the tree's depth is the number of pieces to be packed, and the number of successor nodes branching from each node is the number of piece types remaining, possibly with multiple orientations. As a result, the nodes at the lowest level of the tree represent complete solutions. Since the greediest selection at each level does not necessarily lead to the best solution, they pursue more than one path through the search tree while restricting the number of successor nodes at each level.

Albano and Sapuppo (1980) prune the tree using a waste criterion to evaluate the partial solution generated by each successor. They pursue one path through the levels while the evaluation of waste is only slightly higher than that of partial solutions further up the tree. They also permit backtracking within a given number of levels.

Bennell and Song (2008a) use beam search. This approach searches the tree breadth first and at each level the tree is pruned according to two evaluation functions. The first is a local evaluation function that selects a predefined number of successors for each node according to the evaluation of the partial solution generated by the successor node. The second is a global evaluation found by greedily packing all the remaining pieces.

Constructing a solution piece by piece is a quick way of generating reasonable solutions. However, in order to find the highest quality solutions more sophisticated methods are required. This can be achieved through producing multiple solutions such as the beam search approach or working with complete solutions that are iteratively improved, which we will describe next.

5. Working with complete solutions

Since the nesting problem is combinatorial and NP-complete, local search provides an obvious set of candidate solution approaches. A key characteristic of these approaches is the process of iteratively making small changes to a complete solution. Most of the core meta-heuristics have been applied to nesting problems, these include Tabu Search (Bennell and Dowsland, 1999; Burke et al, 2006), Simulated Annealing (Oliveira and Ferreira, 1993; Heckmann and Lengauer, 1995), Genetic Algorithms (Jakobs, 1996; Babu and Babu, 2001). Here we focus on the strategic choices regarding the implementation of these approaches to nesting problems.

There are many features to consider when designing a local search. These include the objective function, the set of feasible solutions, the neighbourhood move and the over-riding search mechanism that controls the generation and acceptance of moves. However, the problem representation is the defining feature of the search strategy design. Here we will discuss the two main problem representations. The first is representing the problem as a sequence of pieces which is decoded through a placement rule; hence the search is over the sequence. The second is working with the solution directly, which we will call the physical layout, and moving pieces within the layout. As one might expect there are benefits and limitations of both approaches. The most significant are associated with the resulting smoothness of the solution landscape and the implications this has on computational time and feasibility.

When working over a sequence it is necessary to decode the sequence into a packing layout to evaluate the solution quality. This tends to incur a greater computational cost than that of evaluating a move within the layout. Also the solution quality is subject to the limitations of the placement rule adopted. A key benefit is that the placement rule guarantees feasibility. Implementations that work with the physical layout often permit overlap between pieces in order to provide scope for the search to adequately navigate the solution space. Hence, converging on a feasible solution can be problematic.

5.1. Searching over a sequence

When using a sequence of pieces as the solution representation, the evaluation of each solution is found by producing the layout using a placement rule. We have discussed the various placement rules in Section 4.1. Here we will describe different approaches for searching over the sequence.

Sequencing problems are found in many optimization applications. When using local search, common neighbourhood search strategies are swap moves and insert moves. A swap move exchanges the position of two pieces in the sequence and an insert move removes a piece from its current position and inserts it somewhere else in the sequence. For packing problems we can add another move, which is changing the orientation of a piece. All three of these moves are illustrated in Figure 9. The top sequence and corresponding layout is modified by applying the swap, insert and change orientation moves.

Figure 9.

The resulting layouts by a BL placement rule after a neighbourhood move.

Full figure and legend (71K)

In the small example in Figure 9, each move significantly changes the resulting layout. Conceptually, the swap move is more likely to generate smaller changes in the layout since replacing one piece with another leaves all other pieces in the sequence in the same position, whereas an insert move will disrupt the layout more as all pieces after the insertion or removal of a piece will be in a different position in the sequence. Hence insert moves can result in hilly solution landscapes and provide greater diversification. A change in orientation may be used when more than one orientation is permitted and the decoding of the algorithm does not already have a mechanism for testing different orientations. This move is used in conjunction with the swap and insert move and is usually considered with a certain probability that favours the swap or insert.

Whether a swap or insert neighbourhood is selected, or a combination of these, the number of pieces in a realistic nesting problem makes it necessary to restrict the size of the neighbourhood. One approach is to include all possible moves for a single piece in the neighbourhood, and another is to include each piece but to restrict the possible moves. The former strategy raises further issues of deciding the search order of the neighbourhoods and the final solution will have a dependency on this order. The latter strategy can be very restrictive and lead to a slow search that has difficulty diversifying.

Gomes and Oliveira (2002) propose a probabilistic two-exchange heuristic which uses a swap neighbourhood where the size of the neighbourhood is limited by a parameter that sets the maximum swap distance between pieces in the sequence. They test three rules for acceptance of a neighbourhood move: first found improve, best improve or random improve. The search terminates once it converges on the first local optimum. Burke et al (2006) use tabu search in order to visit a number of local optima. They restrict their neighbourhood size to just five solutions where they randomly select each solution in the neighbourhood. First, they randomly select between an insert move, a pairwise swap, a three-way swap and an n-way swap. Then, they randomly select the pieces to swap or the piece and position for the insert move. Takahara et al (2003) propose a neighbourhood search based only on insert moves. The search has two states: a normal state and an adaptive state. In the normal state all pieces have the same move probability and in the adaptive state the move probability of a piece is dependent on its relative weight, when compared to the sum of the weights of all other pieces. Whenever a move generates a better solution, the piece weight is increased by one unit. This is clearly an intensification strategy that runs for a fixed number of iterations before the search returns to the normal state.

A genetic algorithm is a natural choice for searching over piece sequences since the representation can be used directly as a chromosome. Jakobs (1996) and Babu and Babu (2001) both use this approach. Jakobs (1996) generates offspring by randomly selecting q consecutive pieces in the sequence starting at a random point p and placing them at the beginning of the offspring. The remaining pieces are added to the sequence in the order they appear in the second parent. A mutation is a 90° rotation of a piece. Babu and Babu (2001) tackle a variant of the nesting problem that considers multiple heterogeneous stock sheets, where the plates are finite and different and the objective is to place all the pieces in the minimum area. The first part of the genetic string has the stock sheet sequence, and the second part of the string has the sequence of pieces. The orientation for each piece is also coded in the string. The crossover operator randomly selects two crossover points, one in the sequence of stock sheets and one in the sequence of pieces. The offspring takes the genes on the right-hand side of each crossover point, at the beginning of each sequence, and the remaining genes from the second parent in the order they appear. They propose three mutation operators: a swap operator and two operators that change a piece's orientation. Once again more emphasis is given to the order by which the pieces are placed than to their orientation.

A unique approach is the Jostle algorithm of Dowsland et al (1998). The approach oscillates between packing from the left end of the stock sheet to packing from the right end of the stock sheet, where the sequence is determined by the x-coordinate position of each piece in the previous iteration. This is illustrated in Figure 10 where the layout at the left end of the stock sheet is translated into a sequence, given by the numbers in the polygon, and then packed in that order at the right end of the stock sheet. An interesting consequence of this approach is that the pieces that are placed at the end of the layout, possibly because they are hard to place, are the first to be placed in the next iteration. Many researchers state that placing difficult pieces early on contributes to good solutions. Jostle is able to exploit this since the placement rule also has hole-filling capability which allows small pieces to be placed between larger pieces, even when they appear much later in the sequence.

Figure 10.

One iteration of the Jostle algorithm.

Full figure and legend (32K)

5.2. Searching over the layout

When working with complete solutions, either represented directly by the physical layout or as a piece sequence, a neighbourhood structure is always implicitly or explicitly present. As a result, the concept of solution space naturally arises and its characterization is useful to categorize the different solution approaches.

The first important characteristic is feasibility with respect to the definition of the original nesting problem. An example of where infeasibility is commonly used is accepting solutions that contain overlap during the search, and penalizing this overlap in the objective function. The advantage of allowing the pieces to overlap is that it generates a smoother and more fully connected landscapes, leading to more efficient search algorithms. The major drawback is that the search may struggle to converge on local optima that do not contain overlap and as a result cannot find a feasible solution to the original nesting problem. Some authors propose 'post-optimization' or repairing procedures to eliminate overlap but this is often at the expense of solution quality.

The second relevant characteristic allows the division between continuous, and therefore infinite, solution spaces and discrete (finite) solution spaces. As discussed previously, the stock sheet, in the most general case, is a continuous area and as a result the solution space for methods that search over the layout is continuous. Methods that discretize the solution space aim to generate faster search procedures, while trying not to eliminate the global optimal solution by keeping the most promising placement points.

The final distinction between the approaches is directly connected to the above two characteristics of the solution space and that is how to alter the solution in order to make a move, which consequently defines the neighbourhood of a solution. Researchers use two major frameworks. The first is based on moving a single piece or a limited set of pieces. A single piece move can be characterized as an insert move where a piece is removed from its current location and inserted in a new location on the stock sheet. If more than one piece is moved, this is usually a swap move where the positions of two or more pieces are exchanged. Other types of movements are usually derived from the geometric nature of nesting problems, such as rotation and symmetry transformation movements. We describe these approaches in Section 5.2.1. The second framework is known as compaction and separation. It enables all pieces to change their positions simultaneously when moving from one solution to another. Although this is a powerful approach, it only searches a local area of the solution space. Hence, if a wider search is required other mechanisms need to be used. These approaches will be described in Section 5.2.2.

5.2.1. Local search approaches

In this section we will discuss strategies to define the solution space for local search approaches where the problem is represented by the physical layout. The way this is defined will influence other features of the search such as the definition of a neighbourhood move. We also discuss relaxing the no-overlap constraint and some of the consequences of such a strategy.

Many local search methods cannot deal with a continuous solution space and therefore require some means of reducing it to a discrete set of points. A common method is to impose a grid over the stock sheet and only search over the grid points. Hence the solution space contains only those solutions that place the origin of each piece at a grid point. Clearly this approach could remove potentially good placement positions from the solution space. The advantages are that it is simple to implement, flexible in terms of grid refinement and evenly distributes the search positions over the stock sheet. Implementations that have employed a search grid report reasonable success. Oliveira and Ferreira (1993) present a simulated annealing algorithm where the pieces are randomly placed on the stock sheet and a neighbourhood move is based on moving a piece by one grid unit. Bennell and Dowsland (2001) also imposed a grid and their neighbourhood contains all the solutions generated by moving a given piece to a new grid position.

An alternative approach to reducing the solution space is based on the understanding that all pieces in an optimal solution will touch the edge of the stock sheet and/or at least one other piece. Hence only the edges of the stock sheet and the touching position between pieces need to be searched. The boundary of the NFP provides a convenient mechanism for defining these positions. Bennell and Dowsland (2001) took this notion one step further by optimizing the placement positions on the edge of the NFP by identifying a subset of points where the point of minimum overlap is among them. They consider the subsidiary objective function of piece overlap minimization, where they represent overlap by the minimum horizontal translation required to resolve the overlap to zero. The subset contains the points that are vertices of NFPs, intersections of edges of NFPs or projections onto NFPs boundaries of other NFPs vertices that lay inside the first NFPs. Figure 11 illustrates these points where piece i and k are already placed and the positions for piece j are being evaluated.

Figure 11.

Discrete set of placement points for piece j at the boundaries of NFP_ij and considering the nearby placed piece k and its NFP_kj.

Full figure and legend (33K)

Blazewicz et al (1993) report a tabu search algorithm that reduces the infinite neighbourhood using a quite different strategy. Pieces are initially placed using a BL with hole filling placement rule in order of non-increasing area. A neighbour solution is found by moving one piece from its present position to a hole within the layout or to the end of the layout. This strategy provides a finite neighbourhood for each piece, but keeping the list of holes updated is a difficult and time-consuming task. Figure 12 illustrates the basic ideas associated with this algorithm.

Figure 12.

Finite neighbourhood of Blazewicz et al (1993).

Full figure and legend (74K)

If the continuous solution space is not approximated then other ways of defining a move are necessary to deal with the infinite neighbourhoods. Gomes and Oliveira (1999) extend the work of Oliveira and Ferreira (1993) by removing the need for a grid approximation of the pieces and stock sheet. They keep the strategy of random displacements over the layout of randomly selected pieces and randomly generate the move direction and distance while constraining the maximum distance a piece can move. As a result the neighbour solutions are fairly alike. Figure 13 illustrates the scope of the neighbourhood and a specifically generated move. The outer circle represents the maximum distance that piece A can move away from its present position in any direction, and the inner circle represents the randomly generated distance of an actual move and the line the randomly generated direction.

Figure 13.

Infinite neighbourhood movement based on pieces displacement over the layout.

Full figure and legend (56K)

A further consideration when defining the set of solutions is whether to permit overlap between pieces. Restricting moves to feasible positions alone can create a hilly solution space that is difficult to navigate. For example, when a solution is reasonably efficient, moving a piece will probably extend the length of the packing layout. Many such moves may be required in order to refine good solutions or escape local optima. As a result many researchers permit infeasible solutions in the solution space, and penalize the overlap in the objective function. This provides a smoother and more connected landscape for the search procedure. However, there is no guarantee that the final solution will not incorporate a small amount of overlap, which would be unacceptable from a nesting problem solution point of view.

In order to follow the strategy of permitting infeasible placements, the amount of overlap needs to be calculated. Computing the area of overlap between two polygons (Figure 14(a)) is a complex and computationally expensive task for one that is performed for every move evaluation. Further, it does not necessarily provide the best information on how far the solution is from feasibility or how difficult it will be to resolve the overlap. As a result researchers use alternative evaluations of overlap. A common alternative is to use a translation distance. The minimum penetration depth gives the minimum distance and direction that pieces have to be moved apart to eliminate overlap (Figure 14(b)). As this is still a complex procedure, researchers may fix the direction, such as horizontal or vertical, to compute the depth (Figure 14(c)).

Figure 14.

Overlap measures: (a) polygon intersection area; (b) minimum penetration depth; (c) horizontal penetration depth.

Full figure and legend (60K)

Relaxing the no-overlap constraint and penalizing it in the cost function creates a multi-objective problem. It is well documented that a key difficulty with such cost functions is managing the trade off between the two objectives. Two approaches to this problem are identified here. The first is to define weights for each cost element in order to obtain the desired balance. For example, Heckmann and Lengauer (1995) define the cost of a layout as the weighted sum of the total length of the layout, the sum of the pair wise overlap, and an additional cost that measures the overlap across the horizontal and vertical dimensions of the packing surface. To overcome the difficulty of balancing the trade-off between overlap and length, the weights are chosen dynamically. Bennell and Dowsland (2001) measure overlap as a horizontal translation and take the direct sum of overlap and length with no further weighting. They overcome the trade-off by using a compaction and separation phase (see Section 5.2.2).

The second approach is to separate the objectives so the search tries to optimize one at a time, possibly oscillating between each objective. For example, Bennell and Dowsland (1999) fix the stock sheet length and solve the overlap minimization problem. On achieving a feasible solution they reduce the stock sheet length. Pieces that are no longer fully contained in the stock sheet as a result of the shortening are assigned new random positions and the process starts again. Imamichi et al (2006) and Egeblad et al (2007) also adopt this strategy.

Other implementations have used multiple criteria in the objective function that encourage certain types of placement. In these cases the components of the cost function do not necessarily compete. For example, Lutfiyya et al (1992) defines an affinity relation that rewards placements of pieces where their adjacent edges have similar or the same gradients. This is combined with the sum of the distance of each piece from the origin.

Egeblad et al (2007) propose an innovative search method. They focus on the overlap minimization problem and simplify the infinite neighbourhood by searching in just the horizontal or vertical direction. Although this is still infinite, the single dimension of the search combined with some new geometric approaches allows them to evaluate all positions of one piece along that continuum. They compute the area of overlap along the chosen direction and select the minimum of the overlap function for the placement of the translated piece (Figure 15).

Figure 15.

Egblad et al (2007) overlap function along the horizontal direction.

Full figure and legend (83K)

5.2.2. Compaction and Separation algorithms

Compaction and Separation algorithms tackle the problem in a very different way to the above approaches. For convenience we will refer to them as compaction from now on. Compaction approaches model and solve the problem as a linear program where the objective is to minimize length and the constraints prevent or remove overlap and ensure pieces remain within the stock sheet. The constraints are defined by one or more edges of the NFP. Since the NFP represents the relative positions of the pieces, the constraints are relative rather than fixed in physical space. Hence, the pieces can move simultaneously. The LP model highly constrains the problem to a small area of the solution space since it only allows linear translations along a feasible path.

Before the mathematical model is formulated it is useful to visualize what is physically happening between the pieces and how the NFP is utilized in the formulation. Figure 16 illustrates three possible constraints between piece i and piece j, where the constraints are defined by the edges of the NFP. The arrows indicate the feasible side of the constraints in which piece j can move. Point v–u is the resultant vector of the positions of piece i and piece j relative to the NFP. In the figure, we have placed i at the origin of the NFP (ie u=0) and j at the position defined by vector v. In this example j lies in the feasible region for all three constraints; however, this is not necessarily the case. Clearly if v–u remains on the current side of the constraint then i and j will not overlap.

Figure 16.

Three constraint scenarios illustrated by the physical pieces and as the NFP representation.

Full figure and legend (39K)

In the example illustrated in Figure 16, only one of the three constraints is used so that the feasible region is not over constrained. However, when using the edges of the NFP that form a concavity then more than one constraint will be required to define the feasible region. Figure 17 illustrates two such examples. Note that in example (b) the constraints are defined by non-consecutive edges as a result of there being a convex vertex within the concavity. The next edge is defined as a constraint when the constraint line enters the interior of the NFP.

Figure 17.

Two examples of defining constraint edges where concavities are involved.

Full figure and legend (35K)

The LP formulation varies between the different published implementations with respect to the objective function and selection of edge constraints. However, the utilization of the NFP to define the no-overlap constraint is consistent throughout and defined as follows. Let piece i be positioned at (x_i,y_i), piece j be positioned at (x_j,y_j) and the equation of the edge that forms a constraint be denoted as ax+by=c, then for pieces i and j the no overlap constraint C_k is written as:

Additional constraints need to be defined to prevent the pieces from dropping off the edges of the stock sheet. Milenkovic et al (1992) and Bennell and Dowsland (2001) also defined bounds on the distance in which any piece is permitted to move. Such a restriction reduces the number of constraints in the LP, since only those pieces that are within twice this minimum distance of each other need to be considered in the no-overlap constraint set. As a result several consecutive LPs must be formulated and solved before the layout is fully compacted. However, by making small movements the pieces can move on a piecewise linear path, potentially exploiting more advantageous positions than can be reached in one linear move.

Stoyan et al (1996) defines the objective function as minimizing the difference between the start of the stock sheet and the end of the packing arrangement, min (z₂-z₁). Bennell and Dowsland (2001) employ the equivalent objective function. However, the beginning of the stock sheet is considered to be at zero, and hence they simply minimize the length of packing. Milenkovic et al (1992) define the objective function as maximizing _i=1ⁿf_ip_i, where f_i is defined as the desired direction for polygon i and p_i represents the position of the polygon i. They select the first constraint edge by taking the linear path that connects the origin of the NFP with the resultant vector v–u. The first intersection with the boundary of the NFP travelling from v–u towards the origin is the first constraint edge. Bennell and Dowsland (2001) simply identify the closest edge of the NFP as the first constraint edge, whereas Stoyan et al (1996) undertakes a process of evaluating each possible constraint edge and selecting the best.

Separation of overlapping pieces can also be performed using this approach. However, the LP will begin from an infeasible solution and therefore may not produce a final feasible solution. Bennell and Dowsland (2001) tackle the non-existence of a feasible solution by progressively relaxing the no-overlap constraints where overlap between pieces occurs. This is done by reducing the distance the pieces have to move apart to achieve feasibility. The aim is to achieve a reduced amount of overlap in each iteration of the LP. Gomes and Oliveira (2006) also relaxed these constraints in a more elegant way by introducing a dummy variable that accounted for the overlap between pieces and endeavoured to minimize this in the objective function.

6. Conclusions

In this paper we have discussed the main approaches to nesting problems. In order to provide an instructive account of research into nesting problems we have structured the paper according to what we see are the key decisions for designing a solution approach. Figure 18 provides a diagrammatic representation of this structure.

Figure 18.

General organization for nesting solution methods.

Full figure and legend (40K)

Each new publication brings better solutions to the benchmark test data sets (which can be found on the ESICUP web page, www.fe.up.pt/esicup), but it is interesting to note that these approaches arise from different decision paths through our structure (Figure 18). For example, Bennell and Song (2008a) work with sequences and partial solutions, Burke et al (2006) search over a sequence, Gomes and Oliveira (2006) and Egeblad et al (2007) search over the physical layout. As a result it is difficult to provide guidance as to where the most promising areas of research lie and we anticipate researchers continuing to find new and innovative approaches to solving the nesting problem.

In addition, we can identify a number of variants of the nesting problem that arise from real applications that we believe will provide fruitful research topics. There are examples of nesting problems that are embedded in other combinatorial optimization problems such as scheduling problems, path determination problems or open stack minimization problems. Constraints from operations management may be incorporated into the nesting problem, such as cutting complete groups of pieces in the textile industry, selecting the assortment of pieces to cut from a larger group of demanded pieces, or different quality zones on the stock sheet. The definition of a single stock sheet sufficiently long to pack all the pieces is not always realistic and so we need to solve problems with multiple stock-sheets, under an irregular cutting stock or irregular bin-packing framework. Finally more work is required with respect to dealing efficiently with the geometry such as pieces that contain arced edges. With such challenges in mind, we predict that researching the nesting problem has a long and exciting future.

References

1. Agarwal PK, Flato E and Halperin D (2002). Polygon decomposition for efficient construction of Minkowski sums. Comput Geom 21: 39–61. | Article |
2. Albano A and Sapuppo G (1980). Optimal allocation of two-dimensional irregular shapes using heuristic search methods. IEEE Trans Syst Man Cybernet 10: 242–248. | Article |
3. Art RC (1996). An approach to the two-dimensional, irregular cutting stock problem. Technical Report 36.008, IBM Cambridge Centre.
4. Babu AR and Babu NR (2001). A generic approach for nesting of 2-D parts in 2-D sheets using genetic and heuristic algorithms. Comput Aided Design 33: 879–891. | Article |
5. Bennell JA and Dowsland KA (1999). A tabu thresholding implementation for the irregular stock cutting problem. Int J Prod Res 37: 4259–4275. | Article |
6. Bennell JA and Dowsland KA (2001). Hybridising tabu search with optimisation techniques for irregular stock cutting. Mngt Sci 47: 1160–1172. | Article |
7. Bennell JA and Oliveira JF (2008). The geometry of nesting problems: A tutorial. Eur J Opl Res 184: 397–415. | Article |
8. Bennell JA and Song X (2008a). A beam search implementation for the irregular shape packing problem. J Heuristics. Doi: 10.1007/s10732-008-9095-x.
9. Bennell JA and Song X (2008b). A comprehensive and robust procedure for obtaining the nofit polygon using Minkowski sums. Comput OR 35: 267–281. | Article |
10. Bennell JA, Scheithauer G, Stoyan Yu and Romanova T (2008). Tools of mathematical modelling of arbitrary object packing problems. Ann Opns Res. Doi: 10.1007/s10479-008-0456-5. | Article |
11. Blazewicz J, Hawryluk P and Walkowaik R (1993). Using a tabu search for solving the two-dimensional irregular cutting problem. Ann Opl Res 41: 313–325. | Article |
12. Burke E, Hellier RSR, Kendall G and Whitwell G (2006). A new bottom-left-fill heuristic algorithm for the two-dimensional irregular packing problem. Opns Res 54: 587–601. | Article |
13. Burke EK, Hellier RSR, Kendall G and Whitwell G (2007). Complete and robust no-fit polygon generation for the irregular stock cutting problem. Eur J Opl Res 179: 27–49. | Article |
14. Dowsland KA, Dowsland WB and Bennell JA (1998). Jostle for position: Local improvement for irregular cutting patterns. J Opl Res Soc 49: 647–658. | Article |
15. Dowsland KA, Vaid S and Dowsland WB (2002). An algorithm for polygon placement using a bottom-left strategy. Eur J Opl Res 141: 371–381. | Article |
16. Dyckhoff H (1990). A typology of cutting and packing problems. Eur J Opl Res 44: 145–159. | Article |
17. Egeblad J, Nielsen BK and Odgaard A (2007). Fast neighborhood search for two- and three-dimensional nesting problems. Eur J Opl Res 183: 1249–1266. | Article |
18. Ferreira JC, Alves JC, Albuquerque C, Oliveira JF, Ferreira JS and Matos JS (1998). A flexible custom computing machine for nesting problems. Proceedings of XIII DCIS, Madrid, Spain, pp. 348–354.
19. Fowler RJ, Paterson MS and Tanimoto SL (1981). Optimal packing and covering in the plane are NP-complete. Inform Process Lett 12(3): 133–137. | Article |
20. Gomes AM and Oliveira JF (1999). Nesting irregular shapes with simulated annealing. In: Ribeiro C (ed). Extended Abstracts of MIC1999—III Metaheuristics International Conference, 19–22 July, Angra dos Reis, Brazil.
21. Gomes AM and Oliveira JF (2002). A 2-exchange heuristic for nesting problems. Eur J Opl Res 141: 359–370. | Article |
22. Gomes AM and Oliveira JF (2006). Solving irregular strip packing problems by hybridising simulated annealing and linear programming. Eur J Opl Res 171: 811–829. | Article |
23. Heckmann R and Lengauer T (1995). A simulated annealing approach to the nesting problem in the textile manufacturing industry. Ann Opl Res 57: 103–133. | Article |
24. Imamichi T, Yagiura M and Nagamochi H (2006). An iterated local search algorithm based on nonlinear programming for the irregular strip packing problem. Proceedings of the Third International Symposium on Scheduling (ISS06), Tokyo, Japan, pp 132–137.
25. Jakobs S (1996). On genetic algorithms for the packing of polygons. Eur J Opl Res 88: 165–181. | Article |
26. Konopasek M (1981). Mathematical treatments of some apparel marking and cutting problems. US Department of Commerce Report 99-26-90857-10.
27. Lutfiyya H, McMillin B, Poshyanonada P and Dagli C (1992). Composite stock cutting through simulated annealing. Math Comput Model 16: 57–74. | Article |
28. Milenkovic V, Daniels K and Li Z (1992). Placement and compaction of nonconvex polygons for clothing manufacturing. In: Wang CA (Ed.) Fourth Canadian Conference on Computational Geometry, St Johns's, Newfoundland.
29. Oliveira JF and Ferreira JS (1993). Algorithms for nesting problems. In: Vidal R.V.V. (ed). Applied Simulated Annealing. Lecture Notes in Economics and Maths Systems Vol. 396. Springer Verlag: Berlin, pp. 255–274.
30. Oliveira JF, Gomes AM and Ferreira JS (2000). TOPOS—A new constructive algorithm for nesting problems. Opns Res Spec 22: 263–284.
31. Ribeiro C and Carravilla MA (2004). global constraint for nesting problems. In: Régin JC and Buehe M (eds). Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. Lecture Notes in Computer Science, Vol. 3011. Springer: Berlin, pp 256–270.
32. Segenreich SA and Braga LM (1986). Optimal nesting of general plane figures: A Monte Carlo heuristical approach. Comput Graph 10: 229–237. | Article |
33. Stoyan YG, Novozhilova MV and Kartashov AV (1996). Mathematical model and method of searching for a local extremum for the non-convex oriented polygons allocation problem. Eur J Opns Res 92: 193–210. | Article |
34. Stoyan YG, Terno J, Scheithauer G, Gil N and Romanova T (2001). Phi-functions for primary 2D-objects. Stud Inform Univ 2(1): 1–32.
35. Takahara S, Kusumoto Y and Miyamoto S (2003). Solution for textile nesting problems using adaptive meta-heuristics and grouping. Soft Comput 7: 154–159.
36. Wäscher G, Hauner H and Schumann H (2007). An improved typology of cutting and packing problems. Eur J Opns Res 183: 1109–1130. | Article |