An efficient algorithm for irregular pattern nesting based on genetic algorithm and greedy strategy

Abstract

Within various industrial settings, such as shipping, aeronautics, woodworking, and footwear, there exists a significant challenge: optimizing the extraction of sections from material sheets, a process known as “nesting”, to minimize wasted surface area. This paper investigates efficient solutions to complex nesting problems, emphasizing rapid computation over ultimate precision. We introduce a dual-approach methodology that couples both a greedy technique and a genetic algorithm. The genetic algorithm is instrumental in determining the optimal sequence for placing sections, ensuring each is located in its current best position. A specialized representation system is devised for both the sections and the material sheet, promoting streamlined computation and tangible results. By balancing speed and accuracy, this study offers robust solutions for real-world nesting challenges within a reduced computational timeframe.

Keywords

Genetic algorithm 2D nesting irregular pattern cutting industrial automation

1 Introduction

Nesting, the optimization of surface area usage through strategic arrangement of parts from a material base, is a prevalent challenge across industries such as shipping, aeronautics, woodworking, and footwear. The core objective is to minimize surface area consumption during extraction, with the problem intricacies magnified when handling irregular pieces.

Historically, tackling the nesting of irregular pieces —categorized as an NP-hard problem—has been daunting due to the computational demand in finding optimal solutions within a vast solution space, leading academia and industry towards heuristic algorithms for acceptable, less computationally intensive outcomes. Despite automation advancements and nesting management tools, many sectors still depend on manual operations, where material wastage and efficiency hinge on operator skill, often resulting in prolonged cutting durations and higher costs.

This paper proposes a novel nesting approach prioritizing computational speed over precision, combining a greedy technique with a genetic algorithm (GA) for optimal piece placement sequencing. Additionally, our introduced enhanced representation system for both pieces and the material sheet aims to streamline the nesting process, aligning with contemporary industry demands.

2 State-of-the-art

2D piece nesting is integral to various industries, with its nature defined by the geometry of pieces involved, categorizing it into regular and irregular nesting. Regular nesting mainly involves extracting rectangular shapes, common in the glass industry, while irregular nesting deals with non-rectangular shapes, typical in industries like footwear and textiles.

The nesting procedure, particularly for irregular shapes, has seen significant advancements, generally comprising three crucial stages:

1.
Establishing a suitable geometric representation for pieces to manage their irregularities, and the sheet’s if needed.
2.
Creating a system to identify interference, a challenge amplifying with the complexity and number of parts.
3.
Developing a heuristic to optimize piece placement on the material sheet.

A literature review unveils numerous strategies and algorithms devised to address this issue.

Freeman and Shapira [1] proposed a novel method for representing curves during the nesting phase, central to which is the “chain coding scheme”. This scheme transforms an arbitrary plane curve into a sequence of straight-line segments superimposed on a finite-space square grid. The intersection points between the curve and grid are connected sequentially, forming a chain-coded representation of the original curve. The method unfolds in two primary stages: initially identifying the curve’s convex hull, and subsequently finding the minimum area rectangle encompassing this hull. The latter stage involves assessing various rectangles aligned with the convex polygon’s edges, selecting the rectangle that minimizes area while fully containing the curve as the optimal solution.

Siasos and Vosniakos [2] presented a comprehensive solution to the nesting problem via a 4-way representation system for part modeling, starting with a detailed 2D vector model incorporating geometric elements like straight lines, circular arcs, and splines. Their strategy, named Bottom-Left-Fill-Left (BLFL), unfolds in two phases. Initially, parts are converted into raster form, facilitating rapid placement on the material sheet by identifying suitable vacant lower-left sections, aiming for a swift near-optimal arrangement. Subsequently, placement refinement occurs to enhance accuracy and material utilization. A GA is employed to ascertain the optimal nesting sequence. The GA initializes with a population of various part sets, termed “chromosomes”, each undergoing the BLFL nesting procedure, then ranked based on material sheet utilization efficiency. Genetic crossover operations are applied to inter-breed ranked chromosomes, producing new generations aimed at continually refining the nesting sequence for maximal efficiency.

Babu and Babu [3] introduced an innovative nesting solution employing a unique integer encoding system. Parts are encompassed within an “imaginary” rectangle, its surface segmented into a uniform 1×1 mm grid, termed as pixels. Pixel values are assigned based on their geometric relation to the part: 0 for pixels within or touching the part’s outline and incrementing positive values from right to left for pixels outside the outline. This encoding spans all possible orientations of each piece. During nesting, parts are systematically positioned on the sheet, moving along the x-axis until a perfect match of zero-valued pixels between the part and sheet is achieved. A GA optimizes the sequence of parts and sheets, including their orientations. Here, chromosomes represent parts, sheets, and their respective rotation angles. Crossover operations adjust sequences, while mutations alter both sequences and rotation angles, ensuring the most efficient orientation for every part.

