# Hybridizing Beam Search with Tabu Search for the Irregular Packing Problem

Authors: Yunqing Rao; Peng Wang; Qiang Luo
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

The irregular packing problem involves arranging all the irregular pieces on a plate with the objective of maximizing the use of material. In this article, the layout is formed by the ordered sequence of the irregular pieces which is obtained by a hybrid search algorithm and where the order is decoded by a proposed placement principle. First, a novel no-fit-polygon (NFP) generator is introduced. Then, a placement principle is presented with the new NFP generator. Finally, a search algorithm hybridized with beam search (BS) and tabu search (TS) is proposed to search over the sequence. The numerical experiments with many benchmark problems show that the hybrid algorithm is an applicative and effective approach for solving the irregular packing problem. The hybrid algorithm can produce competitive solutions in less time than many other typical algorithms.


---

## Body

## 1. Introduction

The irregular packing problem arises in many manufacturing industries, such as metal cutting, textile, leather, and so on, with different industries having different objectives and constraints. In this article, the irregular packing problem is categorized as a 2D irregular open dimension problem (2DIP) by the typology of Wäscher et al. [1]. The problem is concerned with finding a good arrangement of all pieces, which may be arbitrary shape, on a plate. Usually, the objective is to maximize the material utilization or minimize the length of a plate with a fixed width.The problem of finding an arrangement of pieces to cut from or pack inside larger objects is known as the cutting and packing problem, which is NP-hard by Garey and Johnson [2]. The Irregular Packing problem belongs to the more general class of combinatorial optimisation problems—the Cutting and Packing problems. The 2DIP problem is NP-complete, and as a result, the time consumption of the algorithm is very expensive when the scale of the problem is large. To obtain approximate solutions in a reasonable time, numerous methods for the irregular packing problem have been developed [3, 4].There are two key strategies summarized in the published literature for handling this problem. The first one, called the legal placement method, represents the problem as a sequence of pieces and applying a placement rule to construct the solution. The second one, named the relaxed placement method, considers the problem as building a layout on the plate and moves pieces within the layout.The legal placement method never allows the overlap to happen during the packing process. The two critical points of these methods are the placement sequence of pieces and the placement strategy. Art [5] implemented a placement strategy called BL (bottom-left) and using the multiple factors weighted to place the pieces. Dowsland and Dowsland [6] developed this strategy by permitting unpacked pieces to jump over the packed pieces to fill holes. Dowsland et al. [7] also proposed an algorithm where the edges of the plate width were alternated when searching for positions instead of packing pieces from the bottom to the top. Gomes and Oliveira [8] obtained the effective BL position by calculating intersections between the NFP of the already packed pieces and the next piece to be packed. Oliveira et al. [9] put forward a famous placement strategy in a sophisticated constructive heuristic called TOPOS. The solution is produced from a floating position, not the BL position. What’s more, both the next piece to be packed and its placement point are determined by three criteria: (a) minimum area of the rectangular enclosure; (b) minimum length of the rectangular enclosure; (c) maximum overlaps between the rectangular enclosures of the two pieces.The other critical point of the legal placement method is the sequence of pieces. Dowsland et al. [10] proposed an algorithm that adopts a fixed sequence to place pieces. The sequence can be generated in a random way or simply by sorting the pieces by the area or length. Babu and Babu [11] implemented a genetic algorithm to search over the sequence of pieces. Oliveira et al. [9] selected the next piece dynamically by their TOPOS algorithm. Gomes and Oliveira [8] introduced a 2-swap heuristic for handling the sequence of pieces. Burke et al. [12] combined their new BLF(bottom-left-fill) heuristic algorithm with both hill climbing and tabu search, where the sequence was searched by randomly selecting one operator from four operators (an insert move, a pairwise swap, a three-way swap, and an n-way swap). The beam search algorithm was presented by Bennell and Song [13]; computational results showed that some best results published in the literature could be improved by their beam search algorithm. Sato et al. [14] proposed simulated annealing that searched for feasible layouts to be packed in a container with fixed dimensions. Burke et al. [15] extended the orbital sliding method of calculating no-fit-polygons to enable it to handle arcs and used hill climbing and tabu local search algorithm to search the sequence. Leung et al. [16] presented an extended local search algorithm swapping two given polygons in one placement and placing one polygon into a new position and used the tabu search algorithm to avoid local minima. Pinheiro et al. [17] proposed a random-key genetic algorithm, which prescribed the integration of the aforementioned metaheuristic and well-known placement rules. Mundim et al. [18] derived new concepts as the no-fit raster, which could be used to check overlapping between any two-dimensional generic-shaped pieces, and used a biased random-key genetic algorithm to determine the sequence in which pieces were packed. Martinez-Sykora et al. [19] proposed a constructive approach allowing both free orientation for the pieces, as in the case of the ceramic industry, or a finite set of orientations as in the case of the garment industry.The legal placement methods have the advantage of generating feasible solutions and reducing an infinite solution space to a discrete set of solutions. However, reducing the number of solutions may generate the possibility of omitting the global optimum at the same time.The obvious characteristic of the relaxed placement method is to allow overlaps during the packing process. It is very easy to construct an initial layout. The layout can be built randomly, and better results might be obtained by applying a good placement strategy. To minimize the amount of overlap, the way of imposing penalties in objective functions was used widely.Oliveira and Ferreira [20] applied a polygon-based representation where identifying and resolving overlap was handled by using D-functions. Jakobs [21] used minimum rectangular enclosures to represent the irregular pieces and then placed the pieces by the orthogonal method. Besides, the compaction algorithm was applied to move the piece towards the BL position in the orthogonal method, later, hybridizing linear programming compaction with a search algorithm to handle the process of moving pieces within the layout in Bennell and Dowsland [22]. Gomes and Oliveira [23] improved this approach by using a Simulated Annealing (SA) algorithm to search the solution space, where linear programming compaction was used to build the neighborhood structure. To avoid local optimum, meta-heuristics for resolving overlap have become quite popular in the relaxed placement methods [24–26].The difference between the relaxed placement method and the legal placement method is that the former usually build the layout in a continuous region. This means that solution space can be infinite. The relaxed placement method has the advantage that no solutions are lost in the unchanged solution space. However, the time consumption of these methods may be unreasonable. In addition, such approaches even do not guarantee to produce a feasible solution. By contrast, the legal placement method produces a limited number of solutions, but the solution is effective and the run time of the algorithm is acceptable.These approaches mentioned above can effectively solve the irregular packing problem, but the time consumption of the algorithm still can be reduced. More specifically, under the orbiting method of NFP, creating potential translation vectors and finding a feasible translation vector can be faster, and this accounts for a large portion of time consumption. Besides, the local evaluation of the placement position is extensively used, which may lead to the local optimal solution to some degree. Also, the search algorithms in the former literature have a random character. The algorithm needs to be run several times to obtain a better solution, even though it cannot always obtain a feasible solution. In this article, a hybrid search algorithm is proposed to search the sequence of pieces to be packed, which combines the local evaluation and global evaluation, and, an improved orbiting method of NFP, which reduces the steps of creating NFP in Burke et al. [27]. The proposed hybrid algorithm BSTS is somehow deterministic and can produce some good results with less time-consuming.The rest of the article is as follows: Section2 describes using the no-fit-polygon and the novel placement principle to construct the solution under the situation of representing the problem as a sequence of pieces. Section 3 depicts the hybrid search algorithm used to search over the sequence of pieces. When a new sequence is produced by the hybrid search algorithm, the algorithm described in Section 2 will be called to construct the layout. The computational results on many benchmark problems and conclusions are, respectively, presented in Sections 4 and 5.


