A NEW HEURISTIC ALGORITHM FOR CONSTRAINED RECTANGLE-PACKING PROBLEM

Chen, Duanbing

The constrained rectangle-packing problem is the problem of packing a subset of rectangles into a larger rectangular container, with the objective of maximizing the layout value. It has many industrial applications such as shipping, wood and glass cutting, etc. Many algorithms have been proposed to solve it, for example, simulated annealing, genetic algorithm and other heuristic algorithms. In this paper a new heuristic algorithm is proposed based on two strategies: the rectangle selecting strategy and the rectangle packing strategy. We have applied the algorithm to 21 smaller, 630 larger and other zero-waste instances. The computational results demonstrate that the integrated performance of the algorithm is rather satisfying and the algorithm developed is fairly efficient for solving the constrained rectangle-packing problem.

Keywords: Constrained rectangle-packing problem; non-guillotine; heuristic algorithm; corner-occupying action; layout value.

1. Introduction

The constrained rectangle-packing problem is the problem of packing a subset of rectangles into a larger rectangular container, with the objective of maximizing the layout value. It is known in the literature as the “two-dimensional single large object placement problem”. The reader is referred to Hadjiconstantinou and lori (forthcoming) for more details. It belongs to a subset of classical packing problems with many industrial applications such as shipping, wood and glass cutting, etc. To solve this problem, various algorithms based on different strategies have been suggested. In general, t Ik1Sc algorithms can be classified into two major categories: non-deterministic algorithms and deterministic algorithms. The key aspect of non-deterministic algorithms is to design data structures that can represent the geometric relationships among the rectangles. The crux of deterministic algorithms is to determine the packing rules, such that the approximate optimal solution can be obtained within reasonable runtime.

Amarai and Letchford (2001) presented an approach to determine the upper bound of the non-guillotine cutting problem using integer linear programming relaxation. In Boschetti et al. (2002), some new bounding procedures were obtained by different relaxations of a new mathematical formulation of non-guillotine cutting problem. Capraraand Monaci (2004) presented an approach to determine the upper bound of the two-dimensional knapsack problem by using a natural relaxation, namely, one-dimensional knapsack problem with item weights equal to the rectangle areas. Based on this relaxation, they proposed four exact algorithms. Fekete and Schepers (2004) presented a new exact algorithm using a graph-theoretical characterization of feasible layouts. Lai and Chan (1997) presented a simulated annealing algorithm based on evolutionary strategy. Computational results were presÌUited for a number of randomly generated test instances with the objective of minimising the trim loss. Hopper and Turton (2001) gave an empirical investigation of meta-heuristic and heuristic algorithm of the orthogonal packing problem of rectangles. Leung et al. (2001) presented a simulated annealing heuristic with a move corresponding to either swapping two rectangles in the ordered representation or moving a single rectangle to a new position in the representation. They also presented a genetic approach involving five different crossover operators. Wu et al. (2002) suggested two heuristic algorithms based on less flexibility first principle. Beasley (2004) proposed a genetic algorithm based on population heuristic (PH) for the constrained rectangle-cutting problem. Computational results on 21 smaller and 630 larger test instances were presented. Alvarez- Valdes et al. (2005) presented a greedy randomized adaptive search procedure (GRASP) for the constrained twodimensional non-guillotine cutting problem. They investigated several strategies for the constructive and improvement phases and several choices for the critical search parameters. The computational results are rather good. Zhang et al. (2005) presented a new hybrid heuristic algorithm based on divide-and-conquer strategy.

