GRASP Optimization for the Strip Packing Problem with Flags, Waste Functions, and an Improved Restricted Candidate List

Abstract

This research addresses the two-dimensional strip packing problem to minimize the total strip height used, avoiding overlapping and placing objects outside the strip limits. This is an NP-hard optimization problem. We propose a greedy randomized adaptive search procedure (GRASP), incorporating flags as a new approach for this problem. These flags indicate available space after accommodating an object; they hold the available width and height for the following objects. We also propose three waste functions as surrogate objective functions for the GRASP candidate list and use and enhanced selection for the restricted candidate list, limiting the object options to better elements. Finally, we use overlapping functions to ensure that the object fits in the flag because there are some cases where a flag’s width can be wrong due to new object placement. The tests showed that our proposal outperforms the most recent state-of-the-art metaheuristic. Additionally, we make comparisons against two exact algorithms and another metaheuristic.

1. Introduction

The strip packing problem (SPP) is a two-dimensional industrial minimization problem. Given a strip of infinite length and bounded width, the problem is to define a packing of rectangular objects into a strip that minimizes its final length. The SPP is present in the industrial sector in material fabrics as paper, wood, glass, plastics, and metal, among others; its purpose is to reduce the amount of waste of the strip. Additionally, this problem is similar to the two-dimensional knapsack problem [1], where considered are the width and height of the objects in the knapsack. Furthermore, the variable cost and size of the bin packing problem [2] have some similarities regarding the variable size of the bin, which relates to the size of the strip. Nevertheless, there are also extensions to these problems, such as the three-dimensional bin packing problem [3].

The SPP is known as an NP-hard optimization problem [4]. Therefore, in real-world scenarios, the use of heuristic and metaheuristic algorithms is advised [5,6].

The greedy randomized adaptive search procedure (GRASP) is a constructive multi-start optimization algorithm with proven accuracy in NP-hard combinatorial optimization problems. In [7,8], the authors use a simple GRASP to solve the job–shop problem, minimizing the makespan while maximizing the workflow, and the orienteering problem with hotel selection, which look for a path with time limit and maximum score in a graph.

Other papers, such as [9], use a GRASP with a reduced candidate list to tackle the DNA sequence motif discovery.

Additionally, hybrid GRASP algorithms are common; e.g., in [10], Bruni et al. solve the k-traveling repairman problem with profits. In [11,12], Santiago et al. and Saad et al. tackle the precedence-constraint tasks scheduling using a GRASP hybridized with a cellular processing algorithm and a simulated annealing, respectively. Khamlichi et al. used another hybrid GRASP to solve the manufacturing planning [13] for demand fluctuations. Hence, we believe that GRASP is simple and has high hybridizable properties, making room for improvements.

1.1. Literature That Allows Object Rotation

The following is the most relevant literature regarding the strip parking problem. However, this subsection only contains papers that allow rotations, not considered in our research.

In 2004, Beltran et al. [14] implemented a hybrid algorithm using GRASP and VNS algorithm to solve the strip packing problem and consider guillotine cuts.

Later, in 2013, Silveira et al. [15] proposed a GRASP heuristic and a first-fit decreasing height technique with two approximation algorithms for the strip packing problem and the two-dimensional loading capacitated vehicle routing problem.

Gaticia et al. [16] presented, in 2016, an algorithm called strip packing problem game (SPPG) that uses real players, patterns, decision trees, data mining, and heuristics. Their proposed algorithm implemented a puzzle representing a strip packing instance to obtain solutions. The algorithm analyzes the player’s movements through data mining techniques and pattern recognition. Their experimental results showed that SPPG identifies game patterns from previous plays, obtaining adjustments of 87.03% for known instances and 88.2% for unknown instances.

In 2019, Chen et al. [17] presented a heuristic algorithm to the two-dimensional rectangular packing problem using anticipation strategy and step method. They aim to maximize the speed of the fill rate of the strip and improve adjustments in the construction procedure. The computational test concluded that their proposal is competitive against recent algorithms.

