Sage Journals: Discover world-class research

Abstract

A backtracking heuristic algorithm (BHA) was proposed for a two-dimensional rectangular strip packing problem with rotations and without guillotine cutting, which has many applications. An improved fitness strategy was used to select the fittest rectangle to be packed on a strip with a certain height. Next, a backtracking constructive heuristic was repeatedly used at a higher height until all the rectangles were packed. A multi-start improvement procedure then found the best solution by taking a different rectangle as the first rectangle, whereas the sequence of the other rectangles remained unchanged. Finally, in order to further expand the scope of the solution, a simple randomized local search procedure based on random sequences of rectangles with the first rectangle unchanged was applied to search for the optimal solution. BHA has only two parameters; it is simple and effective. Computational results on benchmark problems (zero-waste instances and non-zero-waste instances) with different scales (from 10 to 75,032 rectangles) indicate the following: (1) though it is non-deterministic, the difference between the results after each running is tiny and (2) the proposed algorithm outperforms most of the other algorithms under comparison on the whole, especially for large-scale instances with more than 1000 rectangles, which is further verified by statistical analysis and greatly meaningful in mass industrial production like metal cutting.

Keywords

Packing backtracking heuristic multi-start improvement local search large-scale instance

Introduction

In numerous industries, two-dimensional rectangular strip packing problems (2DRSPPs) are frequently encountered when cutting materials such as paper, glass, textiles, wood, metal, and other sheet materials. Given a set of n rectangles and a rectangular strip of fixed width and infinite height, the task is to pack all rectangles in the strip while minimizing the height of the strip used. Lodi et al.¹ categorized 2DRSPPs into RF, RG, OF, and OG. The first letter indicates whether the rectangles can be rotated by 90° (R if rotation is allowed; O otherwise). The second letter indicates whether guillotine cutting is considered (G if considered; F otherwise). More variants of 2DRSPPs can be found in Lodi et al.,² Bortfeldt & Wäscher,³ and Erjavec et al.⁴ This study focuses on the RF sub-type, which is often encountered in many industries such as metal cutting and glass cutting without directional restrictions of the rectangles to be packed.

2DRSPP is a typical NP-hard problem,⁵ and numerous algorithms have been proposed to solve it.^1,6–10 Generally, there are typically three types of algorithms: exact algorithms, heuristic algorithms, and meta-heuristic algorithms. Exact algorithms ensure the solutions generated are optimal. However, with the number of rectangles increasing, the execution time becomes too high to be accepted. Martello et al.¹¹ and Kenmochi et al.¹² demonstrated that the commonly-used branch and bound algorithm was inefficient in solving benchmark instances with more than 200 rectangles. Therefore, most researchers have devoted their efforts to heuristic algorithms.¹³ Oliveira et al.¹⁰ have comprehensively reviewed the heuristics proposed for 2DRSPPs. The famous heuristic algorithms are bottom-left (BL) algorithms and their variants. The heuristic algorithms based on fitness strategies are also commonly used. With the popularization of intelligent algorithms, meta-heuristic algorithms have been presented. Genetic algorithms, simulated annealing algorithms, neural network algorithms, and mixed meta-heuristic algorithms are some of the most common intelligent algorithms. Meta-heuristic algorithms are non-deterministic and often have many parameters to adjust.

With the development of industrial technology, the number of rectangles involved in 2DRSPPs has increased sharply, leading to a demand of more effective algorithms for large-scale instances. Exact algorithms have difficulty to solve large-scale instances, while heuristic and meta-heuristic algorithms have some advantages, which have been proven by some exploratory work. For example, Hopper & Turton¹³ had demonstrated that some meta-heuristics could find good solutions for large-scale instances with more than 72 rectangles, but the running times were extremely long due to their higher computational complexity. Leung et al.¹⁴ had demonstrated that the hybrid simulated annealing algorithm (HSA) proposed could obtain high-quality solutions for large-scale instances with $n \geq 49$ rectangles. Leung & Zhang¹⁵ had demonstrated that the fast layer-based heuristic (FH) outperformed many algorithms for large-scale instances with greater than 200 rectangles. It should be noted that 200 rectangles are not large for current mass industrial production with the development of industrial technology, thus, it is necessary to keep exploring the potential of algorithms and to propose more potent algorithms.

The difficulty in solving larger instances lies in improving algorithm efficiency to make the solving time acceptable. In life, when we pack things, we always try to put them in a small box first. If it can't fit, we will replace it with a bigger box. By drawing inspiration from real-world events, our algorithm first attempts to pack all the rectangles in a strip with an ideal height. If this is not possible, some of the packed rectangles are backtracked, and the packing process is repeated under a higher height until all the rectangles are packed. Moreover, almost all studies on 2DRSPPs show that the sequence of rectangles significantly affects the solution quality. Although each rectangle's position impacts the solution quality, the first rectangle has a greater impact than the others because the rectangles in the other positions are chosen based on the nesting method under the first rectangle. Based on this empirical law, the backtracking heuristic algorithm (BHA) is proposed for 2DRSPPs.

In the BHA, the first fittest rectangle is first searched, and then the most suitable sequence of the other $n - 1$ rectangles is searched, so there are $n + (n - 1)!$ possible sequences of rectangles in all. In comparison, the other algorithms search for the optimal sequence of all the rectangles on the whole, which have $n!$ possible sequences of all the rectangles and require longer search times. Therefore, the proposed algorithm can significantly reduce the complexity of problem solving. Furthermore, this paper explores whether the proposed BHA can efficiently solve large-scale instances, especially the instance with more than 1000 rectangles. Correspondingly, its advantages have been fully demonstrated in this study.

The remainder of this paper is structured as follows. Section 2 shows the related works. Details of the backtracking constructive algorithm are illustrated in Section 3. The computational results for zero-waste and non-zero-waste instances with varying scales and large-scale instances are presented in Section 4, which also demonstrates the effect of multi-start improvement. Finally, Section 5 summarizes the conclusion.

Related works

So far many excellent algorithms have been developed to solve 2DRSPPs, which can be classified as exact algorithms, heuristic algorithms, and meta-heuristic algorithms. The exact algorithm based on integer programming formulation is one of the early algorithms developed to solve 2DRSPPs.⁵ Martello et al.¹¹ proposed a branch and bound algorithm for solving instances involving up to 200 rectangles. Kenmochi et al.¹² designed a branch and bound algorithm that introduced several branching rules and bounding operations to solve all benchmark instances with up to 29 rectangles for RF and all but one instance with up to 49 rectangles for OF. In general, exact algorithms easily find the optimal solution for small-scale instances but face challenges for large-scale instances.

Heuristic algorithms are becoming increasingly prevalent, because exact algorithms take too long to calculate.¹³ Baker et al.¹⁶ proposed a BL algorithm for placing each rectangle as downward and leftward as possible. Based on the BL algorithm, the bottom-left-fill,¹⁷ bidirectional best-fit,¹⁸ and modified bidirectional best-fit¹⁹ algorithms were presented. Burke et al.²⁰ developed a new best-fit algorithm to determine the fittest rectangle for a partial solution. FH,¹⁵ IA (an efficient intelligent search algorithm),²¹ and SRA (a simple randomized algorithm)²² are heuristics based on fitness strategies. Many excellent algorithms, such as the heuristic recursive algorithm,²³ heuristic rectangle packing (HRP) algorithm,²⁴ greedy randomized adaptive search procedure,²⁵ least wasted first heuristic algorithm,²⁶ and residual-space-maximized packing (RSMP) algorithm²⁷ were proposed. He et al. proposed a best-fit algorithm (BFA),²⁸ deterministic heuristic algorithm (DHA),²⁹ and dynamic reduction algorithm³⁰ built from the BFA.

In recent years, meta-heuristic algorithms have been another significant research focus. Jakobs³¹ and Liu & Teng³² used a genetic algorithm (GA) to evolve the ordering of all rectangles to be packed based on the BL heuristic. Dowsland et al.³³ enhanced the GA approach by using tree search bounds. Bortfeldt³⁴ built a GA to search the space of complete packing directly, rather than encoding of orderings as in the cases of Jakobs³¹ and Liu & Teng.³² Burke et al.³⁵ presented a simulated annealing enhancement of the best-fit heuristic (BSA). Dagli & Poshyanonda³⁶ used a neural network algorithm, but the running time was too long. Leung et al.³⁷ proposed a simulated annealing-genetic algorithm that outperformed the pure genetic algorithm. Leung et al. proposed a two-stage intelligent search algorithm (ISA)³⁸ and HSA¹⁴ by combining different fitness strategies with simulated annealing-genetic algorithms. Hifi et al.³⁹ presented a parallel beam combining a search beam with strip generation solution procedures.