Inspired by the above approaches, a new heuristic algorithm for the constrained rectangle-packing problem (HCRP) is proposed in this paper. The objective is to maximize the layout value, that is. the total value of the rectangles that have already been packed in the container. The algorithm includes two important strategies. The first, strategy is to S(1IeCt the rectangle with the largest value per unit area, and the second is to pack the rectangle at a corner, even a cave if possible. So the rectangles are close to each other wisely, and the layout valut1 is improved consequently. Twenty-one smaller and 630 larger test instances and other zero-waste instances are used to test the algorithm developed. The computational results demonstrate that the algorithm developed is fairly efficient for solving the constrained rectanglepacking problem.

2. Problem Description

The constrained rectangle-packing problem is concerned with packing a subset of ree tangles into i a larger red angular container, with the objective of maximizing the layout value. Non-guillotine packing layout is allowed but each rectangle should not be rotated.

Now, we give a detailed description of this problem. An empty larger rectangular container R^sub 0^ (L^sub 0^, W^sub 0^) of length L^sub 0^ and width W^sub 0^ is given. And there are m types of smaller rectangles ^sub Ri^ (l^sub i^, w^sub i^) of length l^sub i^ and width w^sub i^ (i = 1, 2, … , m). Each type i has an associated value v^sub i^ (i = 1, 2, . . . , m). In the plane rectangular coordinates oxy, the left-bottom of the container is placed at (0, 0), with its four sides parallel to X- or Y- axis. The objective is to maximize the layout value, that is, the total value of the rectangles that have already been packed in the container. The constraints for packing rectangles are:

1. Each side of a rectangle should be parallel to a side of the container.

2. There should be no overlapping for any two rectangles, i.e., the overlapping area is zero.

3. The rectangle should not be rotated, i.e., the rectangles R (l, ^sub w^) and R’ (w,l) represent two different rectangles if l ≠ w.

4. The number of rectangles of each type i that are packed in the container should lie between P^sub i^ and Q^sub i^ (0 ≤ P^sub i^ ≤ Q^sub i^).

Without significant loss of generality, it is usual to assume that L^sub 0^, W^sub 0^, l^sub i^ and w^sub i^ (i = 1,2,. .. ,m) are integers. To ease the notation in this paper we shall use M = ∑^sup m^^sub i=1^ Q^sub i^, VPA^sub i^ – v^sub i^/(i . w^sub i^) (i = 1,2, … m), and use p^sub i^ to denote the number of rectangles of type i (i = 1, 2,… ,m) that have already been packed in the container.

3. Algorithm Description

3.1. Main idea and strategies

If some rectangles have already been packed into the container without overlapping, which rectangle is the best candidate for the remainder and which position is the best one to be filled? We can get two strategies from these two questions: the rectangle selecting strategy and the rectangle packing strategy. According to the rectangle selecting strategy, the rectangle with a higher VPA should be selected with priority. The rectangle packing strategy states that the rectangle should always occupy a corner, and the caving degree of the packing action should be as large as possible. So the rectangles are close to each other wisely, and the layout value is improved consequently.

3.2. Definitions

3.2.1. Configuration

Figure 1 shows a configuration. Some rectangles have already been packed into the container without overlapping and some remain outside. A configuration is called an initial one if there is no rectangle in the container. A configuration is called an end one if all rectangles have already been packed into the container without overlapping or, none of the remaining rectangles can be packed in.

3.2.2. Corner-occupying action

A packing action is called a corner-occupying action (COA). if the rectangle to be packed touches at least two items (an item may be a rectangle or one of the four sides of the container), and the touching lengths are longer than zero. A COA is a feasible one if the rectangle to be packed does not overlap with any previously packed rectangle nor exceeds the container boundary. For example, as shown in Fig. 2, the shadowy rectangles have already been packed, and the rectangle “1” is outside the container. The packing action is a COA, if rectangle “1” is placed at position A or B or C. It is not a COA if placed at position D or E.

In particular, a COA is called a cave-occupying action, if the rectangle related to this COA not only occupies a corner, but, also touches some other previously packed rectangles or the container. For instance, as shown in Fig. 2, if rectangle ‘T” is placed at position A, it occupies the corner formed by rectangles a and b. Furthermore, it touches rectangle

3.2.3. Distance between two rectangles

This distance is an extension of Manhattan distance between two points. For instance, as shown in Figs. 3(a), 3(b) and 3(c), the distance between two rectangles is zero, d and d^sub 1^ + d^sub 2^ respectively.

3.2.4. Distance between one rectangle and several other rectangles

For a rectangle R and a set of rectangles [R^sub i^|^sub i^ = 1, 2,…, k}. Let the distance between R and R^sub i^ be d^sub i^ (i = 1, 2 ,…, k). The distance between rectangle R and k rectangles R^sub 1^, R^sub 2^, …, R^sub k^ is defined as min^sub i∈^{1, 2 ,…. k}(d^sub i^).

3.2.5. Caving degree of COA

The caving degree reflects the nearness between the rectangle to be packed and its nearest rectangle (excluding the rectangles that form the corner). According to the definition, the caving degree of a COA is no greater than 1. In particular, it equals 1 when the corresponding rectangle occupies a cave formed by at least three previously packed rectangles; it may also be smaller than zero when d^sub min^ > [the square root of]l . w. In the packing process, we always select the COA with the largest caving degree, and pack the corresponding rectangle into the container at the corresponding position.

3.2.6. Precedence of point

Let P^sub 1^ (x^sub 1^, y^sub 1^) and P^sub 2^ (x^sub 2^, y^sub 2^) be two points in the plane rectangular coordinates o-xy, P^sub 1^ has precedence over P^sub 2^ if x^sub 1^

3.3. Rectangle selecting strategy

If p^sub i^ ≥ P^sub i^ for each type i (i = 1,2, … ,m), then select the rectangles with the largest VPA from type k with p^sub k^

Several different rectangles may be selected by the selecting strategy. For each selected rectangle, there may be zero, one, or more than one candidate positions (i.e., COAs) to pack it. If there is no feasible COA for any selected rectangles, we set the VTM of these selected rectangles to zero temporarily, and reapply above selecting strategy until there exists a feasible COA to pack the selected rectangle, or none of remaining rectangles can be packed in.

3.4. Selecting criterion for COA

1. Main criterion: select the COA with the largest caving degree.

2. Tiebreaker 1: select the COA with the highest precedence of the left-bottom vertex of the corresponding rectangle.

3. Tiebreaker 2: select the COA with the smallest index of the corresponding rectangle.

3.5. Upper hound value of the problem

The branch-and- bound method is used in this paper to solve the above integer programming. The reader is referred to Kolesar (1967) for more details on this method.

3.6. Sketch of the algorithm

Under the current configuration, select the rectangles according to the rectangle selecting strategy (see Sec. 3.3). For each selected rectangle, pseudo-pack it at all corners to find the feasible COAs. By “pseudo-pack” we mean the rectangle is packed temporarily and will be removed from the container in the future. Then select a single COA according to the selecting criterion (see Sec. 3.4) and pack the corresponding rectangle at the corresponding position. Repeat this process until the number of the rectangles that have already been packed is equal to M, or none of the remaining rectangles can be packed in.

The preceding paragraph describes a deterministic greedy process. In order to get higher layout value, we introduce backtracking process. First, enumerate all feasible COAs by pseudo-packing the rectangles that are selected by rectangle selecting strategy. Second, for each COA, pseudo-pack the corresponding rectangle and calculate a score for this COA by calling Greedy packing procedure. This score represents the quality of the COA. The higher the score is, the higher the quality of the COA. Finally, select the COA with the highest score and pack the corresponding rectangle according to the selected COA. If there are multiple COAs with equal and highest score, use selecting criterion to break tie. Repeat this process until the number of the rectangles that have already been packed is equal to ?/, or none of the remaining rectangles can be packed in. This process describes a backtracking algorithm (HCRP algorithm). The details will be described in Sec. 4.2.

4. The Algorithm

4.1. Greedy packing procedure (C)

Begin

The parameter C is the current configuration.

Under the configuration C. select the rectangles according to the rectangle selecting strategy (see Sec. 3.3) and enumerate all feasible COAs for each selected rectangle.

While there exist some COAs do

Calculate the caving degree for each COA.

Select a single COA according to the selecting criterion (see Sec. 3.4).

Pack the corresponding rectangle and obtain the new configuration, denoted by C.

Under the configuration C, select, the rectangles according to the rectangle selecting strategy (see Sec. 3.3) and enumerate all feasible COAs for each selected rectangle.

End while

Return the configuration C.

End

4.2. HCRP procedure

Begin

Input the length L^sub 0^ and width W^sub 0^ of the container R^sub 0^ (L^sub 0^, W^sub 0^), and input the length l^sub i^, width w^sub i^, associated value v^sub i^, P^sub i^ and Q^sub i^ of each type i (i = 1, 2, . . . , m).

Generate the initial configuration C.

Under the configuration C, select the rectangles according to the rectangle selecting strategy (see Sec. 3.3) and enumerate all feasible COAs for each selected rectangle.

While there exist, some COAs do

For each COA do

Pseudo-pack the corresponding rectangle and obtain the new configuration, denoted by C”.

C’ = Greedy packing procedure(C).

If the layout value of configuration C” equals to the upper bound value then OUt])Ut the layout result, and stop successfully.

