1 Introduction

This article deals with the rectangular strip packing problem (SPP) in two and three dimensions, respectively. In the 3D-SPP a set of rectangular items (boxes) and a container with fixed width and height but variable length are given. A feasible arrangement of all boxes within the container has to be determined so that the required length is minimised. The 2D-SPP is analogously defined. Note that the 2D-SPP can be perceived as a 3D-SPP in which all boxes have a minimum dimension of one length unit while the container height also equals one.

An arrangement is called feasible if no items overlap and all boxes are placed completely within the container and parallel to the container walls. There are no further restrictions imposed for the item stock, so the stock may be homogeneous (one single type of boxes), weakly heterogeneous (a few box types, many boxes per type) or strongly heterogeneous (many box types, a few boxes per type). The items of a box type represent congruent parallelepipeds.

According to the typology of cutting and packing problems (C&P) by Wäscher et al. (2007) the SPP considered here is referred to as open dimension problem (ODP), or more precisely as 3D (or 2D) rectangular open dimension problem with one variable dimension.

The 3D-SPP and the 2D-SPP occur in different industries and in many practical cutting and packing scenarios. In the steel industry, one common problem is to cut small three-dimensional blocks that belong to one customer order out of a larger steel block. Often the profile of the large block is fixed, while its length is variable. Customers usually order identical sets of pieces repeatedly. In such a situation, a good planning of the cutting process is important in order to limit the length of the large block and so to minimize the trim loss. Similar 2D cutting problems can be found in the glass- and paper industry, in which rectangles of known dimensions are to be cut out of a strip with a given width, but variable length.

The following packing problem is in fact also an SPP. Modern attached freight systems aim at a better capacity utilization of trucks. Such a system collects orders of different senders for trucks of different carriers. An order can only be assigned to a truck of sufficient residual capacity determined by the residual free length. Thus, before the assignment, the system calculates the minimum additional length required by a given consignment. Similar algorithms can improve the design of containers, or can even help the selection of vehicles in a vehicle fleet for transporting a given volume of goods.

In practical cutting and packing applications a wide variety of constraints can be observed (cf. Bischoff and Ratcliff 1995). Here, the following three constraints are considered:

  1. (C1)

    Orientation constraint: For a defined subset of the item stock the permitted orientation variants are restricted. For each box up to five of the original six possible spatial orientation variants can be ruled out in the 3D case while in the 2D case one of the two possible orientations may be prohibited.

  2. (C2)

    Guillotine cutting constraint: It requires that all items of a packing arrangement can be reproduced by guillotine cuts, i.e. by wall-to-wall cuts that run parallel to the walls of the container.

  3. (C3)

    Support constraint: The bottom area of each packed box that is not placed on the container floor must be supported completely (i.e. 100%) by other boxes.

The first two constraints play an important role in two-dimensional and three-dimensional C&P applications (cf., e.g., Lodi et al. 1999). In particular the guillotine cutting constraint is often enforced in cutting processes by the available equipment (saws etc.). The support constraint is an important stability condition in 3D (but not in 2D) packing applications to prevent boxes from tilting.

In this article we propose a tree search algorithm (TRSA) for solving the 3D-SPP and the 2D-SPP. The TRSA results by a straightforward adaptation of a tree search algorithm for the 3D container loading problem (CLP) that was proposed by Fanslau and Bortfeldt (2010). Note that in the 3D-CLP (considered here) a box set and one container with fixed dimensions are given and the aim is to maximize the volume (or value) of the packed boxes while generally not all given boxes can be packed. The TRSA generates guillotine patterns throughout, i.e. constraint (C2) is always observed. Both of the other constraints introduced above are satisfied if necessary. The main issue to be investigated is whether the high performance of the integrated CLP method is transferred to the SPP method. The TRSA will be subjected to a comparison with other recently published SPP solution procedures and it will turn out that the TRSA is able to generate top-quality solutions in reasonable running times particularly in the 3D case.

The rest of the article is organized as follows. First, in Sect. 2 we give a literature overview concerning the SPP in three and two dimensions. In Sect. 3 the SPP algorithm is described including an outline of the underlying CLP algorithm as well as its adaptation to the strip packing problem. In Sect. 4 we compare the proposed SPP method to other algorithms from literature by numerical experiments while some conclusions are drawn in Sect. 5.