Prasad et al. [4] proposed a nesting technique based on a three-dimensional matrix representing the number of parts, their features, and entities within those features, which include elements like lines, arcs, and points. The MPSR (Moving Part Slide Right) algorithm was devised to facilitate nesting, targeting pairs of parts. Within a pair, the part with more vertices is set as “fixed”, while the other part, termed “moving”, slides its edges counterclockwise against the “fixed” part without overlapping. The highest y-coordinate vertex on the “moving” part aligns with the lowest y-coordinate vertex on the “fixed” part, termed the sliding vertex. A “guide” segment is chosen for the “moving” part to slide along until interference occurs, producing the next sliding vertex. This cycle repeats until the sliding vertex returns to its initial position. In multi-part scenarios, initial nesting occurs for a pair, with their combined boundary treated as a “composite” part for further nesting. Upon nesting all parts, they merge into a singular part, reoriented between 0° and 180° to find the optimal position on the sheet, selecting the orientation that maximizes material usage.

Jakobs [5] utilizes the Bottom Left (BL) algorithm aiming to place pieces as far left and as low as possible on the sheet, following a specific sequence determined by piece identifiers. Sequence generation employs a GA, with a fitness function measuring the occupied height on the sheet, selecting sequences with least area in case of identical heights. Nesting initiates with pieces sequenced in ascending width order. Sequences undergo a unique crossover operation, generating new sequences from two random numbers derived from existing sequences to determine the starting piece. A mutation operation rotates a randomly chosen piece by 90° within a sequence. This iterative process continues until a specified upper limit is met or no improvements are detected within a set timeframe. For polygonal pieces, a three-phase algorithm is suggested: (a) embedding polygons in minimal area rectangles by rotating them around their gravitational center at fixed angular increments, (b) nesting these rectangles on the material sheet using the GA, and (c) zooming in to address gaps between polygons if no sequence improvements are observed, with a mirror effect applied for added precision.

Han and Na [6] introduced a nesting methodology incorporating polygon approximation and pattern decomposition into rectangles and circles to model pieces, reducing data processing and execution time. Parts are classified as either basic components (rectangles and circles) or irregular parts, decomposed manually using an interactive graphics tool. Overlap computation between parts employs straightforward coordinate comparisons, applicable to both basic and irregular components. The nesting algorithm comprises two stages: the Initial Design Stage (Self Organization Assisted Layout-SOAL) and the Improvement Stage (Simulated Annealing-SA). SOAL integrates the Self-Organizing Map (SOM) and Fuzzy c-means (FCM) to autonomously regulate learning rate distribution, initially centering parts on the sheet with small random position vector values, adjusted during self-organization. The SA algorithm, akin to iterative improvement algorithms, uniquely permits perturbations, utilizing Monte Carlo method foundations and Markov chain concepts. Both stages allow part rotations in 90° increments.

Pinheiro, Amaro, and Saraiva [7] propose a nesting method utilizing the no-fit polygons (NFP) technique for efficient geometry handling in cutting and packing problems with irregular shapes. In this method, polygons are generated from pairs of pieces, designated as “fixed” and “orbital”. The orbital piece slides over the fixed piece, relative to a reference point on the boundary of the generating no-fit polygon. A Random Key Genetic Algorithm (RKGA) is employed to evolve a population of chromosomes across generations. The population, initially comprising p chromosomes, is divided post-fitness evaluation into elite and non-elite groups. The RKGA employs an elitist strategy, copying elite individuals to the next generation, introducing p_m mutants via mutation, and conducting a crossover process to include requisite individuals. Solutions are encoded as vectors X = (X₁, …, X_3n), where n is the total number of figures to be nested. Components X₁, …, X_n form the item type packing sequence (ITPS); X_n+1, …, X_2n design the rotation variant vector (RVV); and X_2n+1, …, X_3n correspond to the placement procedure vector (PPV), establishing the nesting rule for each figure. Three placement rules (bottom left, greedy bottom left, and the no-fit polygon heuristic) are utilized, with solutions generated by decoding the solution vector X.

Elkeran [8] outlines a nesting method commencing with a list of polygons P = (P₁, P₂, …, P_n) and their allowed orientations O = (O₁, O₂, …, O_n) on a rectangular sheet C with a fixed width W and variable length L. A polygon Pi is positioned by a vector v_i = (x_i, y_i) from its reference point. The nesting solution is denoted by lists of positions v = (v₁, v₂, …, v_n) and orientations o = (o₁, o₂, …, o_n), uniquely determining the polygon layout. The Guided Cuckoo Search (GCS) algorithm tackles the problem in two phases: minimizing sheet length and minimizing overlap. Overlap minimization, a nesting subproblem, permits polygon overlaps but not overhangs on sheet C, penalizing total overlap to attain a feasible location. This is addressed via a guided local search combined with the cuckoo search algorithm, moving polygon P_k within the sheet C to reduce overlap. The initial feasible solution employs the bottom-left heuristic, transferring polygons to feasible locations using the no-fit polygon (NFP). Solution quality and initial design enhancement are achievable by clustering polygons with matching features into paired groups, promising better designs with high polygon counts in reduced run time.