It is observed that fitness strategies are commonly used not only in heuristics algorithms,^15,21–22 but also in meta-heuristic algorithms.^14,38 Generally, fitness strategies are used to select the best-fit rectangle for the current partial packing solution to ensure that each step in nesting is the current optimal choice. Based on fitness strategies or other best-fit chosen strategies, finding the optimal solution is equivalent to finding the best sequence of the rectangles. Therefore, many studies sort the rectangles in a specific order. The common sequence used is non-increasing ordering of perimeter,¹⁵ area,^23,26,27,29 height,^11,13,15,27 or width.¹³ Some authors^{14,15,21,22,38} have even proposed swapping all possible two rectangles in a sequence to obtain the best sequence, which is time-consuming; therefore, the algorithms always have time limits. Additional comparisons of HSA,¹⁴ FH,¹⁵ IA,²¹ SRA,²² and ISA³⁸ are presented in Table 1. For large-scale instances with $n \geq 1000$ rectangles, the contradiction between search efficiency and solution quality is more prominent. How to search the most suitable sequence of all the rectangles more efficiently deserves attention for improving algorithms to address large-scale instances.

Table 1.

Comparisons of HSA, FH, IA, SRA, and ISA.

Algorithm	Sub-type	First phase	Second phase	Third phase	Running times	Time limit (seconds per run)
HSA	OF	All use fitness strategies, but the details differ.	Swap all possible two rectangles in a sequence.	Simulated annealing algorithm	10	60
FH	RF, OF			None	1	60
IA	OF			Swap two random rectangles n times	10	60
SRA	OF			Swap two random rectangles n times	10	60
ISA	OF			Simulated annealing algorithm	10	60

To improve solution quality, Alvarez-Valdes et al.²⁵ backtracked the last $k %$ of rectangles packed and repacked them with a deterministic algorithm to eliminate possible incorrect selections generated in the final random process. Wei et al.²⁶ backtracked all the rectangles packed in a partial solution, but it took a long time because they ignored that the constructive heuristic based on the least wasted first strategy is deterministic with a given sequence of all the rectangles.

Despite numerous algorithms developed to solve 2DRSPPs, they mainly focused on solving small-scale instances, and solving large-scale instances has become a challenge. Heuristic algorithms are easy to understand and have advantages in searching speed, so they are more easily promoted and applied in engineering practices. On the basis of the aforementioned related work, BHA builds a backtracking constructive heuristic by combining a new fitness strategy and backtracking method that backtracks some packed rectangles and searches for the optimal sequence of all the rectangles in two pieces to improve the search efficiency and solution quality. Correspondingly, the presence of BHA could provide a new method and research reference for solving the RF sub-type of large-scale instances with $n \geq 1000$ rectangles.

Backtracking heuristic algorithm

BHA includes three phases: backtracking constructive heuristic, multi-start improvement, and randomized local search. In this section, some key principles are defined, followed by a detailed description of BHA.

Definitions

Definition 1 (horizontal line segment)

Assuming multiple rectangles have been already packed in a strip, horizontal and vertical line segments exist between the packed and unpacked regions. Several horizontal line segments are used to present the partial solution. Before packing, there is only one horizontal line segment—the bottom strip boundary.

Definition 2 (packing point)

The packing point is the left endpoint of the lowest horizontal line segment. If several lowest horizontal line segments exist at the same height, the leftmost segment is chosen. The packing point's coordinates are expressed as $(x, y)$ .

Definition 3 (available space)

For a given packing point $(x, y)$ , we can determine one available space S as follows: starting from point $(x, y)$ , go from left to right horizontally until one packed rectangle or the strip is contacted; then move from bottom to top vertically until the upper strip boundary is contacted.²⁹

The horizontal line segments, packing point, and available space change dynamically during packing. Figure 1(a) shows a partial solution for a strip of width W and finite height H. The horizontal line segments are AB, CD, EF, and GH. The lowest and highest horizontal line segments are EF and AB, respectively. E is the packing point according to Definition 2, and S is the available space constructed according to Definition 3. S is determined by seven variables: the coordinates $(x, y)$ of point E, height h between EF and the upper strip boundary, width w of EF, height $h_{l}$ of the left wall DE, height $h_{r}$ of the right wall FG, and height $H_{c u r r}$ of AB.

Figure 1.

Available space in a partial solution. (a) Available space in a partial solution and (b) the new available space.

Backtracking constructive heuristic algorithm

Constructive heuristic based on the fitness strategy

Imahori & Yagiura,⁴⁰ Burke et al.,³⁵ Wei et al.,⁴¹ and some authors^{14,15,21,22,38} have employed fitness strategies to promote good placement quality by placing the fittest rectangle in an available area. Usually, $h_{l}$ and $h_{r}$ are not equal, and the following cases are considered: $h_{l} \geq h_{r}$ and $h_{l} < h_{r}$ . For calculating the fitness value for each unpacked rectangle, when $h_{l} \geq h_{r}$ , FH, ISA, HSA, SRA, and IA defined 4, 5, 5, 7, and 8 cases, respectively, and the same as $h_{l} < h_{r}$ . For BHA, we define five cases as shown in Figure 2, where $r = min (h_{r}, h_{l})$ and $m = max (h_{r}, h_{l})$ .

Figure 2.

Fitness value.

Note that $f_{i}$ , $w_{i}$ , and $h_{i}$ are the fitness value, width, and height of the unpacked rectangle i, respectively. In Figure 2, the rectangle i may have solid or dotted edges. The solid edges indicate that the edges are fixed, while the horizontal and vertical dotted edges indicate that $h_{i}$ and $w_{i}$ can change, respectively.

For case (1), $w_{i} = w and h_{i} = r$ , then $f_{i} = 4$ .

For case (2), $f_{i} = 3$ ; moreover, case (2) differs from case (1) in that $h_{i} = m$ .

For case (3), $w_{i} = w$ and $h_{i} \neq \forall (m, r)$ , then $f_{i} = 2$ . There may be many rectangles with different heights that satisfy case (3). To increase utilization, the rectangle whose height is closest to $h_{r}$ or $h_{l}$ is selected as the candidate. If there are rectangles of which the heights meet $y + h_{i} \leq H_{c u r r}$ , the rectangle with the minimum value of $\min (| h_{l} - h_{i} |, | h_{r} - h_{i} |)$ is selected as the candidate. Otherwise, if there are rectangles of which the heights meet $H \geq y + h_{i} > H_{c u r r}$ , the rectangle having the minimum height becomes the candidate.

For cases (4.1) and (4.2), $w_{i} < w$ and $h_{i} = \forall (m, r)$ , then $f_{i} = 1$ . To maximize utilization, the rectangle with the maximum area is chosen as the candidate.

For case (5), $w_{i} < w$ and $h_{i} \neq \forall (m, r)$ , then $f_{i} = 0$ . Similar to case (3), if $y + h_{i} \leq H_{c u r r}$ , the rectangle with the maximum area is chosen as the candidate. Otherwise, if $H \geq y + h_{i} > H_{c u r r}$ , the rectangle with the minimum height is selected. If the left or right walls of S is the strip boundary, the candidate rectangle is packed near the boundary; otherwise, $| h_{i} - h_{l} |$ and $| h_{i} - h_{r} |$ are calculated, and the candidate rectangle is packed near the wall having a smaller difference. In contrast, FH, ISA, HSA, SRA, and IA always place the candidate near to the left wall when $h_{l} \geq h_{r}$ , and close to the right wall when $h_{l} < h_{r}$ . The placement rule in the BHA creates a new horizontal line segment that is close to the adjacent line segment in height.

If the widths of all unpacked rectangles meet $w_{i} > w$ , the available space S will be wasted. As shown in Figure 1(b), the lowest horizontal line segment EF is elevated to the height of its neighboring lower horizontal line segment CD, and the two horizontal line segments are merged into a new horizontal line segment CF′; then, the new lowest horizontal line segment is CF′, and a new S is constructed.