Finally, in 2020, Martin et al. approached the constrained two-dimensional guillotine placement problem (C2GPP) in [18]; this problem is similar to the one presented by Beltran et al. in [14], which considers guillotine cuts. Their objective is to use orthogonal cuts with constrained patterns to select an optimal set of large objects. The authors proposed a nonlinear integer function to obtain linear programming for nonlinear models and decision trees. The study concludes that models based on ascending storage lead to optimal or semi-optimal solutions with a reasonable computational cost.

1.2. Literature That Does Not Allow Object Rotation

Here, we show the most relevant literature regarding no object rotating strip parking problem.

In 2003, Martello et al. [19] implemented a branch and bound algorithm for the strip packing problem using instances up to two hundred objects. The computational results showed that they were able to solve 75% of the instances.

In 2008, Alvarez-Valdes et al. [20] implemented a reactive GRASP algorithm for the strip packing problem, improving their strategies and critical search options.

Later, in 2009, Alvarez-Valdes et al. [21] proposed a new branch and bound for the strip packing problem. They aim to reduce the tree search and generate better lower bounds.

Two years later, Leung et al. [22] presented a new approach named “two-stage intelligent search algorithm” for the strip packing problem. Their proposal consists of two stages; the scoring rule and the combination of simulated annealing algorithm with local search.

In 2016, Zhang et al. proposed an improved hybrid metaheuristic algorithm with variable neighborhood search that generates sets based on block pattern construction [23], called hybrid algorithm (HA), which has three phases. The first phase uses the least waste strategy, which consists of scoring rules to select the items that fit the least waste on the strip. The second phase selects a better sequence to improve the initial solution. Finally, the third phase constructs different neighborhoods based on block patterns. Their computational tests show that the HA algorithm surpasses other approaches from state of the art for hard instances of the strip packing problem and conclude that the HA algorithm is efficient in selecting neighborhoods dynamically.

Later, in 2019, Wei et al. [24] analyzed the SPP with unloading constraints, which consist of storing objects in a two-dimensional space for transport and unloading. Their objective was to minimize the total height and satisfy the discharge condition using segment trees, heuristics for open spaces, and random local search.

A year later, Rakotonirainy et al. [25] proposed two metaheuristics for the strip packing problem. The first consisted of a simulated annealing combined with a heuristic construction algorithm. The second implemented a simulated annealing in predefined packing layouts without encoding solutions. The authors used 1718 instances, and they concluded that their proposal improved its original version in terms of the quality of the solution.

Table 1. Differences between approaches.

Differences between Approaches
GRASPSPP (Our proposal)	Reactive GRASP [20]
Simple GRASP	Use of reactive GRASP
Use of flags	Use of best fit (BF)
Overlap functions	Evaluate and rearrange the solution
Height and width measurement functions	Use of floating accommodations
Avoid floating objects	-
New Branch and Bound [21]	Iterative Search [24]
Use of Branch and Bound	Use of first-fit
GRASP for improvements	Arrangement in open space
Evaluate and rearrange the solution	Change solutions
Floating objects	Use of random local search
Waste space validation	Combination of 2D-SPP and CVRP
Branch and Bound [19]	Two-stage ISA [22]
Use of Branch and Bound	Use of search algorithm
Available space by two points	GRASP makes improvements
Arrangements by constraints	Accommodations in six dynamic spaces
Height and width evaluation	Width measurement
Branches reduction by selection	-

shows the differences among the most relevant approaches, most of which will be used as a comparison.

2. Strip Packing Problem (SPP)

The strip packing problem is an NP-hard optimization problem commonly found in the industrial sector in materials such as paper, fabrics, wood, glass, plastics, and metal. Their purpose is to reduce the amount of waste in a strip, avoiding overlapping and placing objects outside the strip limits. This problem is defined using the following sets:

$$\begin{array}{c}\hfill O=\{o_1,o_2,\dots ,o_n\}\end{array}$$

(1)

$$\begin{array}{c}\hfill OW=\{o{w}_1,o{w}_2,\dots ,o{w}_n\}\end{array}$$

(2)