2 Literature review

The SPP is NP-hard (cf. Hopper and Turton 2001). Exact algorithms for the 2D-SPP were proposed by Martello et al. (2003), Lesh et al. (2004), Bekrar et al. (2007), Bekrar and Kacem (2009) and Kenmochi et al. (2009). A general framework for exactly solving multi-dimensional packing problems was developed by Fekete and Schepers (1997) (see also Fekete et al. 2007). At the present time only smaller SPP instances can be solved exactly; typical sizes of exactly solved 2D instances range up to 50 items. Hence, heuristic approaches (that do not guarantee optimal solutions) are indispensable for solving large SPP instances in the 2D and even more in the 3D case.

For the 2D-SPP a wide variety of heuristic solution methods has been proposed in recent years. The interested reader is referred to Hopper and Turton (2000, 2001) and to Riff et al. (2009) for a comprehensive survey. We can distinguish four 2D-SPP subtypes (variants) regarding the constraints (C1) and (C2) that are tackled by 2D-SPP algorithms (cf. Lodi et al. 1999):

  • OF: orientation of all pieces is fixed (O) and guillotine cutting is not required (F);

  • RF: pieces may be rotated by 90∘(R) and guillotine cutting is not required (F);

  • OG: orientation of all pieces is fixed (O) and guillotine cutting is required (G);

  • RG: pieces may be rotated by 90∘(R) and guillotine cutting is required (G).

Note that a feasible solution with regard to subtype OG is also feasible regarding the other subtypes while a feasible solution with regard to subtype RG and OF, respectively, is also feasible in terms of subtype RF. In Table 1 a representative sample of heuristic 2D-SPP algorithms is presented. The sample is focused on the 2D-SPP with guillotine cutting constraint but recent and most relevant papers regarding subtypes OF and RF are also considered. For each contribution author(s) and year, relevant subtype(s), type of solution approach and additional features of the algorithm are listed.

Table 1 Heuristic algorithms for the 2D-SPP (sample)
Full size table

The subtypes without guillotine cutting constraint (OF, RF) draw much more attention than the other subtypes (OG, RG). This becomes even clearer if the above mentioned survey articles are consulted. Most of the algorithms apply metaheuristic search strategies like genetic algorithms or simulated annealing. At the moment, the solution methods proposed by Alvarez-Valdes et al. (2008), Belov et al. (2008) and Burke et al. (2009) belong to the most powerful approaches for the 2D-SPP without guillotine cutting constraint (OF, RF) while the genetic algorithm by Bortfeldt (2006) and the branch and bound method by Cui et al. (2008) achieved the best results so far for the guillotine cutting subtypes OG and RG. It is noticeable that three of these five algorithms are based on widely used metaheuristic strategies (cf. Table 1). On the other hand, it turned out that straightforward constructive heuristics are of great value in the design of high-performance solution methods and often successful 2D-SPP methods are built around those placement heuristics (see Table 1, rightmost column). Clearly, the well-known Bottom Left (BL) heuristic (cf. Baker et al. 1980) can be regarded as the prototype of such placement heuristics.

In contrast to the 2D-SPP, only few algorithms have been developed for solving the 3D-SPP so far and almost all of them are listed in Table 2. Table 2 is similarly built as Table 1 but column 2 indicates now whether the methods are able to observe the support constraint (C3).

Table 2 Heuristic algorithms for the 3D-SPP (for acronyms see Table 1)
Full size table

Again, some metaheuristic methods include straightforward constructive heuristics. On the other hand, algorithms for the 3D-SPP are often based on existing algorithms for the 3D-CLP (e.g., see Table 2, branch and bound method of Bortfeldt and Mack 2007).

3 The strip packing algorithm

In the following, the tree search algorithm, referred to as SPTRS (Strip Packing by Tree Search), is introduced in two steps. At first the frame procedure of SPTRS is explained, afterwards the integrated CLP method is described.

3.1 The overall algorithm