Toledo et al. [9] introduce a nesting method utilizing the dotted-board model to represent the sheet, achieved by placing a grid of defined points at a suitable resolution. Each piece is denoted by a polygon with vertices coordinates relative to a reference point. The relation between the part and the sheet is established by the Inner Fit Polygon (IFP) which marks all permissible positioning points for the part, ensuring its complete containment within the board. Overlap avoidance between parts is handled through the No-Fit Polygon (NFP) for part pairs. For two parts, u and v, NFP_u,v is the geometric locus of points such that, if the reference point of part u is inside NFP_u,v, the parts overlap; if on the edges of NFP_u,v, the parts touch each other; and if outside NFP_u,v, the parts do not touch each other.

Valvo [10] presents a solution to the nesting problem by enhancing a heuristic positioning technique, Bottom Left Fill, coupled with the no-fit polygon (NFP) concept. The part placement technique heavily relies on a nesting method employing the NFP polygon for positioning, which although enhances the process, elevates computational complexity. The positioning commences by placing the first piece in the lower left corner of the sheet. Subsequent pieces act as “orbital polygons” on the preceding piece (the “fixed” piece) to derive the NFP, examining the entire perimeter to find the point with the smallest y-coordinate. If y-coordinates are equal, the smallest x-coordinate is selected. This nesting procedure is implemented in Python, utilizing specialized libraries like Polygon for geometric and Inspyred for metaheuristic problems.

Cherri et al. [11] introduce a data structure to store essential geometric information for solution methods based on discretized feasible regions. Utilizing the non-fit polygon (NFP) to assess piece overlap and the inner polygon (IFP) to ensure piece containment within the sheet, this structure keeps only the points on the sheet where one or more rotations can be placed for each piece type to be nested, along with overlap information between pieces. The proposed dotted-board model defines a regular grid by filling the board with points in vertical and horizontal spacing, with any point being a feasible placement point as long as pieces are completely contained within the sheet and do not overlap. This data structure’s versatility allows for alternative meshes, not just regular ones, where point spacing remains invariant, irrespective of part type and rotation. Two mesh types are proposed: one based on the parts to be nested, with point distances based on distances between the part type vertices, and another based on NFP, adjusting the mesh to the geometry of the given part set as closely as possible.

Other relevant recent research works on 2D nesting can be analyzed in Fang et al. [12], Ranga et al. [13], Mundim et al. [14], Guo et al. [15], Liu et al. [16], Muhammed et al. [17], Rao et al. [18], Queiroz and Andretta [19], Zhao et al. [20], Leao et al. [21], Baldacci et al. [22], Du et al. [23], Xu et al. [24], Mundim et al. [25], Sato et al. [26], and Diyaley and Chakraborty [27].

In summation of the research review, it is discernible that various significant research endeavors encompassing some or all sides of the 2D part cutting problem across diverse industrial domains have been elucidated.
3 Methodology

3.1 Problem definition

This study tackles a core material nesting optimization problem: given a quadrangular sheet of fixed dimensions and a set of pieces with varying geometries (regular or irregular), the objective is to strategically arrange these pieces on the sheet to maximize surface area occupation. With only a single sheet available, a configuration accommodating all pieces within the sheet’s bounds is sought; failure to find such a configuration renders the nesting task unsuccessful. Nesting efficiency and material usage extent are gauged by establishing a distinct vertical boundary at the rightmost edge of the arranged pieces. The area to the right of this boundary signifies the sheet’s unoccupied or residual portion, indicating material underutilization.

3.2 Input

The nesting process begins with parts designated for nesting, encapsulated within DXF files, read using the dxflib library. These parts are visualized and drawn using LibreCAD software, handling various geometric entities crucial for forming the desired figures. Upon parsing the DXF file, geometric entities are stored in a section labeled ENTITIES, which acts as a repository for each entity contributing to the figure construction. The attributes and parameters of these entities are captured and stored within specific classes like Point, Line, Circle, and Ellipse, collectively formulating a vector representing the figure.

Following vector acquisition, entities comprising the part are transposed to the Cartesian coordinate system’s second quadrant, ensuring a uniform starting point for all pieces. Each piece is repositioned to be as leftmost and downward as possible, standardizing positioning for accurate rendering irrespective of its location within the coordinate system.

Post-relocation, the part is rendered as a PNG image file, crucial for determining the central rotation point to facilitate varied orientations. This rendering task is managed using the OpenCV artificial vision library, chosen for its expedited figure rendering capabilities. Lastly, conforming to the problem definition, the surface for piece placement is either square or rectangular, with its precise dimensions predetermined and input into the system at the process commencement.

3.3 Spatial coding

To ensure successful nesting, a congruent coordinate system is employed, utilizing a semi-discrete representation system that segments elements into consistent rectangular sections, known as strips. A limitation, as shown in Fig. 1, is potential free surface wastage when a strip houses only a small part fragment.

Fig. 1

Semi-discrete representation of a piece.

Addressing this, our study introduces a semi-discrete representation, an advanced iteration of the discrete model. This representation segments both parts and sheet into vertical strips of consistent width, except the final strip, whose width can be reduced or kept equivalent to preceding strips. This design choice minimizes unutilized free surface on the rightmost part section, enhancing nesting efficiency.

3.3.1 Pieces spatial coding