## 2. Novel Placement Principle Based on Improved NFP

The main contribution of this article is to find out an applicative and effective algorithm for the irregular shape packing problem. The problem is presented as a sequence of pieces that be packed with a novel placement principle. To describe the hybrid algorithm clearly, some related concepts are defined and explained first. The NFP can efficiently avoid overlaps during the packing process. The placement principle is applied to rapidly find the placement positions on NFPs and place the pieces. It is also necessary to imply a search algorithm to search over the sequence of pieces.


### 2.1. The Improved NFP

The no-fit-polygon concept was first introduced by Art [5] and used to avoid overlaps when placing the pieces on the plate. Later it was developed and improved by several researchers. Although different approaches were proposed to generate NFP, they could be categorized into three general methods: (a) the orbiting algorithm [27, 28]; (b) Minkowski sums [29, 30]; (c) decomposition algorithm [31–33].When polygon B slides around the external edge of polygon A (fixed), the locus of the reference point (on polygon B) form the NFPAB. During the orbital process, the relative orientations of the two polygons remained unchanged (see Figure 1). There are three conditions about the position of the reference point.Figure 1
The no-fit-polygon of two polygons A and B.If the reference point of B is positioned inside NFPAB, A and B will overlap; if the reference point of B is positioned on the boundary of NFPAB, B will touch A; if the reference point of B is positioned outside NFPAB, A and B will neither overlap nor touch.Hence, the problem of relative positions of two polygons can be simplified as finding the relative positions between one point and one polygon (see Figure2).Figure 2
Three relative positions of the reference point and NFPAB: (a) overlapping, (b) touching, and (c) neither overlapping nor touching.
(a)(b)(c)In this article, the calculation of NFP is handled by the orbital algorithm. The improved approach is logically similar to the algorithm of Burke et al. [27], while a modified implementation is proposed.In this section, the forming process of NFP is described. When polygon B slides around A, each step creates an edge of the NFP. Unlike the algorithm of Burke, the process of producing NFP is broken down into the following three subparts: finding potential vectors, eliminating infeasible vectors, and calculating minimum distance. This method can reduce the time of creating potential translation vectors and finding a feasible translation vector.


#### 2.1.1. Subheadings Finding Potential Vectors

As previously described, the NFP is a polygon with each edge either derived from an edge of A or B, depending on the situation (see Figure3).Figure 3
Translation vector: (a) derived from edge a3 and (b) derived from edge b1.
(a)(b)The set of potential translation vectors is obtained by the touching edge pairs. There are three possible relative positions of two oriented edges (see Figure4):(1)
A vertex of the orbiting edge b touches the middle of the fixed edge a; the potential vector isPtPe⟶.(2)
A vertex of the fixed edge a touches the middle of the orbiting edge b; the potential vector isPePt⟶.(3)
Both edges touch at a vertex. In this case, the potential vector can be detected by the following rules: if the angle from vectorBjBj+1⟶ to AjAj+1⟶is less than 180°, the translation vector is AjAj+1⟶; otherwise, it is Bj+1Bj⟶ (see Figure 5).Figure 4
Three touching edge-pair types.Figure 5
Both edges touch at a vertex.


#### 2.1.2. Eliminating Infeasible Vectors

The potential translation vector produced by the method mentioned above might be infeasible. This section is to eliminate those potential vectors which result in immediate intersections. For example, in Figure6(a), two potential translation vectors, a4 and −b1, can be created according to the rules mentioned in case 3. Figure 6 demonstrates how to identify an infeasible translation vector (a4). The edge-pairs involving edge a4 have been omitted for brevity. Only the edge pairs of the other touch point need to be tested. If translating polygon B along vector a4, this would result in an immediate intersection between edges a1 and b1 (and also a2 and b1). Once one translation is infeasible, the vector should be eliminated, so a4 is not a feasible translation vector.Figure 6
(a) Two vertex-vertex touch cases, (b) feasible edge translations of a4, and (c) infeasible edge translations of a4.
(a)(b)(c)