The overall algorithm of method SPTRS is shown in Fig. 1. The main idea is to solve a given SPP instance by solving a series of CLP instances by means of a CLP algorithm. The box set, the container width wC and the container height hC of all CLP instances are given by the SPP instance. Starting with a sufficiently large value (see below) the container length lC is reduced from instance to instance. The solving of CLP instances will only be finished after no SPP solution has been returned for the first time. A solution of a CLP instance is called an SPP solution if and only if all given boxes were packed.

Fig. 1
figure 1

Overall algorithm of method SPTRS

Full size image

Each time an SPP solution for a CLP instance with container length lC has been calculated, the so-called used container length lCUsed (lCUsed≤lC), given by the maximum coordinate of a box in length direction, is determined. In the next CLP instance the container length is then set lC:=lCUsed−1. In this way it is ensured that a new SPP solution is always better than the previous one. Finally, the last (i.e. best) found SPP solution is output.

The initially chosen container length should meet two different demands. On the one hand, it has to be chosen so that an SPP solution (including all given boxes) can be generated in any case. On the other hand, the initial container length should be not too large in order to save computational effort that is caused by a long series of solved CLP instances. Both the demands are satisfied as follows.

First, the initial container length is calculated as product of the continuous (or material) lower bound lClB of the required container length and a factor greater than one. The lower bound is determined as lClB:=⌈(total box volume)/(wC ∗ hC)⌉ (⌈a⌉ is the smallest integer not smaller than a). The factor is given as quotient 100/minspp_fillrate wherein the parameter minspp_ fillrate stands for the expected minimum filling rate of the container volume (in %). With a suitable value of minspp_ fillrate, e.g. 90%, a very large initial container length can be avoided. Hence, an attempt is made to solve the related CLP instance.

Only if this attempt fails, a second greater initial container length lC is tried. This time lC is set to the sum of the minimum dimensions in length direction of all boxes (this sum is denoted as high_value in Fig. 1). The minimum dimension of a box in length direction is determined considering the container dimensions as well as the orientation constraint (C1). Clearly, the CLP with length high_value has an SPP solution in any case, formed by a sequence of all boxes in length direction, so that the first requirement is also met. Hence, an initial SPP solution with a related length lCUsed is available in any case.

Note that the computation is (also) finished if the used container length lCUsed of the last found SPP solution reaches the lower bound lClB (not shown in Fig. 1).

3.2 The integrated CLP algorithm

To solve the CLP instances the tree search algorithm CLTRS (Container Loading by Tree Search) by Fanslau and Bortfeldt (2010) is used. CLTRS generates guillotine packing patterns throughout, i.e. constraint (C2) is always satisfied, while orientation and support constraint (C1) and (C3), respectively, are optionally observed. Below we give an extended outline of algorithm CLTRS; for a comprehensive description we refer the reader to Fanslau and Bortfeldt (2010).

Algorithm CLTRS is based on the so-called block building approach. Instead of filling the container by single boxes it is packed by blocks of several boxes without or only with small gaps. Compared to older block building algorithms, CLTRS does not only use loss-free blocks consisting of boxes of the same box type which are arranged in the same spatial orientation (so-called simple blocks). Instead the block concept is extended in that also general blocks are allowed that comprise boxes of different types or have congruent boxes with different spatial orientations. A general block may have gaps (cf. Fig. 2). However, the minimum volume utilization of a block (regarding the enveloping cuboid) is stipulated by a parameter that is usually set to a high value, e.g. 98%. General blocks are mainly beneficial for strongly heterogeneous problem instances.

Fig. 2
figure 2

A simple block and a general block (top view, 2D case)

Full size image

The overall algorithm of CLTRS is shown in Fig. 3. The search is organized in two stages. In the first stage only simple blocks are used while in the second stage general blocks are allowed. At the beginning of each stage an appropriate list of oriented blocks, that serve to fill the container, is generated in advance. Each stage has a specific time limit. The best packing plan over both stages is output at the end. Using the two stages can be considered a means to diversify the search.

Fig. 3
figure 3

Overall algorithm of method CLTRS

Full size image