The adoption of a semi-discrete representation typically results in a more compact enveloping rectangle for a part compared to a discrete representation. Given its effectiveness, this representation is applied to all parts across all possible orientations, aiding in constructing an occupancy table for each orientation, as depicted in Fig. 2. In this figure, it can be observed that segment 1 of the piece comprises from 0 to 86 mm, while segment 6 comprises a first section from 10 to 17 mm and a second section from 66 to 93 mm.

Fig. 2

Tabular illustration of semi-discrete representation of the piece in Fig. 1 (mm).

The process begins with the extraction of a PNG image from the part’s corresponding DXF file. Through OpenCV, the image is processed to identify points defining its outline. Following this, the outline is segmented into strips according to a predetermined width, as demonstrated in the constructed occupancy table in Fig. 2.

3.3.2 Sheet spatial coding

In sheet material context, strip fractions represent unoccupied spaces. Initially, with an empty sheet, each strip’s range spans from 0 to the sheet’s full height, with strip width denoted in the vacancy table’s final row. As nesting progresses and parts occupy the sheet, the vacancy table updates accordingly, illustrated in Fig. 3. In this figure, it can be observed that strip 1 is free from 86 to 200 mm, while strip 5 has two free section, from 0 to 10 mm and from 92 to 200 mm, respectively. Notably, a 5 mm width for strips 9 and 10 arises from the semi-discrete representation’s modulation, halving the final strip’s initial 10 mm width, thus increasing the representing strips and computational overhead for part positioning.

Fig. 3

Vacancy table for the sheet area as depicted above, values in mm.

Computationally, aligning strip width harmoniously with parts is vital. This alignment minimizes terminal strip simplifications for each part orientation, optimizing computational time. Essentially, a broader, compatible strip width enhances accuracy and computational efficiency over a misaligned, narrower alternative.

3.3.3 Obtaining the orientations of a part

The precise rotation of a part necessitates a reference point, identified as the part’s geometric center or centroid, extracted using the OpenCV library through a series of processing steps on the part’s image. Initially, the image is transformed into grayscale, then binary format, followed by contour extraction. To enhance accuracy, a filtering phase is integrated, leading to the computation of image moments up to the third order for the resultant polygon from the filtered contour, from which the centroid’s coordinates are derived using spatial moments of orders 0 and 1.

Furthermore, part orientation is crucial, methodically achieved by rotating the part through predefined angular intervals from 0° to 360°. An interval of 0° or 360° maintains the original orientation, while a 45° interval yields eight discernible orientations. Each orientation, with its unique vector reflecting the rotated part’s entities and distinct centroid, is not only differentiated by its semi-discrete representation but also by its distinct centroid.

3.4 Search

The nesting process’s core search mechanism aims to find feasible part locations on the sheet, utilizing fractional ranges within each strip to represent sheet vacancy. These ranges highlight unoccupied sheet segments, aiding in assessing if a part’s occupancy requirements are met.

The search procedure is systematic, initiating with the feasibility analysis of placing a workpiece’s leftmost strip on the sheet. If viable, similar examination extends to the workpiece’s subsequent strips. The search traverses the sheet’s vacancy table from the bottom-left corner, moving upwards, then rightwards.

Various scenarios arise during this exploration. If a sheet strip can accommodate the workpiece’s leftmost strip, the part is positioned on the sheet, aligning the bottom edges of both the part’s occupancy and the sheet’s vacancy segments. However, interference with already placed parts prompts elevation of the recently placed part segments by the interference’s height. If no feasible placement is found, the examination shifts rightward to the next sheet strip, continuing until the entire workpiece finds a suitable position (Fig. 4). If the sheet’s rightmost segments lack required space, it is inferred that the workpiece cannot be nested within the current sheet layout.

Fig. 4

Repositioning of the piece strips until a feasible position is achieved.

3.5 Placement

The complexity of the nesting problem is underscored by its NP-hard nature, indicating that obtaining an optimal solution for all pieces collectively might be computationally daunting, especially given the vast spectrum of potential solutions. To navigate this challenge, our research pivots towards a synergistic approach that harnesses the capabilities of the Greedy Method, further enhanced by a GA. The primary objective of this combined method is to devise an efficient layout for all the pieces. Thus, while the greedy algorithm selects the best position for each piece, the GA is in charge of exploring the order of the next pieces to be placed. The strategy operates in a cyclical manner, as visualized in Fig. 5. The iterative process concludes when the algorithm identifies no enhancements across n consecutive iterations, or generations, in relation to the performance metrics of the previously identified optimal part sequence. Detailed insights into the various stages of this algorithm will be analyzed in the succeeding sections.

Fig. 5

Greedy method flowchart.

3.5.1 Parts orientation order

Initially, the algorithm necessitates defining an orientation order for positioning each part, achieved by constructing enveloping rectangles using strips for every feasible orientation, as elaborated in subsection 3.3.1. The prioritization of orientations adheres to three key principles:

1.
Width Consideration: Favoring orientations with smaller enveloping rectangle widths promotes space efficiency.
2.
Gravity Center Proximity: Preferences are given to orientations where the center of gravity is nearer to the enveloping rectangle’s bottom edge, facilitating better accommodation of subsequent parts and enhancing nesting efficiency.
3.
Orientation Similarity: Given close matches based on the aforementioned criteria, the latter orientation is prioritized.