#### 2.1.3. Calculating Minimum Distance

Before polygon B translates along the translation vector, the feasible translation vector must be trimmed, which means calculating the minimum distance of the vector. This is necessary because other edges may intersect during the translation of polygon B. For example, in Figure7(a), polygon A and polygon B intersect because of applying the entire vector without trimming. In this case, the minimum distance from the original point to the intersection point defines the final feasible vector (see Figure 7(b)).Figure 7
The final feasible translation vector: (a) untrimmed and (b) trimmed.
(a)(b)


### 2.2. The Novel Placement Principle

The solution space of the irregular packing problem is infinite without limiting the placement positions and rotations. To reduce the solution space, some placement principles have been presented, such as BL and TOPOS. BL principle, in which a piece is placed to the bottom-left position, usually works for the orthogonal packing problem, not for the irregular packing problem. TOPOS algorithm is to place the piece by evaluating the placement positions with the evaluation criteria.In this section, to determine placement position and rotation angle for each piece, a new placement principle based on BL principle and lowest-gravity-center principle [34] is applied. The modified and concise criteria are proposed to evaluate the best placement position. Two attributes (length L and area A of the rectangle enclosure) are selected to create the criteria Z as follows (equations (1)–(3)). Figure 8 displays the meaning of the symbol in equations.(1)length:L=Lnewxnew,(2)area:A=Lnew×Wnewxnew×ynew,(3)CostFuctioncriteria:Z=minL+A.Figure 8
Illustration of the criteria for the new piece.Now, given a piece, its gravity center is first calculated and then can generate two NFPs (gravity-center NFP and bottom-left NFP) by viewing the gravity center and the bottom-left vertex as the reference point, respectively. Note that both gravity-center NFP and bottom-left NFP will be different when different rotations of the piece are performed. The lowest gravity center and bottommost-leftmost vertex are chosen to be evaluated by the criteria presented above. The position with the best evaluation is determined to be the placement position. Figure9 shows an example of the presented placement principle. The two solid polygons (noted 1, 2) are the gravity-center NFPs with two different rotations. Meanwhile, the dotted polygons, noted 1 and 2 (some dotted edges coincide with the edges of the container) are the bottom-left NFPs correspondingly.Figure 9
Finding the bottommost-leftmost vertex and lowest gravity center.


## 2.1. The Improved NFP

The no-fit-polygon concept was first introduced by Art [5] and used to avoid overlaps when placing the pieces on the plate. Later it was developed and improved by several researchers. Although different approaches were proposed to generate NFP, they could be categorized into three general methods: (a) the orbiting algorithm [27, 28]; (b) Minkowski sums [29, 30]; (c) decomposition algorithm [31–33].When polygon B slides around the external edge of polygon A (fixed), the locus of the reference point (on polygon B) form the NFPAB. During the orbital process, the relative orientations of the two polygons remained unchanged (see Figure 1). There are three conditions about the position of the reference point.Figure 1
The no-fit-polygon of two polygons A and B.If the reference point of B is positioned inside NFPAB, A and B will overlap; if the reference point of B is positioned on the boundary of NFPAB, B will touch A; if the reference point of B is positioned outside NFPAB, A and B will neither overlap nor touch.Hence, the problem of relative positions of two polygons can be simplified as finding the relative positions between one point and one polygon (see Figure2).Figure 2
Three relative positions of the reference point and NFPAB: (a) overlapping, (b) touching, and (c) neither overlapping nor touching.
(a)(b)(c)In this article, the calculation of NFP is handled by the orbital algorithm. The improved approach is logically similar to the algorithm of Burke et al. [27], while a modified implementation is proposed.In this section, the forming process of NFP is described. When polygon B slides around A, each step creates an edge of the NFP. Unlike the algorithm of Burke, the process of producing NFP is broken down into the following three subparts: finding potential vectors, eliminating infeasible vectors, and calculating minimum distance. This method can reduce the time of creating potential translation vectors and finding a feasible translation vector.


### 2.1.1. Subheadings Finding Potential Vectors

As previously described, the NFP is a polygon with each edge either derived from an edge of A or B, depending on the situation (see Figure3).Figure 3
Translation vector: (a) derived from edge a3 and (b) derived from edge b1.
(a)(b)The set of potential translation vectors is obtained by the touching edge pairs. There are three possible relative positions of two oriented edges (see Figure4):(1)
A vertex of the orbiting edge b touches the middle of the fixed edge a; the potential vector isPtPe⟶.(2)
A vertex of the fixed edge a touches the middle of the orbiting edge b; the potential vector isPePt⟶.(3)
Both edges touch at a vertex. In this case, the potential vector can be detected by the following rules: if the angle from vectorBjBj+1⟶ to AjAj+1⟶is less than 180°, the translation vector is AjAj+1⟶; otherwise, it is Bj+1Bj⟶ (see Figure 5).Figure 4
Three touching edge-pair types.Figure 5
Both edges touch at a vertex.


### 2.1.2. Eliminating Infeasible Vectors

The potential translation vector produced by the method mentioned above might be infeasible. This section is to eliminate those potential vectors which result in immediate intersections. For example, in Figure6(a), two potential translation vectors, a4 and −b1, can be created according to the rules mentioned in case 3. Figure 6 demonstrates how to identify an infeasible translation vector (a4). The edge-pairs involving edge a4 have been omitted for brevity. Only the edge pairs of the other touch point need to be tested. If translating polygon B along vector a4, this would result in an immediate intersection between edges a1 and b1 (and also a2 and b1). Once one translation is infeasible, the vector should be eliminated, so a4 is not a feasible translation vector.Figure 6
(a) Two vertex-vertex touch cases, (b) feasible edge translations of a4, and (c) infeasible edge translations of a4.
(a)(b)(c)