In each stage a series of complete solutions (packing plans) is generated. The admitted search effort per solution is controlled by an internal parameter search_effort that is doubled from solution to solution. Hence, better and better solutions can be found within a search stage. A solution is constructed block by block and each block fills a residual space, i.e. an empty block-shaped space of defined size and position inside the container. The residual spaces are collected in a stack that is initially filled by the container itself, i.e. the interior space of the container is the first residual space to be processed. To process the current residual space, namely the uppermost residual space in the stack, the most appropriate block is selected from the block list and then placed in the residual space’s lower corner nearest to the origin of the used coordinate system. Afterwards the rest of the space is orthogonally cut resulting in up to three new residual spaces that are again inserted into the stack. Heuristic rules for cutting (filled) and inserting (new) residual spaces aim at preventing waste, i.e. no longer usable space in the container. If a block has been specified and placed, this decision is not revised when further blocks are determined.

Determining the best block for the current residual space forms the kernel operation of a search stage and is based on the following principle. Let an incomplete solution s 0 including n 0 (n 0≥0) placed blocks be given. To find a block for the uppermost residual space rstop of the residual space stack, starting from s 0, i.e. retaining the n 0 blocks already placed, different complete solutions are generated experimentally. The (n 0+1)th block of all temporarily-generated solutions fills the (same) residual space rstop that results by the previously added blocks. The (n 0+1)th block of the complete temporary solution with maximal packed volume is then returned as the best block for rstop.

Each of the complete solutions results by a separate tree search (called partition search) that is itself composed by several basic search phases (cf. Fig. 4). The basic search phases are chained as the incomplete solution s j that is output by the jth basic search phase is taken as input solution by the (j+1)th phase. Of course, the input solution of the first basic search phase is the original incomplete solution s 0. Each basic search phase adds d j (d j ≥1) blocks to its input solution (j=1,…,l). Only the last basic search phase provides a complete solution.

Fig. 4
figure 4

A partition search and its basic search phases

Full size image

In the jth basic search phase a tree is constructed in which the input solution s j−1 and the related state data (residual space stack, set of unpacked boxes) form the root node. The tree is defined by two parameters, namely the depth d j (d j ≥1) and the number of successor nodes ns j . Starting with the root, ns j successor nodes are constructed per node (search state) by filling the respective uppermost residual space alternately with the largest blocks (in terms of volume) that fit into the space and consist of still unpacked boxes. Since d j blocks are to be added the tree will have a depth of d j +1 and generally each extended solution will have n j−1+d j blocks if the input solution consists of n j−1 blocks.

The extended solutions are generally still incomplete and to determine the best extended solution of the jth basic search phase all extended solutions are completed by the so-called greedy completion. Given an incomplete solution s′ the greedy completion packs repeatedly the largest possible block into the respective uppermost residual space until no further block can be packed, i.e. a complete solution s″ is reached. Now the output solution of the jth basic search phase is determined as the extended solution s′ of (generally) n j−1+d j blocks that yields the best complete solution s″ with maximum packed volume. Only in the last basic search phase the best completed solution s″ is returned instead of the related incomplete solution s’ (see Fig. 4).

The number of successor nodes ns in a basic search phase is determined as a function of the depth d so that a greater depth d corresponds to a smaller successor number ns and vice versa. In Fig. 5 two possible trees of a basic search phase are shown. While in the first tree of depth d=2 the number of successors per node is ns=2, the second tree has the parameters depth d=1 and ns=4. Note that the number of successors ns determines the search width or local diversity of the search while the depth d affects the number of simultaneously considered consecutive search levels, i.e. the degree of foresight within a basic search phase.

Fig. 5
figure 5

Two different search trees of a basic search phase

Full size image

If the best block for a residual space has to be determined, at first the total depth td of the partition searches is determined as a function of the parameter search_effort, i.e. td is increased with search_effort. Then all ordered (number-theoretic) partitions of integer td, denoted by π=(l,d 1,d 2,…,d l ) with l≥1, d j >0, j=1,…,l and \(\sum^{l}_{j=1} d_{j}= td\), are considered. For each such partition π a partition search is carried out with l basic search phases and depth values d j given by π. As explained above the best complete solution over all partition searches then determines the block for the current residual space. If, e.g., the total depth is td=3, then partition searches have to be done for the four partitions (1,3), (2,1,2), (2,2,1) and (3,1,1,1).

The special fashion of tree search outlined before is called partition controlled tree search (PCTRS). According to the experience with the CLP the PCTRS is able to handle two success factors of a tree search, namely the search width and the degree of foresight, in a flexible and balanced way.