$$\begin{array}{c}\hfill OH=\{o{h}_1,o{h}_2,\dots ,o{h}_n\}\end{array}$$

(3)

where O is the set of rectangular objects; $OW$ is the set of object widths, and $OH$ is the set of heights.

For every $o_i$ their correspondent width and height are $o{w}_i$ and $o{h}_i$ respectively. The objective of the strip packing problem is to accommodate O into a delimited strip with a fixed width and infinite height, avoiding overlapping and aiming to reduce the total strip length used.

We implement a GRASP meta-heuristic algorithm to the strip packing problem, prioritizing the objects that generate less waste of area in the strip to minimize the height used.

One interesting element of our proposal is the use of flags. These flags are in the upper left and bottom right corners of an accommodated object. Additionally, they store the existing information in the strip, such as the widths and heights available for the next candidate.

On the other hand, we analyze the total height, waste area, the algorithm performance, and computational time. The impact of waste functions is also analyzed, and finally, functions that validate overlaps for objects are incorporated to determine if the current flag is disabled or updated.

3. GRASP Algorithm for SPP

The greedy randomized adaptive search procedure algorithm (GRASP) is a metaheuristic proposed by Feo et al. [26,27]. The GRASP algorithm is a multi-start process that has two phases. The first phase corresponds to a heuristic construction, which provides a high-quality solution, and the second phase improves the solution through a local search. However, given the nature of the solution, a slight change in the placement of the rectangular objects for an already-completed solution would produce a huge problem for repairing highly-possible overlaps or would increase wastes. Therefore, we avoid the use of local search, limiting the algorithm to the heuristic construction phase.

Algorithm 1 shows the general procedure of our proposed optimization method; it generates the solutions with a defined number of iterations. The process starts with the LoadInstance function that loads the instance. The InitializeParameters function initializes the main parameters to use in GRASP construction. The ReorderObjects function consists of ordering the objects from the smallest area to the largest area. The SPPGRASP function constructs the GRASP solutions; we validate the solutions to obtain the best solution. This code is available at https://github.com/csalas07/GraspSpp (accessed on 4 February 2022).

Algorithm 1 GRASP General Procedure

1: $Sol=⌀$, $best=\varnothing$ 2: LoadInstance() 3: InitializeParameters() 4: ReorderObjects() 5: for $i=1\to MaxIter$ do 6:   $Sol=SPPGRASP\left(\right)$ 7:   if $f\left(Sol\right)<best$ then 8:    $best=f\left(Sol\right)$ 9:   end if 10: end for

Output: best

3.1. GRASP Construction

One of the main contributions of this paper is the use of flags, and at the beginning of the algorithm, we set a single flag at the lowest left corner of the strip to mark the first place for setting an object.

Algorithm 2 describes the initial construction that consists of three parts. The first is to select an available flag index with the FindFlagIndex function (see line 4), which iterates a list of available flags and selects the index of the flag that has the lowest height, and if there were several flags with the same height, it chooses the one furthest to the left. The second part consist of the use of waste functions (see Equations (5)–(7)) to analyze the objects’ waste. Finally, the last part is constructing the candidate list (CL) and the restricted candidate list (RCL).

Algorithm 2 GRASP Construction Part 1