An intriguing facet is the potential mirror effect application on pieces, pertinent when sheet material is uniform on both sides. This effect, executed by altering coordinate signs in the part-representing vector, generates mirrored vectors, and consequently, two distinct PNG images for each rotation –one for the original and another for the mirrored part, effectively doubling the orientation count e.g., from eight to 16 for a piece with a 45° rotational interval (Fig. 6).

Fig. 6
(a) Current part. (b) Derived orientation order from the current part (45° rotation interval and mirror effect).

The motive behind this orientation order is to streamline the part placement search process. Upon identifying a feasible position for a part with a specific orientation, it sets an “upper bound” for subsequent orientations of the same part (Fig. 7), denoting the strip number on the surface where the part’s initial strip is placed. As illustrated in Fig. 6, if a subsequent orientation secures a superior position, it establishes a new upper bound, ensuring efficient and optimal part placement on the sheet.

Fig. 7
Setting an upper limit, using the established orientation order of a piece (right).
3.5.2 Sequence generation mechanism

The algorithm’s second stage necessitates a robust sequence-generating mechanism to aid part placement, employing GA for its evolutionary optimization process. In this context, GA encodes potential solutions as sequences (chromosomes), with each cell in a sequence representing a different piece. Initially, sequences are randomized, with the leftmost cell dictating the first part to be placed. For instance, Fig. 8(a) shows a sequence where the first piece to be placed would be piece #4 and the last piece to be place would be piece #5. Post-placement, inefficient sequences (higher surface usage) or those failing to provide feasible placements are discarded. Conversely, high-performing sequences undergo crossover and mutation, while new random sequences replace discarded or invalidated ones.

Fig. 8

Generating a parts sequence by GA showcasing: (a) Encoding of a chromosome; (b) Crossover operation; and (c) Mutation operation.

Given the permutation nature of the part sequence problem, traditional crossover operations are inadequate as they might omit certain parts. Hence, single chromosome crossover operation is utilized, swapping segments of two chromosomes based on a random pivot, as illustrated in Fig. 8(b).

Mutation operation, depicted in Fig. 8(c), involves randomly selecting a sequence and swapping one of its cells with a neighboring cell, ensuring every potential solution remains under consideration.

To sum up, the tuning of the GA is as follows: –

Every sequence is applied the crossover (swapping) operation.

–

The mutation operation is performed on at least one of the current sequences and at most on all of them according to a uniform random value.

Two record-keeping steps accelerate the process and stabilize the optimal sequence. The “historical” record contains all GA-generated sequences to prevent re-evaluation, reducing computation time. The subsequent record preserves the best-performing sequence, replacing it only if a new sequence exhibits lesser surface occupation.

3.5.3 Optimizing position and orientation of a part within a sequence

Upon generating multiple part sequences via the GA, the pivotal part placement phase begins, serving to evaluate sequence performance and ensure optimal nesting. This step, detailed in Fig. 6, aims to streamline part orientation selection efficiently, utilizing the upper bound discussed in subsection 3.5.1.

Orientations are ranked based on predefined criteria (Fig. 6), setting an upper limit for successive orientations of the same part. The logic is clear: during the search for a feasible space for a part’s foremost strip, surpassing or reaching the set upper limit by a higher-ranked orientation halts the search, as any position found henceforth is deemed inferior in performance to the orientation setting the limit.

The search methodology, while exhaustive, is efficient. In a worst-case scenario necessitating exploration of every possibility, a thorough examination of each orientation and its corresponding strips for a part is mandated. Conversely, in a best-case scenario, the search may be concise, potentially requiring analysis of just one orientation, with subsequent orientations needing only a first-strip assessment.

3.6 Output representation

Upon acquiring the optimal sequence post-n generations, the nested sheet encompassing all selected pieces is rendered in a vacancy table format, transitioning to a more visually intuitive DXF file format for user-friendliness in the final stage, utilizing the dxflib library for file creation. Each tuple in this representation consists of three elements: the original part identifier denoting each part’s unique identity; the original part rotation identifier specifying the part’s orientation; a starting point marking the initiation for rendering the respective orientation within the DXF file. This structure eases access to each entity vector of the respective orientations and streamlines the rendering process. Through the dxflib library, each part orientation is drawn from its designated starting point, ensuring clarity and precision in the final visual depiction.

4 Experimentation

To substantiate the presented approach, various patterns—both regular and irregular—were subjected to tests. This was complemented by varying the parameters integral to the method. These parameters include:

•
Total amount of generations.
•
Sequence count within each generation.
•
Strip width in the semi-discrete representation for both pieces and the sheet.
•
The angle of rotation assigned to the pieces.

The ensuing case studies have been executed in a testing milieu, underpinned by an Intel Core i5-7200U processor operating at 2.50 GHz. Notably, during the sequence formulation using the GA, a sample size of 10 chromosomes (or sequences) was consistently adopted. It is worth mentioning that the experimentation process was designed to halt if there was a lack of performance improvement observed across 30 successive iterations (or generations).