To adapt the CLP algorithm to the SPP the main routine is modified (see Fig. 3). If an SPP solution including all given items was found in the first stage then the search for the given container length is aborted, i.e. the second stage is ignored. It has been experimentally proved that in this way the search effort can be reduced without worsening the solution quality.

4 Computational experiments

SPTRS was implemented in C/C++ using the GNU C/C++ compiler together with Netbeans IDE 6.8 as development environment. All tests were run on an Intel 3.16 GHz PC with 3.6 GB RAM (Intel Core2 Duo, CPU 8500 3.16 GHz). In the computational experiments the following parameter settings were used throughout. The parameter minspp_fillrate was set to 90% (cf. Sect. 3.1). For the parameters of method CLTRS the original settings as described in Fanslau and Bortfeldt (2010) were adopted. However, a pair of reduced time limits for the search stages (10 seconds for stage 1, 20 seconds for stage 2) was applied throughout. As explained above the second stage is only performed if no SPP solution was found in the first stage of the search for a given container length. Moreover, in the 3D case a time limit of 80 seconds for the entire search is imposed (commented in detail below). Afterwards the experimental results for the 3D and 2D cases are presented.

4.1 Results on 3D test instances

To evaluate the performance of SPTRS for the 3D-SPP, almost all problem instances introduced by Bortfeldt and Gehring (1999) and by Bortfeldt and Mack (2007) were calculated. Altogether, five different instance sets for the 3D-SPP with a total of 800 instances are used (note that a test case is a subset of an instance set):

  • Instance set SP-BR was introduced in Bortfeldt and Gehring (1999) (see also Bortfeldt and Mack 2007) and includes 10 test cases of 10 instances each. The instances were derived from the 3D-CLP instances proposed by Bischoff and Ratcliff (1995) and Davies and Bischoff (1998), respectively. The number of box types per instance varies from 3 in test case 1 to 50 in test case 10. The mean number of boxes per instance and test case lies between 128 (in test case 5) and 140 (in test case 2). The character of the test cases changes progressively from weakly to strongly heterogeneous. The optimal container lengths are not known.

  • Instance set SP-BR-XL was introduced in Bortfeldt and Mack (2007) and includes 10 test cases of 10 instances each. The problem instances and test cases are similarly constructed as for instance set SP-BR. However the number of boxes per instance amounts constantly to 1000 and the instances can be viewed as weakly heterogeneous throughout. The optimal container lengths are not known.

  • Instance sets L, G and N were introduced in Bortfeldt and Mack (2007). Each of the sets includes 8 test cases with 25 instances each. For all three instance sets the number of box types per instance varies from 8 in test case 1 to 50 in test case 8 of the instance set. The mean number of boxes per instance lies between 120 and 200 boxes. Each instance of instance set L is constructed in such a way that an optimal solution with a volume utilization of 100% (perfect solution) made up of some walls that follow each other in length direction of the container is known. Each instance of set G has a known perfect solution, observing guillotine cutting constraint (C2) that has not a wall structure in general. Finally, each instance of instance set N has a known perfect solution not observing (C2).