Input:k 1: $miss=\left|O\right|$ 2: while$miss>0$ do 3:   $CL=⌀$ 4:   $j=FindFlagIndex\left(Flags\right)$ 5:   for $i=0\to \left|O\right|$ do 6:    if $s_i=0$ && $o{w}_i\le tf{w}_j$ then 7:     $CL=CL\cup \left\{o_i\right\}$ 8:     $w{k}_{ij}=CalculateWaste\left(k\right)$ 9:     $W=W\cup \left\{w_{ij}\right\}$ 10:    end if 11:   end for 12:   if $CL\ne \varnothing$ then 13:    $kElems=max\left(\right|CL|\times 0.10,5)$ 14:    $RCL=⌀$ 15:    $RW=⌀$ 16:    for $i=1\to kElem$ do 17:     $imin={arg\; min}_{i}w{k}_{ij}\forall w{k}_{ij}\in W$ 18:     $RCL=RCL\cup \left\{o_{imin}\right\}$ 19:     $RW=RW\cup \left\{w{k}_{imin}\right\}$ 20:     $W=W\setminus \left\{w{k}_{imin}\right\}$ 21:    end for 22:    $Limit=max\left(W\right)+(\beta \times (max\left(W\right)-min\left(W\right)\left)\right)$ 23:    for $i=1\to \left|RCL\right|$ do 24:     if $w{k}_{ij}\in RW>Limit$ then 25:      $RW=RW\setminus \left\{w{k}_{ij}\right\}$ 26:      $RCL=RCL\setminus \left\{o_i\right\}$ 27:     end if 28:    end for 29:    $O_r=Roulette(RCL,RW)$

The algorithm checks that the set value $s_i$ is equal to zero, where $S=\{s_1,s_2,\dots ,s_n\}$ is a set that represents the availability of the objects (see Equation (4)).