### 2.1.3. Calculating Minimum Distance

Before polygon B translates along the translation vector, the feasible translation vector must be trimmed, which means calculating the minimum distance of the vector. This is necessary because other edges may intersect during the translation of polygon B. For example, in Figure7(a), polygon A and polygon B intersect because of applying the entire vector without trimming. In this case, the minimum distance from the original point to the intersection point defines the final feasible vector (see Figure 7(b)).Figure 7
The final feasible translation vector: (a) untrimmed and (b) trimmed.
(a)(b)


## 2.1.1. Subheadings Finding Potential Vectors

As previously described, the NFP is a polygon with each edge either derived from an edge of A or B, depending on the situation (see Figure3).Figure 3
Translation vector: (a) derived from edge a3 and (b) derived from edge b1.
(a)(b)The set of potential translation vectors is obtained by the touching edge pairs. There are three possible relative positions of two oriented edges (see Figure4):(1)
A vertex of the orbiting edge b touches the middle of the fixed edge a; the potential vector isPtPe⟶.(2)
A vertex of the fixed edge a touches the middle of the orbiting edge b; the potential vector isPePt⟶.(3)
Both edges touch at a vertex. In this case, the potential vector can be detected by the following rules: if the angle from vectorBjBj+1⟶ to AjAj+1⟶is less than 180°, the translation vector is AjAj+1⟶; otherwise, it is Bj+1Bj⟶ (see Figure 5).Figure 4
Three touching edge-pair types.Figure 5
Both edges touch at a vertex.


## 2.1.2. Eliminating Infeasible Vectors

The potential translation vector produced by the method mentioned above might be infeasible. This section is to eliminate those potential vectors which result in immediate intersections. For example, in Figure6(a), two potential translation vectors, a4 and −b1, can be created according to the rules mentioned in case 3. Figure 6 demonstrates how to identify an infeasible translation vector (a4). The edge-pairs involving edge a4 have been omitted for brevity. Only the edge pairs of the other touch point need to be tested. If translating polygon B along vector a4, this would result in an immediate intersection between edges a1 and b1 (and also a2 and b1). Once one translation is infeasible, the vector should be eliminated, so a4 is not a feasible translation vector.Figure 6
(a) Two vertex-vertex touch cases, (b) feasible edge translations of a4, and (c) infeasible edge translations of a4.
(a)(b)(c)


## 2.1.3. Calculating Minimum Distance

Before polygon B translates along the translation vector, the feasible translation vector must be trimmed, which means calculating the minimum distance of the vector. This is necessary because other edges may intersect during the translation of polygon B. For example, in Figure7(a), polygon A and polygon B intersect because of applying the entire vector without trimming. In this case, the minimum distance from the original point to the intersection point defines the final feasible vector (see Figure 7(b)).Figure 7
The final feasible translation vector: (a) untrimmed and (b) trimmed.
(a)(b)


## 2.2. The Novel Placement Principle

The solution space of the irregular packing problem is infinite without limiting the placement positions and rotations. To reduce the solution space, some placement principles have been presented, such as BL and TOPOS. BL principle, in which a piece is placed to the bottom-left position, usually works for the orthogonal packing problem, not for the irregular packing problem. TOPOS algorithm is to place the piece by evaluating the placement positions with the evaluation criteria.In this section, to determine placement position and rotation angle for each piece, a new placement principle based on BL principle and lowest-gravity-center principle [34] is applied. The modified and concise criteria are proposed to evaluate the best placement position. Two attributes (length L and area A of the rectangle enclosure) are selected to create the criteria Z as follows (equations (1)–(3)). Figure 8 displays the meaning of the symbol in equations.(1)length:L=Lnewxnew,(2)area:A=Lnew×Wnewxnew×ynew,(3)CostFuctioncriteria:Z=minL+A.Figure 8
Illustration of the criteria for the new piece.Now, given a piece, its gravity center is first calculated and then can generate two NFPs (gravity-center NFP and bottom-left NFP) by viewing the gravity center and the bottom-left vertex as the reference point, respectively. Note that both gravity-center NFP and bottom-left NFP will be different when different rotations of the piece are performed. The lowest gravity center and bottommost-leftmost vertex are chosen to be evaluated by the criteria presented above. The position with the best evaluation is determined to be the placement position. Figure9 shows an example of the presented placement principle. The two solid polygons (noted 1, 2) are the gravity-center NFPs with two different rotations. Meanwhile, the dotted polygons, noted 1 and 2 (some dotted edges coincide with the edges of the container) are the bottom-left NFPs correspondingly.Figure 9
Finding the bottommost-leftmost vertex and lowest gravity center.


## 3. The Hybrid Algorithm for Searching Sequence

Usually, some sorting criteria, such as the area or the length, are applied to determine the packing sequence of pieces. Better solutions can be produced if a search algorithm is applied to searching over the sequence. BS and TS algorithms can successfully solve the 2DIP problem, but there are still some imperfections. The beam search is a heuristic with a strong global search and deterministic. However, this may also generate the possibility of removing other good solutions. To deal with the problem, tabu search is hybridized with a strong local search with beam search to implement an applicative and effective hybrid search algorithm BSTS. The focus of this section is on the hybridization of tabu search with beam search in the resolution of the packing sequence.


### 3.1. Tabu Search