The results for the 3D-SPP instances are shown in Tables 3, 4, 5 that are explained as follows:

  • For instance sets SP-BR and SP-BR-XL the numbers of box types per test case are indicated in brackets in column 1 of the related table. For instance sets L, G and N these numbers are part of the names of the test cases shown in column 1 of Table 5.

  • Two SPTRS variants were tested, i.e. SPTRS was applied with and without support constraint (C3). Whether (C3) is observed by SPTRS or by another solution method is indicated in row “100% support” (“yes” or “no”).

  • Four algorithms from literature were included for a comparison: the parallel tabu search method TSA-CC-4P by Bortfeldt and Gehring (1999), the branch and bound method SPBBL-CC4 by Bortfeldt and Mack (2007), the constructive heuristic 3BF and the tabu search method 3BF+TS by Allen et al. (2011). These can be viewed as the most effective methods so far (cf. Table 2). The following computers were used for the compared methods: TSA-CC-4P: four Pentium PCs (200 MHz each), SPBBL-CC4: AMD Athlon (2.0 GHz), 3BF and 3BF+TS: Intel PC (1.86 GHz).

    A time limit for the entire search of SPTRS was imposed to ensure that the compu-tational effort used for SPTRS shows only small differences to the effort spent by the recent competing methods SPBBL-CC4 and 3BF+TS, respectively. Considering the specified time limit of 160 seconds for both the methods 3BF+TS and SPBBL-CC4 and the given data for the processors used, the time limit for SPTRS was set to 80 seconds. Here it was taken into account that this time limit of SPTRS is often slightly exceeded since the elapsed time is only checked outside the integrated container loading method. Mean computing times of SPTRS and all compared methods can be found in Tables 3–10.

    Table 3 Results for instance set SP-BR (best utilizations for case (C3) not required in bold)
    Full size table

  • The solution quality is given as volume utilization (VU) of the container in percent that is calculated as VU=(total box volume)/(wC ∗ hC ∗ lCUsed) (in %). However, Allen et al. (2011) calculate the volume utilization as VU 2=lClB/lCUsed (in %) (cf. Sect. 3.1 for calculation of lClB). It is easily seen that VU 2≥VU in any case (since ⌈a⌉≥a). Both utilizations, VU and VU 2, are indicated for the SPTRS variants in Tables 3 and 4. In Table 5 only utilization VU is indicated since the existence of perfect solutions ensures the identicalness of VU 2 and VU for all instances of the sets L, G and N.

    Table 4 Results for instance set SP-BR-XL (best utilizations for case (C3) not required in bold)
    Full size table
    Table 5 Results for instance sets L, G and N (best utilizations for case (C3) not required in bold)
    Full size table

  • As SPTRS is a deterministic algorithm, the SPTRS results are compared to mean volume utilizations of stochastic algorithms if mean and best utilization values are available. Per method and test case or instance set the mean volume utilization over all instances is presented.

  • Calculation times are given in seconds (related to used processor(s)) and represent total computation times (not times to best-values). Calculation times are averaged over all instances of a test case or instance set. Alternatively time limits are used as calculation times.

The results for the 3D-SPP can be summarized as follows:

  • Generally, the SPTRS variant that fulfills the support constraint (C3) achieves smaller volume utilizations than the other variant. For instance set SP-BR the observance of (C3) “costs” approximately 2.6 %-points and for instance set SP-BR-XL approximately 1.8%-points of volume utilization. These results correspond to the findings of Fanslau and Bortfeldt (2010) on the influence of constraint (C3). However, for nine groups of instances with smaller numbers of box types within the instance sets L, G and N an anomaly regarding this influence could be observed (see Table 5).

    A particular high solution quality can be achieved by SPTRS for weakly heterogeneous problem instances while the solution quality decreases as the heterogeneity of the box sets increases. Note that this is not the case with, e.g., method SPBBL-CC4 (cf., e.g., Table 3).

  • To ensure a fair comparison in first instance only methods that behave in the same way regarding support constraint (C3) should be compared to each other. Hence, the SPTRS variants that observe (C3) should be compared to the parallel tabu search method TSA-CC-4P while the SPTRS variants that do not observe (C3) should be compared to the other methods taken from literature. If constraint (C3) is required SPTRS reaches a better solution quality than the competing method TSA-CC-4P for all 10 test cases of the instance set SP-BR (for other instance sets no results are available for competing methods observing (C3)). If constraint (C3) is not required SPTRS achieves a better or equal solution quality than all competing methods for 28 of 44 test cases. In 3 test cases of instance set SP-BR-XL the competing method 3BF+TS performs better on average and in 13 test cases of the instance sets L, N and G, respectively, the method SPBBL-CC4 achieves the better average utilization. Best results of competing methods are failed for some test cases with higher numbers of box types (see Tables 4 and 5). Averaged over all 200 instances of the sets SP-BR and SP-BR-XL SPTRS achieves a mean volume utilization of 93.3% while the mean utilizations of 3BF+TS and SPBBL-CC4 amount to 90.6% and 89.3%, respectively. The mean volume utilization over all 800 instances of all considered instance sets is 94.3% for SPTRS and amounts to 93.7% for SPBBL-CC4. All in all, SPTRS proves to be very competitive in the 3D case. The mean total calculation times in Tables 3–5 show that the computational effort of SPTRS and the best competing methods is similar.