Else

Record the layout value of configuration C as the score of the corresponding COA.

Remove the pseudo-packed rectangles from the container.

End if

End for

Select the COA with the highest score.

If there are multiple COAs with the highest score then

Select a single COA according to the selecting criterion (see Sec. 3.4).

End if

Pack the corresponding rectangle and obtain the new configuration, denoted by C.

Under the configuration C, select the rectangles according to t he rectangle selecting strategy (see Sec. 3.3) and enumerate all feasible COAs for each selected rectangle.

End while

Output the layout result.

End

4.3. Computational complexity

As each iteration of packing will occupy one or more corners and generate some new corners, the number of corners left should be proportional to m × M. Therefore, for each rectangle to be packed, the number of COAs generated will be bounded by O (m^sup 2^ × M). For Greedy packing procedure, the process is repeated once for each rectangle packed. As a result, the worst-case time complexity of Greedy packing procedure will be O (m^sup 2^ × M × M) = O (m^sup 2^ × M^sub 2^). For HCRP procedure, the Greedy packing procedure is repeated O (m^sup 2^ × M) times for each rectangle packed. So the worst-case time complexity of HCRP procedure will be O (m^sup 2^M^sup 2^ × m^sup 2^M × M) = O (m^sup 4^ × M^sup 4^). It should be noted that the average time complexity will be much smaller than O (m^sup 4^ × M^sup 4^). The time complexity of our algorithm is polynomial and relative small compared with the exponential time complexity of the original problem.