Different from some greedy algorithms, tabu search is a search algorithm with a neighborhood set that accept worse solutions, not always better solutions. The advantage of this characteristic is that the tabu search can escape from local minima. Tabu list is a dynamic and flexible memory structure that prevents the algorithm from performing the recently executed moves in the next few iterations.The tabu search mechanism in this article is similar to the algorithm of Glover and Taillard [35]. The neighborhood size in the tabu search is set to 5 and the tabu list is 100, which contains the recently searched solutions, not the moves. In this article, to extensively search over the packing sequence, tabu search is applied to hybridize with beam search. The focus of the tabu search is on escaping from local minima. So the neighbour structure is defined as a 4-way swap where four randomly selected pieces are swapped. The process can be represented in the following way (see Figure 10).Figure 10
The algorithm of tabu search.


### 3.2. Beam Search

Beam search is an established heuristic derivative branch-and-bound. A common application is the algorithm that uses a tree search mechanism in which only the most promising nodes are performed to branch at each level according to the evaluations. Usually, a two-stage beam search is applied with two evaluations: local evaluation and global evaluation. A local evaluation (also called rough evaluation) can be faster but may result in discarding some good solutions, whereas a global evaluation (also called accurate evaluation) usually may be more time-consuming. So, the combination of the two evaluations is significant in most beam search algorithms.First, a local evaluation is applied to evaluate all child nodes (branching from each beam node) and select the bestγ nodes (filter width) at each level. Then, the global evaluation is used to accurately evaluate the γ nodes and retain the best w nodes (beam width) to branch (see Figure 11).Figure 11
Illustration of a beam search.In this article, the search tree, from the root to the last level, represents the packing sequence of all pieces. At each level, each node with its parent nodes in the upper levels represents a partial solution. Each branch from each beam node means adding an unpacked piece to the partial solution until the lowest level, which means the complete solution. Obviously, from the root to the lowest level, the number of levels is the number of all pieces. And at each level, the number of nodes branching from its parent node is the number of the remaining piece types. Figure12 shows how beam search works for the problem.Figure 12
The algorithm of beam search.


### 3.3. Hybrid Algorithm

As mentioned above, the beam search is a heuristic with a strong global search and deterministic. However, this may also generate the possibility of removing other good solutions. To deal with the problem, hybridize tabu search with a strong local search with beam search to implement an applicative and effective hybrid search algorithm BSTS.The hybrid search algorithm uses the same process of the beam search except that using global evaluation to evaluate the complete solution. In the hybrid search algorithm, the sequence of the already packed pieces has been determined by the BS mechanism and only the unpacked pieces need to be searched by tabu search, not simply ordered randomly or by decreasing area. The hybrid search algorithm is a two-stage strategy, where the local evaluation is the same criteria was presented in the placement principle, but the global evaluation is the length of the complete solution. The process of the algorithm can be represented as in Figure13.Figure 13
The hybrid search algorithm.


## 3.1. Tabu Search

Different from some greedy algorithms, tabu search is a search algorithm with a neighborhood set that accept worse solutions, not always better solutions. The advantage of this characteristic is that the tabu search can escape from local minima. Tabu list is a dynamic and flexible memory structure that prevents the algorithm from performing the recently executed moves in the next few iterations.The tabu search mechanism in this article is similar to the algorithm of Glover and Taillard [35]. The neighborhood size in the tabu search is set to 5 and the tabu list is 100, which contains the recently searched solutions, not the moves. In this article, to extensively search over the packing sequence, tabu search is applied to hybridize with beam search. The focus of the tabu search is on escaping from local minima. So the neighbour structure is defined as a 4-way swap where four randomly selected pieces are swapped. The process can be represented in the following way (see Figure 10).Figure 10
The algorithm of tabu search.


## 3.2. Beam Search

Beam search is an established heuristic derivative branch-and-bound. A common application is the algorithm that uses a tree search mechanism in which only the most promising nodes are performed to branch at each level according to the evaluations. Usually, a two-stage beam search is applied with two evaluations: local evaluation and global evaluation. A local evaluation (also called rough evaluation) can be faster but may result in discarding some good solutions, whereas a global evaluation (also called accurate evaluation) usually may be more time-consuming. So, the combination of the two evaluations is significant in most beam search algorithms.First, a local evaluation is applied to evaluate all child nodes (branching from each beam node) and select the bestγ nodes (filter width) at each level. Then, the global evaluation is used to accurately evaluate the γ nodes and retain the best w nodes (beam width) to branch (see Figure 11).Figure 11
Illustration of a beam search.In this article, the search tree, from the root to the last level, represents the packing sequence of all pieces. At each level, each node with its parent nodes in the upper levels represents a partial solution. Each branch from each beam node means adding an unpacked piece to the partial solution until the lowest level, which means the complete solution. Obviously, from the root to the lowest level, the number of levels is the number of all pieces. And at each level, the number of nodes branching from its parent node is the number of the remaining piece types. Figure12 shows how beam search works for the problem.Figure 12
The algorithm of beam search.


## 3.3. Hybrid Algorithm

As mentioned above, the beam search is a heuristic with a strong global search and deterministic. However, this may also generate the possibility of removing other good solutions. To deal with the problem, hybridize tabu search with a strong local search with beam search to implement an applicative and effective hybrid search algorithm BSTS.The hybrid search algorithm uses the same process of the beam search except that using global evaluation to evaluate the complete solution. In the hybrid search algorithm, the sequence of the already packed pieces has been determined by the BS mechanism and only the unpacked pieces need to be searched by tabu search, not simply ordered randomly or by decreasing area. The hybrid search algorithm is a two-stage strategy, where the local evaluation is the same criteria was presented in the placement principle, but the global evaluation is the length of the complete solution. The process of the algorithm can be represented as in Figure13.Figure 13
The hybrid search algorithm.


## 4. Results

In this section, the hybrid algorithm is tested by the benchmark problems previously published in the literature. To provide good solutions, NFP and the novel placement principle are discussed in Section3 to place each piece by the sequence, which is given by the BSTS. Implementation and parameters are set by preliminary computational experiments, which are not discussed in this article.