$$\begin{array}{ccc}\hfill s_i& =& \left\{\begin{array}{c}1\mathrm{The} \mathrm{object} \mathrm{is} \mathrm{set} \mathrm{in} \mathrm{the} \mathrm{strip}\hfill \\ 0\mathrm{Otherwise}\hfill \end{array}\right.\hfill \end{array}$$

(4)

The $CalculateWaste\left(k\right)$ function calculates the waste area of an object $w{k}_{ij}$ (see line 8). We use three waste functions (see Equations (5)–(7)) to analyze the objects’ waste. Each function validates different components among the rectangular objects and a specific flag.

$$w_{ij}^1=min\left(\right|df{w}_j-o{w}_i|,|tf{w}_j-o{w}_i\left|\right)+min\left(\right|lf{h}_j-o{h}_i|,|rf{h}_j-o{h}_i\left|\right)$$

(5)

$$w_{ij}^2=min\left(\right|lf{h}_j-o{h}_i|,|rf{h}_j-o{h}_i\left|\right)$$

(6)

$$\begin{array}{c}{w}_{ij}^3=\left(min\right(|df{w}_j-o{w}_i|,|tf{w}_j-o{w}_i\left|\right)\times max(oh,min(lf{h}_j,rf{h}_j))+\hfill \\ \hfill \left(min\right(|lf{h}_j-o{h}_i|,|rf{h}_j-o{h}_i\left|\right)\times o{w}_i)\end{array}$$

(7)

where $O=\{o_1,o_2,\dots ,o_n\}$ is the set of objects and $w{k}_{ij}$ is the waste of the object i on the flag j. Hence, in the algorithm, we calculate the waste for all the available objects $o_i$ for the selected flag $f_j$. Figure 1 shows the characteristics of the flags and the objects, i.e., $df{w}_j$ and $tf{w}_j$ are the flag’s desirable and total width, respectively; $lf{h}_j$ and $rf{h}_j$ are the height to the left and to the right of the flag. Finally, $SP$ is the starting point and $o{w}_i$ and $o{h}_i$ are the current object width and height, respectively.

The selection of the first object is the one with the largest area. We select the rest of the elements according to the waste area function which is similar in some sense to the feature selection used in [28]; the $WA$ value stores all waste area values for each object for a specific flag. Additionally, we validate that $CL\ne \varnothing$ in line 12. Therefore, if no object fits in the space of the flag, then we try to raise the flag (see line 35 of Algorithm 3).

Algorithm 3 GRASP Construction Part 2

30:    if $NoObjectOverlapping\left(\right)$ then 31:     $FixFlagOverlapping\left(\right)$ 32:     $Set(O_r,j)$ 33:    end if 34:   else 35:    $RiseFlag\left(\right)$ 36:   end if 37: end while

Later, Equation (8) calculates a limit value, which will be compared with the waste areas of the candidate objects to create the restricted candidate list ($RCL$).

$$Limit=max\left(WA\right)+(\beta \times (max\left(WA\right)-min\left(WA\right)\left)\right)$$

(8)

where $\beta$ is a real number between 0 and 1; we made several tests to identify the best value, but we could not find it; hence, we chose to use random values between 0.4 and 0.5, which were the values with the best performance.. Additionally, the objects have a wide variety of sizes and, therefore, wastes, meaning that there might be lower or higher differences among the wastes. Hence, we could end up without candidates or with a lot of them, nullifying the purpose of the restricted candidate list.

Therefore, the candidate list selects $kElems$, which are either five elements or 10% of the objects in $CL$ until exhaust $CL$ (see line 13). As a result, the algorithm initializes the restricted candidate list with the elements in $CL$ with the lowest waste.

Line 17 obtains the index of the object for which the waste $w{k}_{ij}$ is minimal. Then, we update the restricted candidate list ($RCL$) and the restricted waste list ($RW$), respectively (see lines 18, and 19). Finally, the procedure removes $w{k}_{imin}$ from W (see line 20).

The algorithm calculates the $Limit$ value to further restrict the $RCL$ to those wastes that have a lower or equal value than $Limit$ (see line 22). Therefore, the algorithm updates $RW$ and $RCL$ in lines 25 and 26, respectively.

The procedure selects an object $O_r$ in $RCL$ randomly with a roulette technique [29] (see line 29); for further explanation see Section 3.2.

3.2. Roulette Procedure

Algorithm 4 describes the selection process using the roulette. The roulette assigns larger probabilities to the elements in $RCL$ with lower waste.

Algorithm 4 General Roulette Procedure

Input:$RCL$, $RW$ 1: $R{W}^{\prime }=\left\{w{k}_{ij}^{\prime }\right|w{k}_{ij}^{\prime }=max\left(RW\right)+min\left(RW\right)-w{k}_{ij},\forall w{k}_{ij}\in RW\}$ 2: $t={\sum }_{w{k}_{ij}^{\prime }\in W{K}^{\prime }}\left(w{k}_{ij}^{\prime }\right)$ 3: $p=Random(1,t)$ 4: for$\forall w{k}_{ij}^{\prime }\in R{W}^{\prime }$do 5:   $p=p-w{k}_{ij}^{\prime }$ 6:   if $p\le 0$ then 7:    return $(o_i\in RCL)$ 8:   end if 9: end for

The procedure starts obtaining the maximum and minimum waste values from $RW$ transforming high values of $w{k}_{ij}$ to lower values of $w{k}_{ij}^{\prime }$ and vice versa (see line 1 of Algorithm 4). Additionally, t stores the total sum of $R{W}^{\prime }$ and p obtains a random value between 1 and t in lines 2 and 3, respectively.

Finally, the procedure iterates the converted values in $R{W}^{\prime }$ and subtracts $w{k}_{ij}^{\prime }$ from p; see lines 4 and 5. The process ends when the p value is less than or equal to zero and returns the selected object $o_i$ in lines 6 and 7.

3.3. Object Arrangement

Once we have the selected object $o_r$, we try to accommodate it in $f_j$. However, first, we need to check for overlapping of the current object $o_r$ regarding other objects in the strip. If there is any overlapping, then we update the data of the current flag and restart the selection of the object (see line 30). There is another possible overlapping, which occurs between the object $o_r$ and another flag $f_k$; if this happens, we merge the information of $f_j$ and $f_k$ together and proceed to accommodate the object $o_r$ in $f_j$ (see lines 31 and 32, respectively).

Once $o_r$ is placed in the strip, we create two new flags at the upper left and the lower right corners of the object (see Figure 2).

3.4. Overlapping among Objects

Figure 3 shows the idea of the overlaps detection among rectangles. The function validates that the current rectangular object does not cover an active rectangular object in the strip (see line 30 in Algorithm 3).

Here, when the algorithm created $f_j$, it also set $tf{w}_j$ before the object to the right was there. Therefore, it contains wrong information. Hence, we check for collisions of $o_i$ with the objects in the strip.

3.5. Overlaps between Rectangles and Flags

Figure 4 shows the overlaps between objects and flags. The function validates that the current rectangular object $o_i$ does not cover the nearest flag space $f_k$. In case of overlapping, the process updates the current flag $f_j$, merging the information with $f_k$ and finally deleting it.

3.6. Rise Flag

Figure 5 and Figure 6 present the rise flag concept. The procedure expands the total width to the right and changes the height of the flag, allowing the algorithm to improve the management of the space, avoiding larger empty spaces (see line 35 in Algorithm 3).

The rise flag function changes the current flag information when no available object fits in the current flag. There are two possible cases for this function. The first case happens when the left height is lower than the right height; if this happens, then the flag is deleted. However, for the second case, if the right height is lower than the left height, we merge both flags $f_j=f_j+f_k$.

4. Experimental Results

This section presents the experimental results from the proposed optimization method called GRASPSPP, which includes a comparison among the waste functions and four state-of-the-art papers, using nonparametric tests.

4.1. Configuration and Instances

The algorithm runs computational tests on a computer with 2.50 GHz with 8 GB of RAM, Windows 7, and the Microsoft Visual Studio platform with C++ as the programming language.

Table 2. Used instances.

Name	Autor	Total	n
2lcvrp	Gendreau [30]	180	15–255
Chr/cgcut	Christofides & Whitlock [31]	3	10–70
Brk/N1-13	Burke [32]	13	10–500
Ben/beng	Bengtsson [33]	10	20–200
Htu/ht	Hopper and Turton [34]	114	16–28
Hop	Hopper and Turton [35]	350	17–199
Bea/gcut-ngcut	Beasley [36,37]	25	10–22
Class 1–4	Martello and Vigo [19]	200	20–100
Class 5–10	Berkey and Wang [38]	300	20–100
50cx–15,000cx	Pinto and Oliveira [39]	6	50–15,000
P1	Ramesh Babu [40]	1	1000

shows the data of the instances used, where the first column shows the instance name, the second column shows the author’s name, and the third and fourth columns show the total of the instances and their sizes. The instances are available at https://mega.nz/folder/9slymA7b#kUSGqJGcfGszPDxF7a5sJg (accessed on 4 February 2022).

4.2. Waste Comparison

In this section, we present the comparison among the three waste functions regarding quality and time. The waste functions detect the amount of wasted space of any object. For the computational test, the algorithm uses three waste functions. We evaluate the performance and efficiency to determine the best waste function using the Friedman and the Wilcoxon tests. The waste functions are $w_{ij}^1$, $w_{ij}^2$, and $w_{ij}^3$ (see Equations (5)–(7)).

Figure 7 describes the quality result obtained from the different waste area functions. This comparison indicates that waste function $w_{ij}^1$ obtains lower heights than $w_{ij}^2$, and $w_{ij}^3$. However, $w_{ij}^3$ obtains lower heights than $w_{ij}^2$.

A Friedman test showed that $w_{ij}^1$ is the best-ranked waste function, followed by $w_{ij}^3$, and $w_{ij}^2$ in last place. Additionally, it shows that there is a statistically significant difference among them. Finally, the Wilcoxon test indicates that waste function $w_{ij}^1$ has statistically better quality than $w_{ij}^3$ and $w_{ij}^2$.

Regarding efficiency, most of the tests showed a computing time close to one second, which is not suitable for graphics. Here, the waste function $w_{ij}^3$ showed the lowest times. A Friedman test confirmed that the best ranked waste function is $w_{ij}^3$, followed by $w_{ij}^1$, and $w_{ij}^2$ in the last place. Finally, the Wilcoxon test indicated that there is no statistical difference between $w_{ij}^1$ and $w_{ij}^3$. However, there is a significant difference between $w_{ij}^1$ and $w_{ij}^2$. Therefore, $w_{ij}^1$ produces solutions with low computational times and the highest quality. On the other hand, $w_{ij}^2$ produces solutions with high computational times and low quality. Therefore, our proposed algorithm uses the waste function $w_{ij}^1$ for the rest of the computational test.

4.3. Comparison between GRASPSPP and Iterative Search Algorithm

In this section, we compare the results between the GRASPSPP algorithm and the iterative search (IS) algorithm presented in 2019 [24] by Wei et al. The authors performed 20 independent runs at 1000 iterations; thus, we configured our computational experimentation with the same runs and iterations.

Figure 8 shows the comparison of the average errors (errAvg) for the 20 runs for each instance set, for which we also calculated the average and standard deviation among all the sets of instances for the GRASPSPP (1.13 average, 0.06 standard deviation) and IS (1.12 average, 0.02 standard deviation). These errAvg are the average of the minimum error and the maximum error:

$$errAvg=\frac{minError+maxError}{2}$$

(9)

and the error is calculated as follows:

$$error=\frac{obtainedHeight}{bestHeight}$$

(10)

Additionally, this figure shows that GRASPSPP outperforms IS in six instances, and IS outperforms GRASPSPP in one instance. The Wilcoxon test result showed that GRASPSPP and IS produce statistically equivalent solutions with a significance value of 0.233.

Figure 9 shows the computational times between the GRASPSPP (2.70 average, 2.07 standard deviation) and IS (17.77 average, 9.51 standard deviation) algorithms. Here, the computational times are the average of the computational time of the 20 runs per set of instances. In all cases, the IS algorithm obtains higher computational times than GRASPSPP. Additionally, the Wilcoxon test result showed that GRASPSPP statistically outperforms IS with a 98.2% certainty.

4.4. Comparison between GRASPSPP and Branch and Bound Algorithm

This section shows the comparison between GRASPSPP and a Branch and Bound algorithm (B&B) presented in 2003 [19] by Martello et al, where the authors executed their approach with a time limit of one hour and reported the time in which they found their best result. For this comparison, we executed the GRASPSPP algorithm with a time limit of 5 min in an attempt to produce an equivalent computational effort because our processor is an Intel Core i5 at 2.50 Ghz, which outperforms the authors’ Pentium III at 800 Mhz processor.

Figure 10 shows the percentage error (see Equation (11)) comparison between GRASPSPP (2.62 average, 7.17 standard deviation) and B&B (0.97 average, 1.79 standard deviation). We obtain the %error as follows:

$$\%error=(100\times (obtainedHeight-bestHeight\left)\right)/bestHeight$$

(11)

Here, GRASPSPP outperformed B&B in eight instances; while B&B outperformed GRASPSPP in 11 instances. Among those 11 instances, three of them presented an extremely high %error in GRASPSPP; therefore, we require further analysis of the properties of those instances to identify the cause and implement corrections; those instances were ht4, ht7, and ht9. Additionally, the Wilcoxon test showed that the GRASPSPP and B&B are statistically equivalent.

Figure 11 shows the computational time comparison between GRASPSPP (0.000 average, 0.001 standard deviation) and B&B (1116.30 average, 1632.09 standard deviation). These values are the computational times of each instance set. Here, the B&B algorithm presents some instances with the highest possible values, because they reached the time limit of 3600 s. On the other hand, the proposal processes the instances with times closer to one second.

A visual comparison shows that the GRASPSPP algorithm is faster than B&B. Additionally, the Wilcoxon test corroborates that the GRASPSPP outperforms B&B statistically with a p-value of 0.001.

4.5. Comparison beteween GRASPSPP and a New Branch & Bound Algorithm

This section compares the experimental results between GRASPSPP and a new branch and bound algorithm (NB&B) proposed by Alvarez et al. in 2009 [21], where the authors executed their approach with a time limit of 1200 s. For this comparison, we executed our GRASPSPP algorithm with a time limit of 150 s to produce equivalent results because our processor is an Intel Core i5 at 2.50 Ghz, which outperforms the authors’ Pentium 4 at 2 Ghz processor.

Figure 12 shows the percentage error comparison (see Equation (11)) values between GRASPSPP (6.43 average, 7.13 standard deviation) and NB&B (1.37 average, 1.72 standard deviation) algorithm. Here, we can see that the NB&B algorithm outperforms GRASPSPP in most cases. However, GRASPSPP achieved a tie in 18 instances and won over NB&B in five instances. Finally, the Wilcoxon test showed that the NB&B statistically outperforms GRASPSPP with a p-value of 0.000.

Figure 13 shows the computational time comparison between GRASPSPP (0.42 average, 1.67 standard deviation) and NB&B (19.33 average, 51.20 standard deviation) algorithm. These values are the computational times of each instance set. Here, the NB&B algorithm reached the time limit of 1200 s, or even exceeded it, for five instances. On the other hand, GRASPSPP produced times near 1 s for most cases. Finally, the Wilcoxon test shows that the GRASPSPP algorithm outperforms NB&B with a p-value of 0.000.

4.6. Comparison between GRASPSPP and Reactive GRASP Algorithm

This section shows the comparison results between the GRASPSPP and reactive GRASP algorithm proposed by Alvarez et al. in 2008 [20]. The comparisons only have the best height and average values because the author prioritizes the results of the instances and not the computational times. Therefore, we cannot guarantee a fair equivalence regarding quality and efficiency; hence, we included these comparisons merely as a complement using a time limit of 60 s.

Figure 14 shows the percentage error (see Equation (11)) comparison between GRASPSPP (0.03 average, 0.01 standard deviation) and reactive GRASP (0.84 average, 0.57 standard deviation) algorithm from instance C1–C7 from the set Htu/ht (see Table 2. The reactive GRASP produces, in general, high average errors. The Wilcoxon test shows that the GRASPSPP algorithm outperforms statistically the reactive GRASP with a p-value of 0.046.

Figure 15 and Figure 16 shows the comparison of best values between the GRASPSPP (958.94 average, 1847.64 standard deviation) and reactive GRASP (948.59 average, 1786.24 standard deviation) algorithms. It is important to highlight that the author does not provide the rest of the average errors for these instances. Instead, they choose to use the best value, and, according to Figure 14, we believe that their algorithm produces solutions with a high variance.

As we can see, the differences between both algorithms are minimal except for a handful of instances.

The Wilcoxon test shows that the reactive GRASP has statistically better performance than GRASPSPP with a p-value of 0.000.

5. Conclusions

In this paper, we tackle the strip packing problem, which is NP-hard [4]. For this problem, we proposed a GRASP algorithm with flags, three waste functions, and an improved selection of the restricted candidate list ($RCL$). Additionally, we carried out an extensive experimentation with state-of-the-art algorithms and datasets.

The GRASP algorithm processes the instance with a new approach through flags, which indicate ideal available spaces for new objects. However, there are some cases where old flags keep outdated information; therefore, we check for collisions for every object.

Additionally, we proposed three waste functions that help to identify the possible wasted space for each object in the candidate list. These waste functions consider different measures. Among them, the best waste function is $w_{ij}^1$, which considers the minimum distance of the object width regarding the flag desired and total width, plus the minimum distance of the object height regarding the left and right flag height. The other two waste functions consider the vertical waste and the total area waste.

Regarding the improved selection of the restricted candidate list, we noticed that using the limit in the restricted candidate list was not enough to prevent the algorithm from using bad objects for any specific flag. Therefore, we selected a subset of the candidate list with the best waste to enhance the selection process of the restricted candidate list. This improvement was carried out and tested before the rest of the tests, and it significantly enhanced the performance of GRASPSPP.

The computational tests showed that GRASPSPP outperformed the most recent state of the art metaheuristic (IS) regarding quality and efficiency. However, GRASPSPP outperformed the two exact B&B algorithms regarding efficiency, while achieving equivalent performance regarding quality with the first exact algorithm (B&B). Finally, the last metaheuristic (reactive GRASP) outperformed GRASPSPP regarding quality; however, the authors did not report computational time. Nevertheless, GRASPSPP outperformed this metaheuristic regarding average errors.

As future work, we will consider analyzing the characteristics of some instances that produced a high percentage of error for further improvement. Additionally, we consider that an object permutation can code this problem, placing the objects according to the flag at the bottom and further to the left.