5. Computational Results

In this study, 21 smaller and 030 larger test instances and other zero-waste instances are used to evaluate the performance of the HCRP algorithm. The comparisons between PH (Beasley. 2004), GRASP ( Alvarez- Valdes et al., 2005), HH (Zhang et al., 2005) and HCRP are shown in Tables 1 4. PH is run on a Silicon Graphics ()2 workstation with R10000 chip 225MHz and 128MB main memory, GRASP on Pentium III with 800MHz, HH on Dell GX260 with 2.4GHz CPU, and HCRP is implemented by C#.net programming language and run on an IBM portable PC with 2.0GHz processor and 256MB memory.1

5.1. Publicly available smaller test instances

In order to evaluate the performance of the HCRP. we use 21 publicly available smaller test instances whose optimal solutions are known. These 21 instances are taken from Beasley (1985). Hadjiconstantinou and Christofides (1995), Wang (1983). Christofides and Whitloek (1977) and Fekete and Schopors (1097). They can also be obtained from http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/ngcutap.txt.

The comparisons between PH. GRASP and HCRP are shown in Table 1. For tin1 21 instances, 13 of them achieved optimal solutions by PH, 18 of them achieved optimal solutions by GRASP, and 17 of them achieved optimal solutions by HCRP.

5.2. Publicly atiailable larger test instances