Since BHA handles the RF sub-type, each rectangle's initial and 90° rotation poses are considered during packing. The constructive heuristic based on the fitness strategy is as follows: At the beginning of packing, the first rectangle in the given sequence X is placed at the bottom left corner of the strip. The initial and 90° rotation poses of the first rectangle are considered, and there are two loops. For each loop, the fittest rectangle and its pose are selected individually according to the fitness strategy. If there is more than one rectangle meeting the requirements, the first hit rectangle is selected.

Backtracking constructive heuristic

At the beginning of packing, we set the height of strip H as the ideal solution $H_{0}$ . $H_{0} = 1 / W (\sum_{i = 1}^{n} A_{i})$ , where $A_{i}$ is the area of rectangle i. The $i_{t h}$ rectangle in X is denoted as $R_{i}$ . During packing, if not all rectangles are packed under H, the solution under H is noted as $S_{p}$ and there are t rectangles packed in $S_{p}$ , BHA achieves a partial solution $S_{p - m}$ by eliminating the last but no more than m rectangles packed in $S_{p}$ . If $t \geq m$ , m rectangles packed in $S_{p}$ are backtracked; otherwise, t rectangles are backtracked. Thereupon, let $H = H + 1$ , and the packing process is repeated from $S_{p - m}$ at the new height H. If not all the rectangles can be fully packed at the new height, the backtracking process is repeated until all the rectangles are packed. The above backtracking constructive heuristic is shown in Backtracking Algorithm $(X)$ .

Backtracking Algorithm $(X)$

01: Input: a strip with width W, given sequence X with n rectangles, and

H_{0}

02: Output: the smallest height H of strip achieved and the corresponding solution03: The first rectangle

R_{1}

in X is placed in the bottom left corner of the strip with the initial pose.04:

H \leftarrow H_{0}

05:

i \leftarrow 1

06: While

i \leq n

do07: Find the lowest horizontal line segment and available space

S (x, y, h, w, h_{l}, h_{r}, H_{c u r r})

.08: If an unpacked rectangle based on the fitness strategy can be found, then09: the rectangle is packed according to the constructive heuristic based on the fitness strategy.10:

i \leftarrow i + 1

11: Update the lowest horizontal line segment and S.12: Else if the width of each unpacked rectangle

w_{i} > w

, then13: S is wasted.14: Update the lowest horizontal line segment and S.15: Else if there is no unpacked rectangle fit for S because of the limit of H, then16: denote the partial solution as

S_{p}

.17:

H \leftarrow H + 1

18:

S_{p - m}

is achieved by eliminating the last but no more than m rectangles packed in

S_{p}

.19:

i \leftarrow i - m

20: Update the lowest horizontal line segment and S.21: end if22: end while23: the first rectangle

R_{1}

in X is placed in the bottom left corner of the strip with the rotating pose; repeat the above steps 04–22.24: compare the two H under the two poses of the first rectangle in X, and save the smaller one as H.25: return H, the corresponding sequence and the first rectangle's pose.

Multi-start improvement