The programming and graphics environments used were Visual Studio Code 1.78 and OpenCV 2.7.0.
4.1 Case study 1

In the initial experiment, the aim was to optimally place 28 uniquely shaped, irregular pieces (Fig. 9) on an 80×50 cm material surface. The rotation interval was set at 45° to establish orientation order for each piece. Various strip widths in the semi-discrete representation were explored, with performance distinctions noted in Table 1 when applying the algorithm.

Fig. 9

Selected patterns for the first case study.

Table 1

Results obtained from case study 1

Strip width	1	2	3	4
Occupied surface (mm)	488	480	534	550
Computation time (s)	4.303	0.849	0.365	0.343

Execution time escalated as strip width diminished, attributed to the increased number of strips requiring computation during feasible position search. However, reduced strip width didn’t always enhance nesting accuracy, as broader strips potentially aligned better with pieces, needing fewer evaluations during the search process. This was corroborated by results where 1 cm and 2 cm strip widths produced outputs of 488 mm and 480 mm sheet occupancy, respectively. Performance enhancement was observed within the initial 10 to 20 generations (Fig. 10), except in the case of a 3 cm strip width where performance settled across 30 iterations, suggesting comparable outcomes might be attainable with fewer generations, thereby lessening computation time. The evaluation’s final outcome is displayed in Fig. 11.

Fig. 10

Occupied surface versus count of generations for varied strip widths (black = 1 cm; grey = 2; yellow = 3; blue = 4 cm).

Fig. 11

Final nesting of case study 1 (strip width = 2 cm).

4.2 Case study 2

In case study 2, 31 distinct irregular parts are examined for placement on an 80×60 cm sheet, depicted in Fig. 12, with a rotation interval of 30° and varying strip widths. Table 2 shows algorithm execution comparisons, indicating, like the preceding case, that broader strip width reduces computation time without directly enhancing nesting precision.

Fig. 12

Shapes used in case study 2.

Table 2

Algorithm execution comparisons

Strip width (cm)	1	2	3	4
Occupied surface (mm)	570	620	600	720
Computation time (s)	10.8	1.343	0.73	0.334

Notably, computation time escalates due to increased piece count and augmented total orientations per piece, with this case exhibiting 12 orientations compared to the former’s 8. Figure 13 illustrates that fewer generations yield comparable results in a reduced timeframe, except in the third graph where performance enhancement occurs between the 20th and 30th generations, suggesting a decrease in generations might yield inferior performance. The final placing is shown in Fig. 14.

Fig. 13

Occupied surface versus number of generations for different strip width (brown = 1 cm; grey = 2; yellow = 3; blue = 4 cm).

Fig. 14

Outcome of the second case study (strip width = 3 cm).

4.3 Case study 3

In the third experiment, 35 irregular parts comprising four distinct patterns are arranged on an 80×60 cm sheet, as illustrated in Fig. 15. A rotation interval of 1° is assigned to each piece, with strip width values retained from previous cases. Table 3 encapsulates the results. Compared to earlier cases, computation durations significantly extend due to the expansion of orientations per piece from 12 to 360, following the 1° rotation interval. A stark contrast in execution time is observed for a strip width of 1 cm versus other widths, attributable to executing 100 generations in the 1 cm case, as opposed to a maximum of 50 generations in other cases.

Fig. 15

Shapes used in case study 3.

Table 3

Results obtained from case study 3

Strip width (cm)	1	2	3	4
Occupied surface (mm)	440	440	540	480
Computation time (s)	277.69	16.04	7.525	2.658

The best results concerning accuracy and computation time are observed using 2 cm and 4 cm as strip widths. Figure 16 suggests that reducing the number of generations could truncate computation times, potentially at the expense of performance deterioration. A viable alternative might be diminishing the sequences per generation to secure a more favorable time/performance ratio. Results are shown in Fig. 17.

Fig. 16

Occupied surface versus count of generations for different strip width (grey = 1 cm; brown = 2; yellow = 3; blue = 4 cm).

Fig. 17

Final outcome of the third case study (strip width = 2 cm).

4.4 Case study 4

In the fourth case study, 50 copies of a singular piece type are arranged on a 140×80 cm sheet with varying rotation intervals, as depicted in Fig. 18. Given the uniform piece type, sequence generation via the GA is deemed unnecessary, maintaining a constant nesting order. A width of 2 cm is employed for the strips alongside diverse rotation interval values, with results encapsulated in Table 4.

Fig. 18

Shape used in case study 4.

Table 4

Results obtained in case study 4

Rotation interval (deg)	1	5	15	35	45	55
Occupied surface (mm)	980	1040	1140	1100	980	1180
Computation time (s)	0.203	0.054	0.035	0.032	0.031	0.031

The data reveals that a smaller rotation step escalates the computation time without corresponding enhancement in material surface utilization. This is exemplified by the rotation steps of 1° and 45°, achieving identical surface utilization but with a reduced computation time for the 45° rotation interval, showcasing a time difference of 0.172 s between them. Since this case exclusively involves a single piece type, sequence generation is omitted, hence a performance graph is not necessary. The resultant nesting is depicted in Fig. 19.

Fig. 19

Final nesting of case study 4 (rotation interval = 45°).