In order to investigate the performance of the HCRP on larger instances, we use 630 larger test instances taken from Beasley (2004). These instances can be classified into three types (type I, II, III). Each type has seven categories (rn = 40; 50; 100; 150:250:500; 1000); each category has three pairs with P^sub i^ = 0 and Q^sub i^ = Q* (Q* = 1;3;4); and each (rn,Q*) pair has ten different instances. All 030 instances can be obtained from http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/ngcutfel.txt, http:// people. brunel.ac.uk/~ma8tjjb/jeb/orlib/files/ngcutfe2.txt and http:// people. brunel. ac.uk/~mastjjb/jeb/orlib/files/ngcutfe3.txt. The reader is referred to Beasley (2004) for more details on these instances.

The average percentage deviation obtained by HCRP is 1.31% for type I, 1.3% for type II and 1.171% for type III, and the average runtime is less than 30 seconds. The average percentage deviation obtained by PH is 1.637%, 1.697% and 1.66%, with an average runtime of 558.1 seconds, 668.4 seconds and 830.0 seconds respectively. The average percentage deviation obtained by GRASP is 1.07% with an average runtime of 5.91 seconds, as shown in the last row of Table 2.

5.3. Doubly constrained test instances

The 21 test instances mentioned in Sec. 5.1 were transformed by Beasley (2004) into doubly constrained instances by defining some lower bounds P^sub i^, specifically for each type from i = 1,2,.. .,m satisfying m^sub j=1^ ∑^sup m^^sub j=1^ (l^sub j^w^sub j^)P^sub j^ + l^sub i^w^sub i^ ≤ (L^sub 0^W^sub n^)/3, the lower bound P^sub i^ is set to 1. The reader is referred to Beasley (2004) for more details. This set of instances would allow us to test the algorithm in the general case of doubly constrained instances. The computational results on these 21 doubly constrained instances are shown in Table 3. The upper bound value is equal to the optimal solution value taken from Table 1.

5.4. Zero-waste test instances

We also use 21 zero-waste instances provided by Hopper and Turton (2001) to test our algorithm. The comparisons between HH (Zhang et al., 2005) and HCRP are listed in Fable I. For these 21 instances. 7 of them achieved optimal solutions by HCRP, and 3 of them achieved optimal solutions by HH. From Table 4, we can see that the integrated performance of HCRP is also rather satisfying for this special case.

6. Conclusions

In this paper, we have proposed a new heuristic algorithm. HCRP. for solving the constrained rectangle-packing problem. As demonstrated, this algorithm is able to achieve a high layout value within reasonable runtime. For the 21 smaller test instances taken from the literatures, 17 of them achieved optimal solutions by HCRP. And for the 630 larger test instances taken from Beasley (2004), the average percentage deviation obtained by HCRP is 1.31% for type I, 1.3% for type II and 1.171% for type III, and the average runtime is less than 30 seconds. Two special cases, namely, doubly constrained and zero-waste instances are also used to test our approach. The integrated performance of HCRP is also rather satisfying for these two special cases. The computational results demonstrate that the algorithm developed is fairly efficient for solving the constrained rectangle-packing problem.

Acknowledgments

We would like to thank the anonymous referees for many constructive suggestions. This work was partially supported by National Natural Science Foundation of China under Grant NO. 10471051 and by NKBRPC (2004CB318000).

1 The computer used by us is about 1.25 times faster than that by PH, about 2.5 times faster than that by GRASP, and about 1.2 times slower than that by HH.

2 The value of GRASP is the average value of type I, II and III.

References

Alvarez-Valdes, R, F Parreño and JM Tamarit (2005). A GRASP algorithm for constrained two-dimensional non-guillotine cutting problems. Journal of the Operational Research Society, 56, 414-425.

Amarai, A and AN Letchford (2001). An improved upper bound for the two-dimensional nonguillotine cutting problem. Technical report, Lancaster University, UK.

Beasley, JE (1985). An exact two-dimensional non-guillotine cutting tree search procedure. Operations Research, 33, 49-64.