4.2 Results on 2D test instances

The performance of SPTRS for the 2D-SPP is tested using four instance sets with 616 instances:

  • Instance set SP-KR was introduced by Kröger (1993, 1995) and includes 12 strongly heterogeneous instances with 25 to 60 items. The number of item types corresponds nearly to the number of items and optimal container lengths are not known.

  • Instance set SP-HT was defined by Hopper (2000) and by Hopper and Turton (2000) and comprises three series C, N and T with 21, 35 and 35 strongly heterogeneous instances, respectively. Each series consists of 7 test cases of 3 or 5 instances with (nearly) the same number of items. All instances have perfect optimal solutions without any waste (at least if SPP subtype RF is supposed), i.e. the lower bound lClB (see Sect. 3.1) specifies the optimal container length. The instances of series T have guillotineable optimal solutions while the instances of series N have only non-guillotineable optimal solutions.

  • Instance set SP-N was generated by Burke et al. (2004) and consists of 13 strongly heterogeneous instances with 10 to 3152 rectangles. Each instance has a perfect solution so that the optimal container lengths are known.

  • Instance set SP-BWMV comprises ten classes (test cases) with 50 instances each. The first six classes (C01 to C06) were suggested by Berkey and Wang (1987) and the last four classes (C07 to C10) were defined by Martello and Vigo (1998) (see Iori et al. 2002, for a fine description). Each class has five subclasses with 10 instances each. The item numbers per instance lie between 20 and 100 and all instances are strongly heterogeneous. Optimal container lengths are not known.

Algorithm SPTRS has been tested in two variants, namely for the SPP subtypes OG and RG. In the first variant the orientation of all items is fixed (as stipulated in all tested 2D instances) while in the second variant rotating the items is allowed. In the interest of a fair comparison CLTRS is primarily matched to 2D-SPP methods from literature that also observe the guillotine cutting constraint, i.e. that are specified for SPP subtypes OG or RG. Only if for a given set of instances results of such methods are not available, top-quality procedures for subtypes OF or RF are considered. As in the 3D case SPTRS is compared preferably to mean (not best) results of stochastic methods and total calculation times are given in seconds for the used processor. Unlike the 3D case no time limit for the entire search of method SPTRS is specified for the calculation of 2D instances since there are too many competing methods that were tested using very different testbeds.

The results for instance set SP-KR can be found in Table 6. For each instance the number of items is given in brackets (column 1). SPTRS is compared to the parallel genetic algorithms by Kröger (1993, 1995) and Schnecke (1996), respectively. Further competing methods are the genetic algorithm SPGAL by Bortfeldt (2006) and the B&B method HRBB by Cui et al. (2008). SPGAL has been tested on a Pentium PC with 2 GHz while HRBB results were achieved on a PC with 2.8 GHz. All competing methods work for subtype RG. In Table 6 the used container lengths (lCUsed) are presented. SPTRS (RG) performs somewhat better than the parallel GAs and HRBB and it performs slightly worse than SPGAL. While SPTRS achieves a better quality for the smaller instances SPGAL dominates for the larger ones.

Table 6 Results (used container lengths) for instance set SP-KR (best results for type RG in bold)
Full size table

Table 7 shows the results for instance set SP-HT, series C. For each test case (of three instances) the number of items per instance is given in brackets (column 1). SPTRS is compared to the recursive procedure HR and the simulated annealing method SA+HR by Zhang et al. (2005, 2006), respectively, the genetic algorithm SPGAL by Bortfeldt (2006) and to the B&B method by Cui et al. (2008). HR has been tested on a Dell GX260 PC with 2.4 GHz while HR+SA was run on a DELL GX270 with 3.0 GHz CPU. While SPGAL is tailored to subtype OG the other competing methods work for subtype RG.

Table 7 Results (mean gaps in %) for instance set SP-HT, series C (best results for type RG in bold)
Full size table