4.5 Comparing performance with a commercial application

A comparative analysis is provided between the proposed nesting technique and an online tool from CNC-APPS [28], utilizing its unique proprietary algorithm, based on the earlier examined case studies. The comparison, focusing on surface utilization and computation time, keeps all parameters consistent across both methods, barring the non-configurable strip width in the commercial tool. Table 5 presents performance metrics and computation time, showcasing superior nesting precision and processing speed of the proposed method in case studies 1 and 3, except in case study 3 with a 1 cm strip width due to intensive iterations prolonging the time significantly. Table 6 illustrates that in case study 4, despite slightly less effective surface utilization, the proposed method considerably reduces computation time, attributed to the single piece type used eliminating the need for sequence creation via GA, thus streamlining the process. The results affirm the proposed method’s objective of balancing accuracy and efficiency in part arrangement, with commendable surface utilization and generally favorable computation times, often surpassing expectations. Notably, compared to the CNC-APPS tool, the proposed method demonstrates a significant advantage in handling pieces with inner holes, a feature apparently not well-supported by the online tool.

Table 5
Results comparison between proposed method and benchmark for case studies 1 and 3

Case 1 Case 3

Strip width (cm) 1 2 3 4 1 2 3 4

Benchmark surface occupation (mm) 600 596

Proposed approach surface occupation (mm) 480 480 534 550 440 440 540 480

Benchmark computation time (s) 22 38

Proposed approach computation time (s) 4.303 0.849 0.365 0.343 277.69 16.04 7.525 2.658

	Case 1	Case 3
Benchmark surface occupation (mm)	600				596
Proposed approach surface occupation (mm)	480	480	534	550	440	440	540	480
Benchmark computation time (s)	22				38
Proposed approach computation time (s)	4.303	0.849	0.365	0.343	277.69	16.04	7.525	2.658

Table 6

Results comparison between proposed method and benchmark for case study 4

Rotation interval (deg)	1	5	15	35	45	55
Benchmark surface occupation (mm)	980	990	995	1100	965	1050
Proposed approach surface occupation (mm)	980	1040	1140	1100	980	1180
Benchmark computation time (s)	42	45	42	41	35	36
Proposed approach computation time (s)	0.203	0.054	0.035	0.032	0.031	0.031

5 Discussion

The evaluation of various experimental scenarios suggests that the proposed method, given suitable parameter values, renders competitive performance and processing speed compared to CNC-APPS. It’s important to note, in many industrial applications, nesting procedures are extensively employed with substantial part quantities. Verifying the feasibility of nesting all parts on the sheet is critical, especially when the total surface area of all parts closely matches the sheet’s surface area. Once achieved, the emphasis shifts to optimizing part placement to minimize material wastage, a heightened concern with high-cost sheet materials. Therefore, discussions on scenarios with fewer parts to be nested on a large sheet become less relevant, as such tasks are easily managed through human intervention.

In summary, our method meets the expectations, delivering competitive results compared to the commercial online tool.

6 Conclusions

This study introduces a comprehensive solution to the longstanding nesting or packaging challenge. By integrating a greedy methodology to determine the optimal positioning for each element within a designated sequence and introducing the novel semi-discrete representation for spatial coding, we have advanced the field’s understanding and capabilities. The application of the Genetic Algorithm for sequence formation and the iterative strategy to enhance performance ensures that the computational time remains feasible.

The proposed method only considers a small subset of the enormous solution space. The experimental outcomes point towards a trend of reduced incremental gains in performance with the inclusion of more generational iterations.

A significant factor underpinning the method’s efficiency is the upper bounding strategy. It operates on the assumption that every component in the sequence occupies its most suitable current position. This not only accelerates the iterative process but also circumvents the exhaustive examination of all strips across different part orientations. Instead, in the best-case scenario only the initial orientation of a component and the leftmost strip of its succeeding orientations are checked. Another notable mention is the semi-discrete representation, simplifying the material sheet’s state update, thereby contributing to the method’s efficiency. Regarding effectiveness, the approach strives for optimal part placement following a sequence order, rather than pursuing stringent optimization. The experimental outcomes affirm the commendable performance of the proposed approach across all examined examples.

Looking ahead, several avenues for enhancing the presented method are identified: –

Redundancy elimination: for parts exhibiting geometric symmetry, certain rotation angles, yielding identical orientations, can be disregarded, thereby reducing the orientation count examined during part placement. For instance, considering rotation angles between 0° to 180° for a rectangular part cuts down orientations from 8 to 4.

–

Incorporating a minimal gap: given potential machine errors during real sheet material cutting, introducing a predefined gap at the onset could be a viable solution. In this way, although the sheet area used could be increased, there is less chance that an error in the cutting machine will result in one or more pieces not being correctly extracted from the material because of a faulty cut.

–

Reducing computational cost, by performing a previous study of accelerating the algorithm execution on multicore systems or even GPU.

–

A higher number of experiments will be performed so as to continue on checking the method robustness.

References

Freeman

Shapira

, Determining the minimum-area encasing rectangle for an arbitrary closed curve, Communications of the ACM18(7) (1975), 409–413.