If the solution H obtained by the Backtracking Algorithm $(X)$ is not the ideal solution $H_{0}$ , BHA uses the multi-start improvement algorithm to seek a better solution. Each rectangle is packed as the first rectangle, while the sequence of the other rectangles in X remains unchanged; then $n - 1$ new sequences $X^{'}$ are generated. Backtracking Algorithm $(X)$ is subsequently used to get $n - 1$ solutions and the solution with the minimum H is regarded as the best solution. If $H_{0}$ is achieved, the process stops immediately. The algorithm is described in Multi-start Improvement Algorithm.

Multi-start Improvement Algorithm

01: if Backtrack Algorithm

(X)

fails to obtain the ideal solution

H_{0}

then02: for

i \leftarrow 2

n

03: if H is not the ideal solution then04: let the

i_{t h}

rectangle in X be the first rectangle, while the sequence of the other rectangles in X remains unchanged, then a new sequence

X^{'}

is generated05:

H^{'} \leftarrow Backtrack Algorithm (X^{'})

06: if

H^{'} < H

then07:

H \leftarrow H^{'}

08: end if09: else10: break11: end if12: end for13: return H, the corresponding sequence

X \leftarrow X^{'}

and the first rectangle's pose in

X^{'}

14: end if

Randomized local search

If the solution obtained by the Multi-start Improvement Algorithm is not the ideal solution H₀, a simple randomized local search is used to improve the solution. The method to generate a random sequence of rectangles is as follows:

R₁ is taken as the first rectangle with the pose obtained in the multi-start improvement algorithm; two random rectangles in $(R_{2}, \dots, R_{n})$ of X are selected and swapped to generate a new sequence; the new sequence is taken as X. The process is repeated until the rectangles are swapped n times. Finally, a random sequence of rectangles is generated.

Backtracking Algorithm $(X)$ is used for random sequences no more than $l s$ times; if the ideal solution is achieved, the algorithm stops immediately. The simple randomized local search algorithm is as follows:

Randomized Local Search Algorithm

01: if Multi-start Improvement Algorithm fails to obtain the ideal solution

H_{0}

then02: for

i \leftarrow 1

l s

03: if H is not the ideal solution then04: for

j \leftarrow 1

n

05: randomly select two rectangles in the remaining

n - 1

rectangles except

R_{1}

X

06: swap the two rectangles in X and obtain a new sequence

X^{'}

X \leftarrow X^{'}

07: end for08:

H^{'} \leftarrow Backtrack Algorithm (X)

09: if

H^{'} < H

then10:

H \leftarrow H^{'}

11: end if12: else13: break14: end if15: end for16: return H and the corresponding sequence17: end if

Parameter setting

In the BHA, there are two parameters to be set: the number m of backtracking rectangles and the number $l s$ of randomized local search times. For demonstrating the effects of various m and $l s$ values adequately, we made tests on data sets of different sizes. Computational tests for benchmark instances of Nice, Path, and ZDF, have been conducted in order to select fit parameters for BHA.

Nice and Path: This data set generated by Valenzuela & Wang⁴² using the techniques described by Wang & Valenzuela⁴³ comprises 72 instances ranging from 25 to 5000. This float data set has similarly sized rectangles (Nice1–Nice5t) and vastly differently sized rectangles (Path1–Path5t). Nice1t, Nice2t, Nice5t, Path1t, Path2t, and Path5t include 10 instances. Because BHA is a fit for the integer data set. We used BHA for the data set at https://github.com/18439870129/BHA/tree/master with $W = 1000$ , and let $H = H / 10$ be the solution of the instances.

ZDF: This data set generated by Leung & Zhang¹⁵ comprises 16 instances ranging from 580 to 75,032.

BHA has three stages; m and $l s$ are needed in the second and third stages, respectively, so we first determine m, and then $l s$ .

Effect of various $m$

To determine m, computational tests of various m on the Nice, Path, and ZDF with $l s = 0$ were carried out. Figures 3 and 4 compare the solution H achieved under the conditions of $m = 0$ , 20, 50, 100, 150, 200, 250, and 300.

Figure 3.

Computational results of various m on the data sets Nice and Path.

Figure 4.

Computational results of various m on the data set ZDF.

For data sets Nice and Path, we observed that $m \geq 100$ can yield the same solutions except Path2t, and Path2t shows a slight increment of 0.1 when $m \geq 200$ . The worst solution is obtained at $m = 0$ . Though not always, a larger m usually yields better solutions.

For the data set ZDF, zdf1–zdf5 omitted in Figure 4 always had the same solutions. It is observed that $m \geq 100$ can yield the same solutions. The worst solution is obtained when $m = 0$ . A larger m always yields better results.

Overall, the solution of $m = 100$ is as good as that of $m = 150$ (yielding the best results). Considering the time-space overhead, the proposed BHA chooses $m = 100$ .

Effect of various $l s$

Since BHA has some randomness, the test was run 20 times for each condition with $m = 100$ and $l s > 0$ . $H_{s u m}$ is the sum of the H values for all instances in a data set. Figure 5 compares $H_{s u m}$ obtained under the conditions of $l s = 0$ , 200, 500, 1000, 1500, and 2000 on the data sets Nice, Path, and ZDF.

Figure 5.

Effect of various $l s$ .

For $l s = 200$ , 500, 1000, 1500, and 2000, the median values of Nice and Path were 1842.11, 1841.98, 1841.88, 1841.83, and 1841.81, respectively; and ZDF's median values were 58,713.5, 58,689.5, 58,681, 58,678.5, and 58,678.5, respectively. From $l s = 0 to 1000$ , the improvement was apparent, but when $l s > 1000$ , the improvement was less than 0.1 for Nice and Path, and less than 4 for ZDF. For $l s = 1000$ , 1500, and 2000, the mean values of Nice and Path were 1841.87, 1841.83, and 1841.81, respectively, and those of ZDF are 58,681.05, 58,677.8, and 58,677.05, respectively. With a larger $l s$ , the solution becomes better overall, but the improvement is slight when $l s > 1000$ . Considering the time-space overhead, the proposed BHA chooses $l s = 1000$ .

Computational results

There are many benchmark instances in the literature. Iori et al.⁴⁴ listed the benchmarks (C, N, and ZDF) originally proposed for 2DRSPPs. To evaluate the performance of BHA, we compared it with some other excellent algorithms for the RF sub-type on more instances with wide scales. The benchmark specifications are as follows.

C: This data set generated by Hopper and Turton¹³ comprises 21 instances with 16–197 rectangles.

N: This data set generated by Burke et al.²⁰ comprises 13 instances with 10–3152 rectangles.

CX: This data set generated by Pinto and Oliveira⁴⁵ comprises 7 instances with 50–15,000 rectangles.

Nice and Path: as mentioned above.

ZDF: as mentioned above.

There are two categories depending on whether there is unused space in the ideal solution. Zero-waste instances, such as C, N, and CX, are in the first category, and their optimal solutions are known as $H_{0}$ . Non-zero-waste instances such as Nice, Path, and ZDF constitute the second category.

BSA,³⁵ HRP,²⁴ FH,¹⁵ DHA,²⁹ and RSMP²⁷ solve the RF sub-type and have excellent solutions, and we mainly compare our algorithm with them. HRP, FH, DHA, and RSMP are deterministic algorithms that need to be run only once. BSA is a non-deterministic algorithm similar to BHA and is run 10 times to decrease the randomness; therefore, we ran BHA 10 times. BHA was performed using C#. The detailed computational environment is presented in Table 2.

Table 2.

Computational environments.

Algorithm	CPU (GHz)	RAM	Running times	Time limit (seconds per run)
BSA	2	256 MB	10	60
HRP	2	2 GB	1	10,000
FH	2	2 GB	1	60
DHA	3.0	2 GB	1	1000
RSMP	3.4	8 GB	1	No restriction in time
BHA	2.6	4 GB	10	No restriction in time

The computational results for BSA, FH, DHA, and RSMP were obtained from the original atricles.^15,27,29,35 The computational results of HRP were taken from Leung & Zhang,¹⁵ which differ from the original results,²⁴ where HRP was designed to calculate the waste area of each instance and just has original results for data set C.

LB represents the lower bound, which equals $H_{0}$ . For each instance, if H = LB, the solution is optimal. For an algorithm that needs to be run only once, H and Gap are the results. For an algorithm that needs to be run several times, BestH, MeanH, and BestGap denote the best and mean results. Gap% is the percentage of Gap to LB, that is, $G a p = 100 \times (H - L B) / L B$ . Sum. is the total value of each column. The best result (equal to the optimal result) for each instance is shown in bold letters and marked with *, whereas the best result (not equal to the optimal result) for each instance is shown in bold letters. “—” denotes that the solution cannot be found within the time limit. T signifies the running time, and its units are seconds. In the column of T, “0” signifies that the running time is not more than 0.01 s. Blank denotes the instance not computed by the corresponding algorithm.

Computational results on zero-waste instances

Tables 3‒5 present the computational results for C, N, and CX, respectively. We compared BestH of BHA with those of other algorithms.

Table 3.

Computational results on the data set C.

Instance				BSA	HRP		FH		DHA		RSMP	BHA
	$n$	$W$	LB	BestH	H	$T (s)$	$H$	$T (s)$	$H$	$T (s)$	$H$	BestH	$T (s)$	MeanH
C11	16	20	20	20*	20*	0.03	20*	0	20*	0	21	21	0.16	21
C12	17	20	20	20*	20*	0.19	20*	0.01	21	0.3	21	21	0.15	21
C13	16	20	20	20*	20*	0.03	21	0	20*	0.02	21	21	0.19	21
C21	25	40	15	16	15*	0.27	16	0.02	15*	0.59	16	15*	0.02	15*
C22	25	40	15	16	15*	0.06	15*	0	15*	0.23	16	15*	0.00	15*
C23	25	40	15	16	15*	0.05	15*	0	15*	0.06	16	16	0.31	16
C31	28	60	30	31	31	0.61	31	0.02	31	3.27	31	31	0.27	31
C32	29	60	30	31	31	0.61	31	0.02	32	5.14	31	32	0.40	32
C33	28	60	30	31	31	0.63	32	0.02	30*	0.25	31	30*	0.00	30*
C41	49	60	60	61	61	1.84	61	0.16	61	20.86	61	61	0.49	61
C42	49	60	60	61	60*	0.23	61	0.11	61	16.95	61	61	0.68	61
C43	49	60	60	61	61	2.02	61	0.08	60*	14.62	61	61	0.44	61
C51	73	60	90	91	91	4.3	91	0.28	90*	2.02	92	91	0.83	91
C52	73	60	90	91	90*	1.34	90*	0	90*	15.62	91	91	1.08	91
C53	73	60	90	92	91	4.3	91	0.3	90*	39.18	92	92	1.21	92
C61	97	80	120	122	121	9.84	121	0.83	121	169.53	122	121	1.32	121
C62	97	80	120	121	121	8.38	121	0.89	121	139.25	121	121	1.05	121
C63	97	80	120	122	121	9.94	121	0.76	120*	2.7	122	121	1.31	121
C71	196	160	240	244	241	61.48	241	13.91	241	1000	243	241	4.70	241
C72	197	160	240	244	241	58.91	241	11.64	241	1000	243	241	3.56	241
C73	196	160	240	245	241	62.9	241	15	241	1000	242	241	3.90	241
Sum.				1756	1738	227.96	1742	44.05	1736	3430.59	1755	1745	22.08	1745

In Table 3, BHA obtained three optimal results, whereas DHA, HRP, FH, BSA, and RSMP obtained 11, 8, 5, 3, and 0 optimal results, respectively. Figure 6 shows that $H_{s u m}$ of BHA is 1745, which outperforms BSA (1756) and RSMP (1755), but is inferior to DHA (1736), HRP (1738), and FH (1742). In detail, it is shown that BHA is not as powerful as the other methods for instances with few rectangles ( $n \leq 90$ ), but for the six instances (C61, C62, C63, C71, C72, and C73) with more than 90 rectangles, the results of BHA are the same as those of FH and HRP; the result of C63 of BHA (BestH = 121) is slightly worse than that of DHA (BestH = 120). Moreover, though BHA has no time restriction, the running time of each instance varies from 0 to 4.7 seconds. In contrast, HRP, FH and DHA have time limits and the running time of each instance varies greatly, their shortest and longest times being 0.03 to 62.9, 0 to 15, and 0 to 1000 seconds, respectively. BHA had the smallest standard deviation (1.34), while those of HRP, FH, and DHA were 21.27, 4.82, and 352.88, respectively, signifying that the running time of BHA was the most stable for the data set C.

Figure 6.

Comparison on the data set C.

Table 4 shows that BHA finds 2 optimal results in the overall 13 instances, while the numbers of optimal results obtained by BSA, HRP, FH, DHA, and RSMP are 2, 1, 2, 8, and 1, respectively. As shown in Figure 7, DHA ( $H_{s u m} = 2318$ ) is the best algorithm for N, followed by FH and BHA, which have the same $H_{s u m}$ (2326), signifying that although only two optimal results are obtained by BHA, the overall effect is quite competitive. With the exception of N13, all instances of BHA have steady running times ranging from 0 to 9.16 seconds. The running times of BHA, HRP, and DHA for N13 with 3152 rectangles were 221.36, 2743.48, and 191.67 seconds, respectively. The running time of BHA is acceptable, even for instance with 3152 rectangles.

Figure 7.

Comparison on the data set N.

Table 4.

Computational results on the data set N.

Instance				BSA	HRP		FH		DHA		RSMP	BHA
	$n$	$W$	LB	BestH	H	$T (s)$	$H$	$T (s)$	$H$	$T (s)$	$H$	BestH	$T (s)$	MeanH
N1	10	40	40	40*	40*	0.03	40*	0	40*	0.02	40*	40*	0	40*
N2	20	30	50	50*	51	0.02	52	0	51	0.42	53	51	0.22	51
N3	30	30	50	51	51	0.61	51	0.02	50*	0.2	52	51	0.29	51
N4	40	80	80	82	81	2.09	83	0.03	81	9.11	83	82	0.51	82
N5	50	100	100	103	102	4.08	102	0.08	103	13.91	106	103	0.73	103
N6	60	50	100	102	102	5.55	101	0.03	100*	2.36	102	101	0.50	101
N7	70	80	100	104	102	9	102	0.13	102	41.5	102	103	1.33	103
N8	80	100	80	82	81	6.78	81	0.23	80*	29.69	82	81	0.85	81
N9	100	50	150	152	152	23.27	151	0.14	150*	0.25	154	151	1.10	151
N10	200	70	150	152	151	61.19	151	0.55	150*	0.16	152	151	2.24	151
N11	300	70	150	153	151	67.69	151	1.48	150*	0.61	152	151	3.87	151
N12	500	100	300	306	305	85.72	301	5.63	301	1000	305	301	9.16	301
N13	3152	640	960	964	972	2743.48	960*	1.91	960*	191.67	962	960*	221.36	960*
Sum.				2341	2341	3009.51	2326	10.23	2318	1289.9	2345	2326	242.18	2326

In Table 5, BHA obtained optimal results for all instances (500cx, 1000cx, 5000cx, 10000cx, and 15000cx) with no less than 500 rectangles; however, the results for 50cx and 100cx are poor. $H_{s u m}$ of BHA (4248) is better than that of DHA (4284) and slightly worse than that of FH (4243), but it is better than that of FH excluding 100cx.

Table 5.

Computational results on the data set CX.

Instance				HRP		FH		DHA		RSMP	BHA
	$n$	$W$	LB	H	$T (s)$	$H$	$T (s)$	$H$	$T (s)$	$H$	BestH	$T (s)$	MeanH
50cx	50	400	600	615	10.09	624	0.33	644	26.91	612	618	4.50	618
100cx	100	400	600	615	47.88	619	3.56	637	266.64	600*	630	15.07	630
500cx	500	400	600	611	87.31	600*	2	601	1000	600*	600*	0.06	600*
1000cx	1000	400	600	607	86.08	600*	0.02	600*	628.48	600*	600*	0.08	600*
5000cx	5000	400	600	607	9256.37	600*	0.05	600*	3.92	600*	600*	0.92	600*
10000cx	10,000	400	600	—	—	600*	0.05	600*	6.5	600*	600*	3.77	600*
15000cx	15,000	400	600	—	—	600*	0.06	600*	9.88	600*	600*	8.14	600*
Sum.						4243	6.07	4282	1942.33	4212	4248	32.54	4248

For data sets C, N, and CX, Figure 8 shows that BHA always performs better than BSA and outperforms RSMP in most instances. Although DHA performed better than BHA for C and N with mostly small-scale instances, it performed worse for CX. FH is stable in finding good solutions for all data sets. FH is better than BHA not only for $H_{s u m}$ but also for the number of best results obtained. A closer study in Table 6 reveals that BHA performed better than FH in five instances and slightly worse than FH in nine instances with 16–100 rectangles (C11, C12, C23, C32, C52, C53, N5, N7, and 100cx). Overall, our BHA is not always the best in small-scale instances, but is quite competitive among the algorithms presented. The running time of BHA increases as the number of rectangles increases, but it is fast except for N13; and the running time of BHA is more stable than those of HRP and DHA.

Figure 8.

Comparison on the data sets C, N, and CX.

Table 6.

Comparison between BHA and FH for the data sets (C, N, and CX).

Instance				FH	BHA
	n	W	LB	H	BestH	MeanH
C11	16	20	20	20*	21	21
C12	17	20	20	20*	21	21
C21	25	40	15	16	15*	15*
C23	25	40	15	15*	16	16
C32	29	60	30	31	32	32
C33	28	60	30	32	30*	30*
C52	73	60	90	90*	91	91
C53	73	60	90	91	92	92
N2	20	30	50	52	51	51
N4	40	80	80	83	82	82
N5	50	100	100	102	103	103
N7	70	80	100	102	103	103
50cx	50	400	600	624	618	618
100cx	100	400	600	619	630	630

The best and mean results of BHA are always the same, as shown in Tables 3 to 5. This phenomenon can occur because they are zero-waste instances and most instances are not large. Despite applying the randomized local search method 1000 times, the solution space remains restricted after the initial rectangle $R_{1}$ is generated in the BHA.

Computational results on non-zero-waste instances

Table 7 and Figure 9 show that BSA and HRP are unable to develop solutions for large-scale instances within the time limit, and all solutions of BHA, with the exception of Path1, Path2, and Path3, are inferior to those of FH and BHA. Although HRP has good solutions for small-scale instances, it is inferior to FH and BHA for all instances with $n \geq 1000$ rectangles. The running time of HRP increased rapidly, whereas those of FH and BHA did not. Leung et al.¹⁵ had demonstrated that FH outperformed many algorithms for the instances with greater than 200. For these reasons, a comparison between BHA and FH was conducted.

Figure 9.

Comparison between BHA and FH for the data sets Nice and Path.

Table 7.

Computational results on the data sets Nice and Path.

Instance				BSA	HRP		FH		BHA
	$n$	$W$	LB	BestH	$H$	$T (s)$	$H$	$T (s)$	BestH	$T (s)$	MeanH
Nice1	25	100	100	104.02	102.4	2.71	104	0.05	104.2	3.68	104.2
Nice2	50	100	100.1	104.41	102.5	12.87	106.4	0.41	105.2	11.36	105.2
Nice3	100	100	100.1	105.04	102.5	60.24	103.7	4.23	103.3	16.96	103.3
Nice4	200	100	100.1	104.74	101.9	62.38	102.4	36.03	102.5	18.97	102.5
Nice5	500	100	100	103.51	101.7	81.98	100.8	60.03	101.1	29.42	101.1
Nice6	1000	100	99.9	103.76	101.1	143.8	100.6	60.03	100.4	55.02	100.49
Nice1t	1000	100	100.1	—	101.2	144.57	100.6	60.04	100.64	56.22	100.79
Nice2t	2000	100	100.1	—	101.2	1142.4	100.4	60.05	100.33	142.85	100.37
Nice5t	5000	100	100.1	—	—	—	100.2	60.05	100.14	751.76	100.17
Path1	25	100	100.1	103.09	102.5	2.67	106.4	0.06	106.6	4.59	106.6
Path2	50	100	100	103.4	104.7	14.66	103.8	0.36	105.5	11.70	105.5
Path3	100	100	100	103.04	104.4	60.37	103.3	4.31	103.5	21.82	103.5
Path4	200	100	100.2	103.42	101.9	63.73	101.8	56.31	104.4	137.06	104.4
Path5	500	100	100	103.48	101.7	83.41	101.3	60.03	102.7	113.33	102.7
Path6	1000	100	100.2	102.87	101.3	146.9	101.2	60.05	100.6	63.77	100.6
Path1t	1000	100	100.1	—	101.2	147.13	100.7	60.05	100.32	62.46	100.32
Path2t	2000	100	100.1	—	101.2	1024.7	100.5	60.06	100.15	179.20	100.16
Path5t	5000	100	99.9	—	—	—	100.2	60.08	99.95	965.06	99.97
Sum.							1838.3	702.23	1841.53	2645.23	1841.87

LB of each instance in Nice and Path has a value of approximately 100. As shown in Figure 9, the greater the number of rectangles in an instance, the closer the solution is to 100. Each line has two valleys composed of instances with at least 1000 rectangles (Nice6, Nice1t, Nice2t, Nice5t, etc.), which shows that BHA is better at solving large-scale instances. $H_{s u m}$ of FH is the best, which is 3.23 less than that of BHA, upon closer inspection; FH outperforms BHA just in most instances with a small sample space, e.g. Nice1, Nice5, Path1, Path4; while for instances with $n \geq 1000$ rectangles, BHA outperforms FH except for Nice1t. For Nice1t, if BHA rounds to one decimal place, the results will be the same. With the increase in the number of rectangles, the gap between BHA and FH became increasingly obvious, which fully demonstrates that BHA is more effective for instances with $n \geq 1000$ rectangles.

The comparative results of the various algorithms for ZDF are summarized in Table 8. BHA, FH and HRP obtained 11, 8, and 0 optimal results, respectively. BHA obtained the most optimal results. FH outperformed BHA in only three instances (zdf8–zdf10), whereas BHA outperformed FH in five instances (shown in Figure 10). It is noted that the result of zdf8 computed by BHA is especially poor, which is 63 higher than that of FH. Nonetheless, the $H_{s u m}$ of FH is 39 higher than that of BHA. Therefore, BHA is the best algorithm for ZDF with large-scale instances for obtaining the most optimal results and best overall quality.

Figure 10.

Comparison between BHA and FH for the data set ZDF.

Table 8.

Computational results on the data set ZDF.

Instance				FH			HRP		BHA
	$n$	$W$	LB	$H$	Gap	$T (s)$	$H$	$T (s)$	BestH	BestGap	$T (s)$	MeanH
zdf1	580	100	330	330*	0*	0.22	331	74.92	330*	0*	0.52	330*
zdf2	660	100	357	357*	0*	2.52	359	64.09	357*	0*	14.54	357.3
zdf3	740	100	384	384*	0*	0.11	386	90.11	384*	0*	0.59	384*
zdf4	820	100	407	407*	0*	0.06	409	115.63	407*	0*	21.19	407.9
zdf5	900	100	434	434*	0*	0.02	438	68.06	434*	0*	0.05	434*
zdf6	1532	3000	4872	5146	5.62	20.03	4932	502.69	5082	4.31	262.74	5082
zdf7	2432	3000	4852	5031	3.69	39.48	4912	1444.19	5016	3.38	311.13	5016
zdf8	2532	3000	5172	5180	0.15	60.06	5236	1355.23	5243	1.37	372.34	5277.9
zdf9	5032	3000	5172	5173	0.02	60.11	5236	8964.57	5177	0.1	915.20	5177
zdf10	5064	6000	5172	5175	0.06	60.13	—	—	5182	0.19	1062.51	5182.2
zdf11	7564	6000	5172	5186	0.27	60.23	—	—	5172*	0*	2542.82	5172.6
zdf12	10,064	6000	5172	5185	0.25	60.24	—	—	5172*	0*	4013.45	5172
zdf13	15,096	9000	5172	5179	0.14	60.22	—	—	5172*	0*	7684.94	5172.8
zdf14	25,032	3000	5172	5172*	0*	2.17	—	—	5172*	0*	145.49	5172*
zdf15	50,032	3000	5172	5172*	0*	2.02	—	—	5172*	0*	281.54	5172*
zdf16	75,032	3000	5172	5172*	0*	2.84	—	—	5172*	0*	517.13	5172*
Sum.				58,683	10.2	430.46			58,644	9.35	18,146.18	58,681.7

Tables 7 and 8 show that BHA has a certain uncertainty for large-scale instances, but the gaps between the best and mean results are smaller, except for zdf8. MeanH of BHA is almost the same as BestH of BHA for Nice and Path. For ZDF, they are different, but even MeanH of BHA is better than H of FH.

Table 9 analyzes the running times of all algorithms mentioned previously. STD is the standard deviation. Range is from the minimum time to the maximum time. The running time and STD of BHA for each data set are significantly smaller than those of HRP and DHA. Since there is no running time limit for BHA, the computation time and STD of BHA increases with increasing number of rectangles, whereas those of FH change slightly because of its limitation of 60 seconds. Although the computation time of BHA is longer than that of FH mostly, it is acceptable. STD of BHA for each data set signifies that BHA is more stable than HRP and DHA in terms of the running time.

Table 9.

The running time comparison.

Data set	HRP			FH			DHA			BHA
	Mean	STD	Range	Mean	STD	Range	Mean	STD	Range	Mean	STD	Range
C	10.9	21.3	0.03–62.9	2.1	4.8	0–15	163.4	352.9	0–1000	1.1	1.3	0–4.7
N	231.5	755.3	0.02–2743.48	0.8	1.6	0–5.63	99.2	275.6	0.02–1000	18.6	61.0	0–221.36
CX	1897.5	4113.8	10.09–9256.37	0.9	1.4	0.02–3.56	277.5	393.3	3.92–1000	4.65	5.4	0.06–15.07
Nice and Path	199.7	349.4	2.67–1142.4	39.0	27.8	0.05–60.08				147.0	266.6	3.68–965.06
ZDF	1408.8	2887.7	64.09–8964.57	26.9	28.4	0.02–60.24				1134.1	2060.6	0.05–7684.94

Computational results on large-scale instances

To illustrate the advantages of BHA on large-scale instances of various kinds, Table 10 summarizes the results of all instances of $n \geq 500$ in data sets N, CX, Nice, Path, and ZDF. BSA, HRP, DHA, RSMP, FH, and BHA obtained 0, 0, 5, 5, 14, and 16 optimal results, respectively, in 33 instances. The results revealed that FH outperformed BHA in six instances, whereas BHA outperformed FH in 12 instances. Moreover, BHA obtained the minimum sum of BestH and BestGap. For all instances of $n \geq 1000$ in Table 10, BSA, HRP, DHA, RSMP, FH, and BHA obtained 0, 0, 4, 5, 8, and 10 optimal results in 24 instances, respectively. The results revealed that FH outperformed BHA in only four instances; however, BHA still outperformed FH in 12 instances. Generally, it is more difficult to obtain better results for instances with more rectangles. Surprisingly, for instances with $n \geq 1000$ rectangles, the probability of BHA obtaining good results enhanced greatly.

Table 10.

Computational results on instances of n ≥ 500.

Instance				BSA	HRP	RSMP	DHA	FH		BHA
	$n$	$W$	LB	BestH	$H$	$H$	$H$	$H$	Gap	BestH	BestGap
N12	500	100	300	306	305	305	301	301	0.33	301	0.33
500cx	500	400	600		611	600*	601	600*	0*	600*	0*
Nice5	500	100	100	103.51	101.7			100.8	0.8	101.1	1.1
Path5	500	100	100	103.48	101.7			101.3	1.3	102.7	2.7
zdf1	580	100	330		331			330*	0*	330*	0*
zdf2	660	100	357		359			357*	0*	357*	0*
zdf3	740	100	384		386			384*	0*	384*	0*
zdf4	820	100	407		409			407*	0*	407*	0*
zdf5	900	100	434		438			434*	0*	434*	0*
1000cx	1000	400	600		607	600*	600*	600*	0*	600*	0*
Nice6	1000	100	99.9	103.76	101.1			100.6	0.7	100.4	0.4
Nice1t	1000	100	100.1	—	101.2			100.6	0.5	100.64	0.54
Path6	1000	100	100.2	102.87	101.3			101.2	1	100.6	0.6
Path1t	1000	100	100.1	—	101.2			100.7	0.6	100.32	0.22
zdf6	1532	3000	4872		4932			5146	5.62	5082	4.31
Nice2t	2000	100	100.1	—	101.2			100.4	0.3	100.33	0.23
Path2t	2000	100	100.1	—	101.2			100.5	0.4	100.15	0.05
zdf7	2432	3000	4852		4912			5031	3.69	5016	3.38
zdf8	2532	3000	5172		5236			5180	0.15	5243	1.37
N13	3152	640	960	964	972	962	960*	960*	0*	960*	0*
5000cx	5000	400	600		607	600*	600*	600*	0*	600*	0*
Nice5t	5000	100	100.1	—	—			100.2	0.1	100.14	0.04
Path5t	5000	100	99.9	—	—			100.2	0.3	99.95	0.05
zdf9	5032	3000	5172		5236			5173	0.02	5177	0.1
zdf10	5064	6000	5172		—			5175	0.06	5182	0.19
zdf11	7564	6000	5172		—			5186	0.27	5172*	0*
10000cx	10,000	400	600		—	600*	600*	600*	0*	600*	0*
zdf12	10,064	6000	5172		—			5185	0.25	5172*	0*
15000cx	15,000	400	600		—	600*	600*	600*	0*	600*	0*
zdf13	15,096	9000	5172		—			5179	0.14	5172*	0*
zdf14	25,032	3000	5172		—			5172*	0*	5172*	0*
zdf15	50,032	3000	5172		—			5172*	0*	5172*	0*
zdf16	75,032	3000	5172		—			5172*	0*	5172*	0*
Sum.								63,950.5	16.53	63,911.33	15.61

For BSA and HRP, not all instances could be computed within the time limit. DHA and RSMP did not compute instances of Nice, Path, and ZDF. Hence, we just compare the summarized results of BHA with those of FH that performed better for instances with $n \geq 200$ ¹⁵ here.

Figure 11 shows the comparison between BHA and FH, and Figure 11(a) to (d) shows instances with $500 \leq n < 1000$ , $1000 \leq n < 5000$ , $5000 \leq n < 10, 000$ , and $n \geq 10, 000$ rectangles, respectively. Each category contains 6–11 instances from various data sets, which makes the comparison more reliable. For instances with $500 \leq n < 1000$ rectangles, FH outperforms BHA; for instances with $1000 \leq n < 10, 000$ rectangles, BHA outperforms FH on most instances except for zdf8-zdf10; for instances with $n \geq 10, 000$ rectangles, BHA outperforms FH. It is clear that there is a tendency from not always better to always better, proving that BHA is superior to the existing best algorithm FH on large-scale instances, particularly those with $n \geq 1000$ rectangles.

Figure 11.

Comparison between BHA and FH for instances with no less than 500 rectangles.

In order to further test the superiority of BHA in solving instances with $n \geq 1000$ rectangles, a statistical analysis was carried out between BHA and FH in 24 instances with $n \geq 1000$ rectangles. Neither sample conformed to the normal distribution; therefore, a two-related-sample rank sum test was performed. The test results are shown in Table 11. M is the median value (50th percentile value), $P_{25}$ and $P_{75}$ are the 25th and 75th percentile values, respectively, Z is the standardized test statistic value, and P is the progressive significance value. It can be seen that $Z = - 2.224$ and $P = 0.026 < 0.05$ . There is a significant difference between the solutions of BHA and those of FH. The results of BHA were obviously better than those of FH.

Table 11.

Comparison between BHA and FH for instances with no less than 1000 rectangles.

Algorithm	$M (P_{25}, P_{75})$	Two-related-sample rank sum test
Algorithm	$M (P_{25}, P_{75})$	$Z$	$P$
FH	0.145 (0,0.475)	−2.224	0.026
BHA	0.045 (0,0.3575)	−2.224	0.026

According to the computational results, DHA is the best algorithm for data sets C and N, RSMP is the best for CX, HRP is the best for Nice1–4, FH is the best for Nice and Path on the whole, and BHA is the best for ZDF. Moreover, BHA performs best for large-scale instances with $n \geq 1000$ rectangles than all existing algorithms (to our knowledge) for the RF sub-type, which is its typical characteristic and particularly meaningful. In industrial production, using large sample space is more rewarding and practical than using a small sample space because of the enormous numbers of rectangles to be packed simultaneously. Therefore, finding an excellent algorithm for solving large sample spaces quickly and stably can effectively reduce industrial losses and improve work efficiency.

Effect of multi-start improvement

The ordering of all rectangles can impact the solution quality, but traversing all possible positions of the rectangles is time-consuming and impractical for large-scale instances. Considering the first rectangle has a greater impact than the others, BHA adopts a multi-start improvement strategy which makes all rectangles take turns as the first rectangle to balance the computation time and solution quality. To test the effect of the multi-start improvement strategy, the computational results of BHA without the multi-start improvement strategy were compared with those of the normal BHA, as listed in Table 12. ΔBestGap is the gap between the two BestHs in a line divided by BestH of BHA without the multi-start improvement phase. The multi-start improvement strategy significantly improves the solutions for all data sets. ZDF and Path have the greatest impact because ZDF has the largest variety of rectangular areas (1–1,081,080) and Path has significantly diverse rectangles.

Table 12.

Comparison between BHA with and without the multi-start improvement strategy.

Instance	n	BHA (without the multi-start improvement strategy)		BHA (with the multi-start improvement strategy)		ΔBestGap
		BestH	MeanH	BestH	MeanH
C	16–196	1764	1764	1745	1745	1.08
N	10–3152	2355	2355.2	2326	2326	1.23
CX	50–15,000	4286	4286	4248	4248	0.89
Nice	25–5000	931.3	931.71	917.81	918.12	1.45
Path	25–5000	958.46	958.64	923.72	923.75	3.62
ZDF	580–75,032	60,391	60,523.8	58,644	58,681.7	2.89

Nice and Path are similar in that they have the same instances, and their corresponding instances have the same rectangles. The most difference between them is Nice with similarly sized rectangles, but Path with vastly different rectangles. We made a comparison of ΔBestGap between Nice and Path, as shown in Figure 12, to test the effect of the multi-start improvement strategy on the size difference of rectangles. Except for the first instance, every instance in Path was better than the corresponding instances in Nice. The larger the size differences of rectangles in an instance, the more significant the effect of the multi-start improvement. This is because the direction of subsequent layout is largely determined by the first rectangle. A different first rectangle may result in significant variations in the solution if the rectangles’ sizes differ significantly.

Figure 12.

Comparison of ΔBestGap between Nice and Path.

Conclusion

The fitness method and the backtracking heuristic are combined in the backtracking constructive heuristic stage. The unique fitness method outperformed the current literature studies (FH, ISA, HSA, IA, and SRA). The backtracking heuristic was used under different heights to pack all the rectangles in a strip with the minimum possible height. For saving running time, BHA backtracked no more than m rectangles packed from the current solution. The computational results of BHA without a multi-start improvement strategy demonstrated that the first rectangle in a sequence significantly impacts the solution quality, and the larger the size difference of rectangles in an instance, the more significant the effect of the multi-start improvement. Furthermore, a local search stage based on random sequences was proposed to improve the solution. BHA is straightforward to implement, with only two parameters m and $l s$ . Although BHA is non-deterministic, the average and best results for zero-waste instances are always the same, and the gaps between the best and average values for non-zero-waste instances are minimal so that the quality of BHA is fairly stable. Computational results for a wide range of benchmark instances demonstrated that the proposed algorithm outperformed the most recently described heuristics (to the best of our knowledge). Although it did not always find the best solution for each instance, it consistently found the best results for almost all large-scale instances with $n \geq 1000$ rectangles, which is meaningful because there are lots of rectangles to be packed in mass production. Moreover, its running time is stable and acceptable, which facilitates its widespread use. Several topics may be relevant for future research. First, BHA can be further improved by considering meta-heuristic algorithms. Second, BHA can be used to test more instances with larger scales and solve other sub-types of 2DRSPPs. Finally, the concept of available space, packing point, and the principle of BHA can be extended to solve 3D packing problems.

Footnotes

Abbreviations

Acknowledgments

The authors would like to express appreciation to the anonymous referees and the editor for their helpful comments. The authors would also like to thank Editage () for English language editing.

Availability of data and material

The data presented in this study are available on request from the corresponding author.

Authors’ contribution

Conceptualization: L.L.; methodology: L.L.; formal analysis and investigation: L.L. and Z.W.; resources: Z.W.; writing—original draft preparation: L.L.; writing—review and editing: L.L. and B.L.; supervision: B.L.; funding acquisition: B.L. All authors have read and agreed to this version of the manuscript.

Code availability

The computational codes are available at .

Declaration of conflicting interests

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Ethics approval

The authors certify that this manuscript is original and has not been published and will not be submitted elsewhere for publication while being considered by the journal. The study is not split up into several parts to increase the quantity of submissions and submitted to various journals or to one journal over time. No data have been fabricated or manipulated (including images) to support the conclusions. No data, text, or theories by others are presented as if they were our own.

Funding

The authors disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Natural Science Foundation of China, the Joint Fund of Henan Science and Technology Research and Development Plan, and the Science and Technology Project of Henan Province in China (grant numbers 12072106, 242103810064, 222103810085, 232103810085, and 242102220029).

Informed consent

This article does not contain any studies with human participants.

ORCID iD

Li Li

Research involving human participants and/or animals

This article does not contain any studies with human participants or animals performed by any of the authors.

Appendix: The solutions of BHA on all data sets

A more detailed description of all the data sets is available at https://github.com/18439870129/BHA/tree/master. Tables A1 to A6 give the detailed solutions of BHA on all data sets mentioned. BHA was run 10 times; No.1–No.10 signify the solutions for each run.

References

Lodi

Martello

Vigo

. Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems. INFORMS J Comput 1999; 11: 345–357.

Lodi

Martello

Monaci

. Two-dimensional packing problems: a survey. Eur J Oper Res 2002; 141: 241–252.

Bortfeldt

Wäscher

. Constraints in container loading: a state-of-the-art review. Eur J Oper Res 2013; 229: 1–20.

Erjavec

Gradišar

Trkman

. Renovation of the cutting stock process. Int J Prod Res 2009; 47: 3979–3996.

Beasley

. An exact two-dimensional non-guillotine cutting tree search procedure. Oper Res 1985; 33: 49–64.

Wäscher

Haußner

Schumann

. An improved typology of cutting and packing problems. Eur J Oper Res 2007; 183: 1109–1130.

Neuenfeldt Júnior

Silva

Francescatto

, et al. The rectangular two-dimensional strip packing problem real-life practical constraints: a bibliometric overview. Comput Oper Res 2022; 137: 1–19.

Iori

De Lima

Martello

, et al. Exact solution techniques for two-dimensional cutting and packing. Eur J Oper Res, 2021; 289: 399–415.

Oliveira

Gamboa

Silva

. An introduction to the two-dimensional rectangular cutting and packing problem. Int Trans Oper Res 2023; 30: 3238–3266.

10.

Oliveira

Neuenfeldt Júnior

Silva

, et al. A survey on heuristics for the two-dimensional rectangular strip packing problem. Pesquisa Operacional, 2016; 36: 197–226.

11.

Martello

Monaci

Vigo

. An exact approach to the strip-packing problem. INFORMS J Comput 2003; 15: 310–319.

12.

Kenmochi

Imamichi

Nonobe

, et al. Exact algorithms for the two-dimensional strip packing problem with and without rotations. Eur J Oper Res, 2009; 198: 73–83.

13.

Hopper

Turton

BCH

. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem. Eur J Oper Res 2001; 128: 34–57.

14.

Leung

SCH

Zhang

Zhou

, et al. A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem. Computers and Operations Research, 2012; 39: 64–73.

15.

Leung

SCH

Zhang

. A fast layer-based heuristic for non-guillotine strip packing. Expert Syst Appl 2011; 38: 13032–13042.

16.

Baker

Coffman

Rivest

. Orthogonal packings in two dimensions. SIAM J Comput 1980; 9: 846–855.

17.

Chazelle

. The bottom-left bin packing heuristic: an efficient implementation. IEEE Transaction on Computers 1983; 32: 697–707.

18.

Aşık

ÖB

Özcan

. Bidirectional best-fit heuristic for orthogonal rectangular strip packing. Ann Oper Res 2009; 172: 405–427.

19.

Özcan

Kai

Drake

. Bidirectional best-fit heuristic considering compound placement for two dimensional orthogonal rectangular strip packing. Expert Syst Appl 2013; 40: 4035–4043.

20.

Burke

Kendall

Whitwell

. A new placement heuristic for the orthogonal stock-cutting problem. Oper Res 2004; 52: 655–671.

21.

Wei

Qin

Cheang

, et al. An efficient intelligent search algorithm for the two-dimensional rectangular strip packing problem. Int Trans Oper Res, 2016; 23: 65–92.

22.

Yang

Han

. A simple randomized algorithm for two-dimensional strip packing. Computers and Operations Research 2013; 40: 1–8.

23.

Zhang

Kang

Deng

. A new heuristic recursive algorithm for the strip rectangular packing problem. Computers and Operations Research 2006; 33: 2209–2217.

24.

Huang

Chen

. A new heuristic algorithm for rectangle packing. Computers and Operations Research 2007; 34: 3270–3280.

25.

Alvarez-Valdes

Parreño

Tamarit

. Reactive GRASP for the strip packing problem. Computers and Operations Research 2008; 35: 1065–1083.

26.

Wei

Zhang

Chen

. A least wasted first heuristic algorithm for the rectangular packing problem. Computers and Operations Research 2009; 36: 1608–1614.

27.

Wang

Chen

. Two-dimensional residual-space-maximized packing. Expert Syst Appl 2015; 42: 3297–3305.

28.

Huang

Jin

. An efficient deterministic heuristic for two-dimensional rectangular packing. Computers Operations Research 2012; 39: 1355–1363.

29.

Jin

Huang

. Heuristics for two-dimensional strip packing problem with 90° rotations. Expert Syst Appl 2013; 40: 5542–5550.

30.

. Dynamic reduction heuristics for the rectangle packing area minimization problem. Eur J Oper Res 2015; 241: 674–685.

31.

Jakobs

. On genetic algorithms for the packing of polygons. Eur J Oper Res 1996; 88: 165–181.

32.

Liu

Teng

. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles. Eur J Oper Res 1999; 112: 413–420.

33.

Dowsland

Herbert

Kendall

, et al. Using tree search bounds to enhance a genetic algorithm approach to two rectangle packing problems. Eur J Oper Res, 2006; 168: 390–402.

34.

Bortfeldt

. A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces. Eur J Oper Res 2006; 172: 814–837.

35.

Burke

Kendall

Whitwell

. A simulated annealing enhancement of the best-fit heuristic for the orthogonal stock cutting problem. INFORMS J Comput 2009; 21: 505–516.

36.

Dagli

Poshyanonda

. New approaches to nesting rectangular patterns. J Intell Manuf 1997; 8: 177–190.

37.

Leung

Chan

Troutt

. Application of a mixed simulated annealing-genetic algorithm heuristic for the two-dimensional orthogonal packing problem. Eur J Oper Res 2003; 145: 530–542.

38.

Leung

SCH

Zhang

Sim

. A two-stage intelligent search algorithm for the two-dimensional strip packing problem. Eur J Oper Res 2011; 215: 57–69.

39.

Hifi

Negre

Ouafi

, et al. A parallel algorithm for constrained two-staged two-dimensional cutting problems. Computers and Industrial Engineering, 2012; 62: 177–189.

40.

Imahori

Yagiura

. The best-fit heuristic for the rectangular strip packing problem: an efficient implementation and the worst-case approximation ratio. Computers and Operations Research 2010; 37: 325–333.

41.

Wei

Leung

SCH

, et al. 2D strip packing problem and its efficient implementation. Computers and Operations Research 2017; 80: 113–127.

42.

Valenzuela

Wang

. Heuristics for large strip packing problems with guillotine patterns: an empirical study. Proceedings of the 4th metaheuristics international conference. University of Porto, Porto, Portugal, 2001, pp. 417–421.

43.

Wang

Valenzuela

. Data set generation for rectangular placement problems. Eur J Oper Res 2001; 134: 378–391.

44.

Iori

De Lima

VÃL

Martello

, et al. 2DPackLib: a two-dimensional cutting and packing library. Optimization Letters 2022; 16: 471–480.

45.

Pinto

Oliveira

. Algorithm based on graphs for the non-guillotinable two-dimensional packing problem. Second ESICUP Meeting, Southampton, 2005.

A backtracking heuristic algorithm for two-dimensional strip packing with rotation

Abstract

Keywords

Introduction

Related works

Backtracking heuristic algorithm

Definitions

Backtracking constructive heuristic algorithm

Constructive heuristic based on the fitness strategy

Backtracking constructive heuristic

Multi-start improvement

Randomized local search

Parameter setting

Effect of various m

Effect of various l s

Computational results

Computational results on zero-waste instances

Computational results on non-zero-waste instances

Computational results on large-scale instances

Effect of multi-start improvement

Conclusion

Footnotes

Abbreviations

Acknowledgments

Availability of data and material

Authors’ contribution

Code availability

Declaration of conflicting interests

Ethics approval

Funding

Informed consent

ORCID iD

Research involving human participants and/or animals

Appendix: The solutions of BHA on all data sets

References

Effect of various $m$

Effect of various $l s$