In Table 7 the mean gaps are given per test case where the gap of an instance’s solution is calculated as gap=(lCUsed−lClB)/lClB (in %) (cf. Sect. 3.1). Both SPTRS variants perform better than the competing methods. SPTRS(RG) improves the mean gap values of HR, SA+HR and HRBB by 3.1, 2.2 and 0.5%-points, respectively, while SPTRS (OG) reaches an improvement of 1.1%-points compared to SPGAL (OG). However, it must be stated that HRBB reaches a good solution quality within very short calculation times compared to the other methods.

Table 8 includes the results for instance set SP-HT, series N and T. For each test case (of five instances) the number of items per instance is given in brackets (columns 1, 6).

Table 8 Results (mean gaps in %) for instance set SP-HT, series N and T
Full size table

SPTRS is compared to method SVC(SubKP) by Belov et al. (2008) and to the GRASP algorithm by Alvarez-Valdes et al. (2008) that are both tailored to subtype OF. SVC(SubKP) was executed on an AMD PC with 2.4 GHz while the results for the GRASP algorithm were calculated on a Pentium 4 Mobile PC with 2 GHz. Again, mean gaps are given per test case. Obviously, the observance of the guillotine cutting constraint (C2) restricts the achievable solutions especially for the smaller instances while this is to some extent compensated by allowing the boxes to be rotated for SPTRS(RG).

Table 9 includes the results for instance set SP-N. For each instance the number of items is indicated in brackets (column 1). SPTRS is compared to method BF+SA by Burke et al. (2009) and 3BF+TS by Allen et al. (2011) that are designed for subtype RF. BF+SA was calculated on a Pentium 4 PC with 2 GHz while Allen et al. (2011) used an Intel PC with 1.86 GHz. The utilizations are given according to the VU formula in Sect. 4.1. Allen et al. (2011) calculate the volume utilization for instance set SP-N as VU 2 (see Sect. 4.1). However, the existence of perfect solutions ensures the identicalness of VU 2 and VU for all SP-N instances. The best mean volume utilization so far has been slightly improved by the SPTRS (RG) variant and the SPTRS (OG) variant is also not dominated by the competing methods that do not satisfy the guillotine cutting and the orientation constraint.

Table 9 Results (volume utilizations VU in %) for instance set SP-N (best results for type RF in bold)
Full size table

Table 10 presents the results for instance set SP-BWMV. For each class and subclass the constant number of boxes per instance is indicated in column 1. SPTRS is again compared to method SVC(SubKP) by Belov et al. (2008) and to the GRASP algorithm by Alvarez-Valdes et al. (2008) that are tailored to subtype OF. Per subclass or class mean used container lengths are shown. SPTRS (RG) achieves equal or better solutions than the GRASP algorithm for 47 of the 50 subclasses while SPTRS (OG) generally does not reach the solution quality of the compared methods for subtype OF. This result goes with the findings for instance set SP-HT, series N and T.

Table 10 Results (used container lengths) for instance set SP-BWMV
Full size table

All in all, SPTRS achieves a top solution quality in reasonable computation times also for 2D-SPP instances. In terms of solution quality SPTRS seems to be at least on a par with the most effective methods for solving the 2D-SPP with guillotine cutting constraint, namely SPGAL and HRBB. A high solution quality was also proved in comparison with high-quality methods for subtype RF using instance set SP-N.

5 Conclusions

In this article an algorithm for the multi-dimensional strip packing problem with guillotine cutting constraint is presented that is based on the method by Fanslau and Bortfeldt (2010) for solving the container loading problem. Solving the SPP is reduced to solving a series of CLP instances with decreasing container lengths. A preferably small value is chosen for the initial container length to shorten the search. The chosen approach is advantageous in some regards. It is easy to implement and the observance of constraints is transferred from the CLP method to the SPP method. The main question to be investigated was whether the high performance of the integrated CLP method is also transferred to the SPP method. This question could be answered in the affirmative by means of extensive numerical experiments. In a comparison to the best known 3D-SPP solution methods the proposed SPP algorithm, called SPTRS, achieved a high solution quality using a similar computational effort as the compared methods. In 28 of 44 3D-SPP test cases SPTRS reached the best volume utilization on average. While SPTRS always satisfies the guillotine cutting constraint this is not the case for most of the competing 3D-SPP methods. Moreover, the experiments proved that algorithm SPTRS belongs to the most effective methods for the 2D-SPP with guillotine cutting constraint.