Siasos

Vosniakos

G.C.

, Optimal directional nesting of planar profiles on fabric bands for composites manufacturing, CIRP Journal of Manufacturing Science and Technology7(3) (2014), 283–297.

Babu

A.R.

Babu

N.R.

, A generic approach for nesting of 2-D parts in 2-D sheets using genetic and heuristic algorithms, Computer-Aided Design33(12) (2001), 879–891.

Prasad

Y.K.D.V.

Somasundaram

Rao

K.P.

, A sliding algorithm for optimal nesting of arbitrarily shaped sheet metal blanks, The International Journal of Production Research33(6) (1995), 1505–1520.

Jakobs

, On genetic algorithms for the packing of polygons, European Journal of Operational Research88(1) (1996), 165–181.

Han

G.C.

S.J.

, Two-stage approach for nesting in two-dimensional cutting problems using neural network and simulated annealing, Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture210(6) (1996), 509–519.

Pinheiro

P.R.

Bonfim

A.J.

Saraiva

, A random-key genetic algorithm for solving the nesting problem, International Journal of Computer Integrated Manufacturing29(11) (2016), 1159–1165.

Elkeran

, A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering, European Journal of Operational Research231(3) (2013), 757–769.

Toledo

F.M.

Carravilla

M.A.

Ribeiro

Oliveira

J.F.

Gomes

A.M.

, The dotted-board model: A new MIP model for nesting irregular shapes, International Journal of Production Economics145(2) (2013), 478–487.

10.

Valvo

E.L.

, Meta-heuristic algorithms for nesting problem of rectangular pieces, , Procedia Engineering2 (2017), 291–296.

11.

Cherri

L.H.

Cherri

A.C.

Carravilla

M.A.

Oliveira

J.F.

Toledo

F.M.B.

Vianna

A.C.G.

, An innovative data structure to handle the geometry of nesting problems, International Journal of Production Research56(23) (2018), 7085–7102.

12.

Fang

Rao

Liu

Zhao

, Sequence transfer-based particle swarm optimization algorithm for irregular packing problems, , IEEE Access2 (2021), 131223–131235.

13.

Ranga

P.A.

Julia

A.B.

Antonio

, Jostle heuristics for the 2D-irregular shapes bin packing problems with free rotation, , Int J Prod Econ2 (2018), 12–26.

14.

Mundim

L.R.

Andretta

T.A.

, Queiroz, A biased random key genetic algorithm for open dimension nesting problems using no-fit raster, , Expert Syst Appl2 (2017), 358–371.

15.

Guo

Zhang

Peng

Zhang

, Two-dimensional irregular packing problems: A review, , Front Mech Eng2 (2022), 1–15.

16.

Liu

Cheng

Tian

Wang

Leng

Zhao

Zhang

Wei

, Algorithms for the variable-sized bin packing problem with time windows, , Comput Ind Eng2 (2021), 107175.

17.

Muhammed

Tansel

Ahmet

, Robust hyper-heuristic algorithms for the offline oriented/non-oriented 2D bin packing problems, , Appl Soft Comput2 (2015), 236–245.

18.

Rao

Wang

Luo

, Hybridizing Beam Search with Tabu Search for the Irregular Packing Problem, , Math Probl Eng2 (2021), 1–14.

19.

Queiroz

Andretta

, A branch-and-cut algorithm for the irregular strip packing problem with uncertain demands, , Int Trans Oper Res2 (2022), 3486–3513.

20.

Zhao

Rao

Fang

, A reinforcement learning algorithm for the 2D-rectangular strip packing problem, , J Phys Conf Ser2 (2022), 012002.

21.

Leao

A.A.

Toledo

F.M.

Oliveira

J.F.

Carravilla

M.A.

Alvarez-Valdés

, Irregular packing problems: A review of mathematical models, Eur J Oper Res 2020.

22.

Baldacci

Boschetti

M.A.

Ganovelli

Maniezzo

, Algorithms for nesting with defects, Discret Appl Math 2014.

23.

Guo

Fang

Wang

Rao

, A hybrid solving algorithm on two-dimensional irregular graphics nesting problem, , Forg Stamp Technol2 (2022), 39–45.

24.

Liu

, An optimization algorithm based on no-fit polygon method and hybrid heuristic strategy for irregular nesting problem, 2017 36th Chinese Control Conference (CCC) (2017), 2858–2863.

25.

Mundim

L.-R.

Andretta

Carravila

M.-A.

Oliveira

J.-F.

, A general heuristic for two-dimensional nesting problems with limited-size containers, International Journal of Production Research56(1-2) (2018), 709–732.

26.

Sato

A.-K.

Martins

T.-C.

Guerra

M.-S.

, Tsuzuki, Massive parallelization accelerated solution for the 2D irregular nesting problem, IFAC-PapersOnLine52(10) (2019), 119–124.

27.

Diyaley

Chakraborty

, Metaheuristics-based nesting of parts in sheet metal cutting operation, Operational Research in Engineering Sciences: Theory and Applications5(2) (2022), 1–16.

28.

CNC-APPS., Available online: https://cnc-apps.com/en/(accessed on 18 October 2021).