Be.asley, JK (2004). A population heuristic for constrained two-dimensional non-guillotine cutting. Kuropean Journal of Operational Research, 156, 601-627.

Boschetti, MA, A Mingozzi and E Hadjiconstantinou (2002). New upper bounds for the two-dimensional orthogonal non guillotine cutting stock problem. IMA Journal of Management Mathematics, 13, 95-119.

Caprara, A and M Monaci (2004). On the two-dimensional knapsack problem. Operations Research Letters, 32, 5-14.

Christofides, N and C Whit lock (1977). An algorithm for two-dimensional cutting problems. Computers and Operations Research, 25, 30-44.

Fekete, SP and J Schepers (1997). A new exact algorithm for general orthogonal ddimensional knapsack problems. Springer Lecture Notes in Computer Science. 128 1. 144-156.

Fekete, SP and J .Schepers (2004). A combinatorial characterization of higher-dimensional ort hogonal packing. Mathematics of Operations Research, 29, 353.368.

Hadjiconstantinou. E and M lori (forthcoming). A hybrid genetic algorithm for the twodimensional single large object placement problem. To appear in Kuropean Journal of Operational Research.

Hadjiconstantinou. E and N Christolides ( 1995). An exact algorithm for general, orthogonal, two-dimensional knapsack problems. Kiiiopian Journal of Operational Resemeli, 83, 39-56.

Hopper. E and B Turton (2001). An empirical investigation of meta-heiiristic and heuristic algorithm for a 2D packing problem. Kuropean Journal of Operational Research, 128, 31-57.

Kolesar, PJ (1967). A branch and bound algorithm for the knapsack problem. Management Science, 13, 723-735.

Lai, KK and WM Chan (1997). An evolutionary algorithm for the rectangular cutting stock problem. International Journal of Industrial Engineering, 4, 130-139.

Leung, TW, CH Yung and MD Troutt (2001). Applications of genetic search and simulated annealing to the two-dimensional non-guillotine cutting stock problem. Computers and Industrial Kngineering, 40, 201 214.

Wang, PY (1983). Two algorithms for constrained two-dimensional cutting stock problems. Operations Research, 31, 573-586.

Wu, YL, W Huang, SC Lau, CK Wong and GH Young (2002). An effective quasi-human baaed heuristic for solving the rectangle packing problem. Kuropean Journal of Operational Research, 141, 341-358.

Zhang, D, A Deng and Y Kang (2005). A hybrid heuristic algorithm for the rectangular packing problem. Lecture Notes in Computer Science, 3514, 783-791.

DUANBING CHEN* and WENQI HUANG

College of Computer Science

Huazhong University of Science and Technology

Wuhan 430074, China

“hustcdb@yahoo.com.cn

Received 19 December 2005

Accepted 8 July 2006

* Corresponding author.

Duanbing Chen is a PhD candidate of Computer Science at Huazhong University of Science and Technology, China. He received his BSc in Mathematics in 1994 from Sichuan Normal College, his MS in 1997 from Southwest Petroleum Institute. His main area of research is in combinatorial optimization. He has published some articles on this topic in journals such as Computers und Operations Research, Computer Science (in Chinese), and Computer Engineering and Applications (in Chinese).

Wenqi Huang is a Professor of Computer Science at Huazhong University of Science and Technology. China. He received his BSc in Mathematics in 1964 from Peking University. From 1981 to 1982, he worked as a visiting scholar at Mathematics Department, Cornell University. He got the gold prize of the Third International Competition for Solving NP-Coinplete Problem SAT in 1996. His research interests include P =? NP problem and practical algorithm for solving NP-hard problems. He has published numerous articles on this topic in journals such as European Journal of Operational Research, Journal of Operational Research Society, Computers and Operations Research, Simulation Modeling Practice and Theory, and Annals of Operations Research.

Are you headed for an all-noodle diet?

Feed: Grain supply and use of coarse grains projected down in 1991/92 - production and consumption statistics