### 4.1. Problem Instances

Hybrid algorithm (BSTS) is tested by the packing problem instances, also used as benchmark problems in other literature. The data files can be downloaded from the ESICUP website (http://www.fe.up.pt/esicup). The details can be summarized in Table 1.Table 1
Details of the benchmark problems.
Problem instanceNumber of piece typesTotal number of piecesRotational constraintsSheet widthFu121290 incremental38Jakobs1252590 incremental40Jakobs2252590 incremental70Shapes04430 absolute40Shapes14430, 180 absolute40Shapes27280, 180 absolute15Dighe116160 absolute100Dighe210100 absolute100Albano8240, 180 absolute4900Dagli10300, 180 absolute60Mao92090 incremental2550Marques82490 incremental104Swim10480, 180 absolute5752Trousers17640, 180 absolute79


### 4.2. Results

The computational tests were conducted on a Core 2 D 2.0 GHz processor with 1024 Mb of RAM. The program was coded in Visual Studio C++.As presented above, the times of applying global evaluation are rising with the increase of the filter widthγ of the hybrid algorithm, which means more time-consuming. Furthermore, if the tabu search used to determine the sequence of the unpacked pieces is complicated, the hybrid algorithm may not be acceptable. According to the preliminary computational experiments, the parameters were set by the following rules: filter width = min {M, O ∗ 5}, Beam widths = {10, 100} with tabu iterations = (N − n − 1) ∗ 5, where N was the total number of all pieces, n was the number of packed pieces, M was the total number of the piece types, and O was the number of the allowed orientations. The neighborhood size in the tabu search is set to 5 and the tabu list is 100.The computational tests consisted of 20 runs for each instance, both for the simulated annealing hybrid algorithm (SAHA) and the Random-Key Genetic Algorithm (μ-BRKGA). The SAHA and μ-BRKGA algorithms can obtain a good solution to the problem. There are some differences between these algorithms in the computational environment. The details about the hardware environment are shown in Table 2. The detailed parameters of the algorithms are represented in their published literature. Thus results are compared with the results of SAHA [23] in Table 3, and compared with the results of μ-BRKGA [36] in Table 4. The results of these algorithms are taken from their original articles.Table 2
Computational environments.
Algorithm#lanCPURAM (G)TimesBSTSVS C++Core 2 D CPU at 2.0 GHz120SAHAC++Pentium IV CPU at 2.13 GHz0.520μ-BRKGAJavaIntel i7- 960 CPU at 3.2 GHz820Table 3
BSTS algorithm results compared with the average results of SAHA.
ProblemAverage results of SAHAAverage results of BSTSLengthAvg. (%)Time (s)BW/FWLengthAvg. (%)Time (s)Fu32.7087.15296100/1232.9986.38282Jakobs112.9375.80332100/2011.9881.87639Jakobs225.8674.62454100/2025.8474.66777Shapes063.1563.18391410/466.1160.38363Shapes158.1768.591031410/460.1465.26557Shapes226.5381.412257100/728.4875.82401Dighe112281.978310/5125.6679.48185Dighe2119.5383.662210/5121.1282.5692Albano10280.184.682257100/810443.183.37926Dagli59.4185.365110100/1062.3780.93413Mao1842.7079.998245100/91839.480.12759Marques79.6386.877507100/879.9486.40591Swim6121.3972.276937100/106369.169.46855Trousers244.6889.018588100/10252.0786.41641Compared with the average results of SAHA, the better results obtained by the hybrid algorithm BSTS are highlighted by bold. Less than 1% worse results are italicized, and this also shows that the BSTS algorithm can produce some comparable results. The bold and italicized values can display the advantage of the BSTS algorithm more clearly.Table 4
BSTS algorithm results compared with the results ofμ-BRKGA.
ProblemThe results ofμ-BRKGAThe results of BSTSBest (%)Avg. (%)Time (s)BW/FWBest (%)Avg. (%)Time (s)Fu91.9688.341815100/1288.7986.38282Jakobs189.0978.796300100/2083.5581.87639Jakobs279.7577.907150100/2075.7274.66777Shapes066.5063.50120010/462.1960.38363Shapes172.5565.89186010/467.5565.26557Dighe1100.00100.00192010/582.2179.48185Dighe2100.00100.00205010/585.1282.5692Albano89.1184.694200100/884.4683.37926Marques89.1484.313240100/887.3186.40591Swim73.5970.787400100/1071.7469.46855Trousers90.5288.677250100/1088.8486.41641The better results obtained by the hybrid algorithm BSTS have been highlighted. Less than 1% worse results are underlined. In comparison to the average results obtained by SAHA, the proposed BSTS algorithm produces three better results (Jakobs1, Jakobs2, Mao) and four comparable results (Dighe2, Fu, Albano, Marques) which are within 1% of the average results. In comparison to the average results obtained byμ-BRKGA, the proposed BSTS algorithm produces two better average results (highlighted in Table 4). Although the best results of μ-BRKGA surpass the BSTS, the time of μ-BRKGA much overtakes the BSTS. In ten benchmark problems, there are all solutions (highlighted in Table 4) to be produced much faster than μ-BRKGA. The layouts for the best results of the seven cases can be found in Figure 14 in Appendix. The details of 20 runs for the 14 benchmark problems are also shown in Table 5 in Appendix.Figure 14
(a) Fu: 88.36% (282 s), (b) Jacobs1: 83.55% (639 s), (c) Marques: 86.40% (591 s), (d) Swim: 71.74% (855 s), (e) Mao: 81% (759 s), (f) Albano: 84.46% (926 s), and (g) Trousers: 88.84% (641 s).
(a)(b)(c)(d)(e)(f)(g)Table 5
The detailed results of 20 runs for 14 instances.
FuJakobs1Jakobs2Shapes0Shapes1Shapes2Dighe1Dighe2AlbanoDagliMaoMarquesSwimTrousers86.3679.6774.2361.0167.3175.2678.585.1284.4680.378186.7668.8386.7788.7980.9973.6760.8267.5580.2377.281.6784.4683.0178.2486.469.5888.8485.8481.6774.5960.9264.0473.7276.6283.3782.7479.3779.1585.9369.5186.686.181.6775.5462.1966.1776.0680.1480.1584.0680.580.1186.7669.3886.686.3681.6774.5959.556676.0680.8482.1283.483.0179.8985.9369.1185.5586.3683.5574.2360.3663.4375.2680.2680.6483.481.2780.8787.3168.4785.9286.3681.6774.2360.3664.3576.0678.1882.7584.2779.4979.386.7668.7486.6486.3683.5574.6661.2966.1776.3380.3582.2584.0680.3779.3885.468.2286.0987.6681.6774.2359.5563.4576.0678.3984.8582.780.8980.0186.6869.8286.485.8681.6775.7260.3665.279.3382.2181.0383.0582.0680.6687.3168.7186.8886.183.3374.2360.7265.4176.0680.3281.8982.6180.7680.8785.9369.9286.0585.8482.2874.2360.2763.3376.3378.6181.7682.5480.7679.3886.2570.4186.486.3680.3374.2359.9164.0476.3378.6783.3183.0580.1280.1186.2568.9286.3686.3681.6775.5459.5563.7475.2679.6882.5683.8181.5479.9784.9870.687.2685.8481.6775.0959.5563.8475.5279.4182.7583.0581.548186.2571.7485.7586.3681.6774.3460.4566.1776.8780.3884.4682.6179.7480.6886.7669.0886.1285.8482.4974.2359.5563.9475.2678.3981.8283.2781.6780.8785.468.8985.4586.182.8674.5959.8267.5573.9778.4584.4683.0580.3779.8986.6869.3386.1986.3681.6775.7261.266.177581.3182.1883.3679.6280.8786.7670.4186.3686.3681.6775.3960.1867.3174.4881.738283.3682.0680.1187.3169.0486.05


## 4.1. Problem Instances

Hybrid algorithm (BSTS) is tested by the packing problem instances, also used as benchmark problems in other literature. The data files can be downloaded from the ESICUP website (http://www.fe.up.pt/esicup). The details can be summarized in Table 1.Table 1
Details of the benchmark problems.
Problem instanceNumber of piece typesTotal number of piecesRotational constraintsSheet widthFu121290 incremental38Jakobs1252590 incremental40Jakobs2252590 incremental70Shapes04430 absolute40Shapes14430, 180 absolute40Shapes27280, 180 absolute15Dighe116160 absolute100Dighe210100 absolute100Albano8240, 180 absolute4900Dagli10300, 180 absolute60Mao92090 incremental2550Marques82490 incremental104Swim10480, 180 absolute5752Trousers17640, 180 absolute79


## 4.2. Results

The computational tests were conducted on a Core 2 D 2.0 GHz processor with 1024 Mb of RAM. The program was coded in Visual Studio C++.As presented above, the times of applying global evaluation are rising with the increase of the filter widthγ of the hybrid algorithm, which means more time-consuming. Furthermore, if the tabu search used to determine the sequence of the unpacked pieces is complicated, the hybrid algorithm may not be acceptable. According to the preliminary computational experiments, the parameters were set by the following rules: filter width = min {M, O ∗ 5}, Beam widths = {10, 100} with tabu iterations = (N − n − 1) ∗ 5, where N was the total number of all pieces, n was the number of packed pieces, M was the total number of the piece types, and O was the number of the allowed orientations. The neighborhood size in the tabu search is set to 5 and the tabu list is 100.The computational tests consisted of 20 runs for each instance, both for the simulated annealing hybrid algorithm (SAHA) and the Random-Key Genetic Algorithm (μ-BRKGA). The SAHA and μ-BRKGA algorithms can obtain a good solution to the problem. There are some differences between these algorithms in the computational environment. The details about the hardware environment are shown in Table 2. The detailed parameters of the algorithms are represented in their published literature. Thus results are compared with the results of SAHA [23] in Table 3, and compared with the results of μ-BRKGA [36] in Table 4. The results of these algorithms are taken from their original articles.Table 2
Computational environments.
Algorithm#lanCPURAM (G)TimesBSTSVS C++Core 2 D CPU at 2.0 GHz120SAHAC++Pentium IV CPU at 2.13 GHz0.520μ-BRKGAJavaIntel i7- 960 CPU at 3.2 GHz820Table 3
BSTS algorithm results compared with the average results of SAHA.
ProblemAverage results of SAHAAverage results of BSTSLengthAvg. (%)Time (s)BW/FWLengthAvg. (%)Time (s)Fu32.7087.15296100/1232.9986.38282Jakobs112.9375.80332100/2011.9881.87639Jakobs225.8674.62454100/2025.8474.66777Shapes063.1563.18391410/466.1160.38363Shapes158.1768.591031410/460.1465.26557Shapes226.5381.412257100/728.4875.82401Dighe112281.978310/5125.6679.48185Dighe2119.5383.662210/5121.1282.5692Albano10280.184.682257100/810443.183.37926Dagli59.4185.365110100/1062.3780.93413Mao1842.7079.998245100/91839.480.12759Marques79.6386.877507100/879.9486.40591Swim6121.3972.276937100/106369.169.46855Trousers244.6889.018588100/10252.0786.41641Compared with the average results of SAHA, the better results obtained by the hybrid algorithm BSTS are highlighted by bold. Less than 1% worse results are italicized, and this also shows that the BSTS algorithm can produce some comparable results. The bold and italicized values can display the advantage of the BSTS algorithm more clearly.Table 4
BSTS algorithm results compared with the results ofμ-BRKGA.
ProblemThe results ofμ-BRKGAThe results of BSTSBest (%)Avg. (%)Time (s)BW/FWBest (%)Avg. (%)Time (s)Fu91.9688.341815100/1288.7986.38282Jakobs189.0978.796300100/2083.5581.87639Jakobs279.7577.907150100/2075.7274.66777Shapes066.5063.50120010/462.1960.38363Shapes172.5565.89186010/467.5565.26557Dighe1100.00100.00192010/582.2179.48185Dighe2100.00100.00205010/585.1282.5692Albano89.1184.694200100/884.4683.37926Marques89.1484.313240100/887.3186.40591Swim73.5970.787400100/1071.7469.46855Trousers90.5288.677250100/1088.8486.41641The better results obtained by the hybrid algorithm BSTS have been highlighted. Less than 1% worse results are underlined. In comparison to the average results obtained by SAHA, the proposed BSTS algorithm produces three better results (Jakobs1, Jakobs2, Mao) and four comparable results (Dighe2, Fu, Albano, Marques) which are within 1% of the average results. In comparison to the average results obtained byμ-BRKGA, the proposed BSTS algorithm produces two better average results (highlighted in Table 4). Although the best results of μ-BRKGA surpass the BSTS, the time of μ-BRKGA much overtakes the BSTS. In ten benchmark problems, there are all solutions (highlighted in Table 4) to be produced much faster than μ-BRKGA. The layouts for the best results of the seven cases can be found in Figure 14 in Appendix. The details of 20 runs for the 14 benchmark problems are also shown in Table 5 in Appendix.Figure 14
(a) Fu: 88.36% (282 s), (b) Jacobs1: 83.55% (639 s), (c) Marques: 86.40% (591 s), (d) Swim: 71.74% (855 s), (e) Mao: 81% (759 s), (f) Albano: 84.46% (926 s), and (g) Trousers: 88.84% (641 s).
(a)(b)(c)(d)(e)(f)(g)Table 5
The detailed results of 20 runs for 14 instances.
FuJakobs1Jakobs2Shapes0Shapes1Shapes2Dighe1Dighe2AlbanoDagliMaoMarquesSwimTrousers86.3679.6774.2361.0167.3175.2678.585.1284.4680.378186.7668.8386.7788.7980.9973.6760.8267.5580.2377.281.6784.4683.0178.2486.469.5888.8485.8481.6774.5960.9264.0473.7276.6283.3782.7479.3779.1585.9369.5186.686.181.6775.5462.1966.1776.0680.1480.1584.0680.580.1186.7669.3886.686.3681.6774.5959.556676.0680.8482.1283.483.0179.8985.9369.1185.5586.3683.5574.2360.3663.4375.2680.2680.6483.481.2780.8787.3168.4785.9286.3681.6774.2360.3664.3576.0678.1882.7584.2779.4979.386.7668.7486.6486.3683.5574.6661.2966.1776.3380.3582.2584.0680.3779.3885.468.2286.0987.6681.6774.2359.5563.4576.0678.3984.8582.780.8980.0186.6869.8286.485.8681.6775.7260.3665.279.3382.2181.0383.0582.0680.6687.3168.7186.8886.183.3374.2360.7265.4176.0680.3281.8982.6180.7680.8785.9369.9286.0585.8482.2874.2360.2763.3376.3378.6181.7682.5480.7679.3886.2570.4186.486.3680.3374.2359.9164.0476.3378.6783.3183.0580.1280.1186.2568.9286.3686.3681.6775.5459.5563.7475.2679.6882.5683.8181.5479.9784.9870.687.2685.8481.6775.0959.5563.8475.5279.4182.7583.0581.548186.2571.7485.7586.3681.6774.3460.4566.1776.8780.3884.4682.6179.7480.6886.7669.0886.1285.8482.4974.2359.5563.9475.2678.3981.8283.2781.6780.8785.468.8985.4586.182.8674.5959.8267.5573.9778.4584.4683.0580.3779.8986.6869.3386.1986.3681.6775.7261.266.177581.3182.1883.3679.6280.8786.7670.4186.3686.3681.6775.3960.1867.3174.4881.738283.3682.0680.1187.3169.0486.05


## 5. Conclusions

The article describes a hybrid search algorithm for the irregular packing problem. The packing problem is presented as a sequence of pieces. The sequence is searched by the proposed hybrid search algorithm BSTS and decoded by an improved placement principle. The improved orbiting method of NFP is presented. It can create potential translation vectors and find a feasible translation vector in a significantly faster time. The placement position of each piece is determined by an evaluation, which is also the local evaluation of the hybrid search algorithm. To generate complete solutions, tabu search is applied to search over the unpacked pieces and decide Beam nodes by using global evaluation. The hybrid algorithm BSTS is somehow deterministic and can produce some good results with less time consumed. Furthermore, hybridizing BS with TS can decrease the possibility of removing other good solutions caused by the determinacy of the single BS approach.The experiments show that the hybrid algorithm is an applicative and effective algorithm for the irregular packing problem. To demonstrate its efficiency and determinacy, the proposed algorithm can produce three better results and four comparable results that are within 1% of the average results of SAHA in the 14 benchmark problems. Also, the algorithm can produce available solutions much faster thanμ-BRKGA approaches.In future work, the performance of the BSTS will be examined in more instances available on the ESICUP website, extending the ideas developed here to other bin packing problems with irregular pieces, such as the problems arising from cutting leather, in which bins are neither identical nor rectangular, and can even have some defects, defining nonusable zones.



---

*Source: 5054916-2021-01-21.xml*