# A Quasiphysical and Dynamic Adjustment Approach for Packing the Orthogonal Unequal Rectangles in a Circle with a Mass Balance: Satellite Payload Packing

Authors: Ziqiang Li; Xianfeng Wang; Jiyang Tan; Yishou Wang
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Packing orthogonal unequal rectangles in a circle with a mass balance (BCOURP) is a typical combinational optimization problem with the NP-hard nature. This paper proposes an effective quasiphysical and dynamic adjustment approach (QPDAA). Two embedded degree functions between two orthogonal rectangles and between an orthogonal rectangle and the container are defined, respectively, and the extruded potential energy function and extruded resultant force formula are constructed based on them. By an elimination of the extruded resultant force, the dynamic rectangle adjustment, and an iteration of the translation, the potential energy and static imbalance of the system can be quickly decreased to minima. The continuity and monotony of two embedded degree functions are proved to ensure the compactness of the optimal solution. Numerical experiments show that the proposed QPDAA is superior to existing approaches in performance.


---

## Body

## 1. Introduction

2D rectangle packing problems are derived from the industry and antiaircraft field [1–3]. They occur in logistics packing, plate cutting, the layout design of the very large scale integration (VLSI), and satellite modules. They can be divided into unconstrained rectangle packing problems [1] and constrained ones [3]. Both are NP-hard problems and are difficult to be solved. However they have attracted much attention and some packing approaches for different containers have been reported in literatures.For the 2D rectangle container, the packing approaches mainly include graph theories [4–7], branch-and-bound methods [8–10], dynamic planning [11], heuristics [12–15], artificial intelligent [16], evolutionary approaches [17], and hybrid approaches [18–20]. Regarding the strip container, main packing approaches are branch-and-bound methods [21], heuristics [22, 23], and evolutionary approaches [24, 25]. On the 2D polygon or 3D polyhedron container, the existing packing approaches have heuristics [26], evolutionary approaches [27–29], and integer programming [30]. Some scholars are interested in the packing problem of the convex region and have proposed heuristics [26] and branch-and-bound approaches [31].The layout design problem of the satellite module described in [32] is an important packing problem, which can be transformed into the problem of packing 2D orthogonal unequal rectangles within a circular container with the mass balance (BCOURP). In 1999, Feng et al. [33] built a mathematical model of this problem and analyzed the isomorphism and equivalent intrinsic properties among its layout schemes by using the graph theory and group theory and proposed a theoretical global optimization algorithm. In 2007, Xu et al. [34] defined embedded degree functions between two rectangles and between the rectangle and circular container and presented a compaction algorithm with the particle swarm local search (CA-PSLS). Their idea is that a feasible solution with a smaller envelope radius obtained through the gradient method is taken as an elite individual and the optimal solution is obtained by the PSO iteration. In 2010, Xu et al. [35] suggested a heuristic algorithm ordered by GA (GA-HA, see its algorithm steps in Appendix A and Figure 1). Its key technology is the positioning strategy of constructing the feasible solution. By combining it with GA, the computational efficiency and solution quality are improved.Figure 1
The sketch map for available positions of the rectangle.Generally, there exist strong points and deficiencies for each type of approaches.(i)
For approaches based on the graph theory, there exists combinatorial explosion when the adjacent topological relation is transformed into the layout diagraph without a size limit for the large-scale layout problem. This is because only two limited relations called the vicinity and distance can be used in pruning branch.(ii)
The heuristic method can be used to quickly construct a feasible solution. But it is generally not easy to devise a good heuristic strategy, unless the designer makes a long time painstaking effort and has good luck.(iii)
Stochastic algorithms have the global search ability, but there exists the bottleneck of time-costing overlapping area calculation for them [33]. By combining the heuristic method with the stochastic algorithm, their respective advantages can be exerted to the utmost. Based on this mechanism, CA-PSLS and GA-HA are consecutively proposed to solve this problem. According to No Free Lunch Theory [36], how to obtain the knowledge from the problem itself and its area and fuse it into the heuristic and stochastic search mechanism is a way of designing a high performance approach for this problem.Huang et al. [37–40] presented a quasiphysical and quasihuman heuristic algorithm and its variants for the circle packing problem. They obtained excellent results. For BCOURP, Xu et al. [34] proposed CA-PSLS based on embedded degrees between circumcircles of two rectangles and between the container and rectangle’s circumcircle. But due to the discontinuity of the two embedded degree functions, it is difficult to obtain a high quality solution by using CA-PSLS. That is, constructing the continuous rectangular embedded function and exploring a better optimized mechanism are necessary for this problem. Therefore, in this paper, we consider two definitions of monotonous and continuous embedded degrees between two orthogonal rectangles and between an orthogonal rectangle and the container and suggest a dynamic adjustment strategy. We merge them into the proposed QPDAA to improve the solution quality of BCOURP. Numerical experiments will test effectiveness of the considered QPDAA.The remainder of this paper is organized as follows. The problem statement and mathematical model are in Section2. The compact and feasible solution strategy and dynamic adjustment strategy are given in Sections 3 and 4, respectively. This algorithm is presented in Section 5. Section 6 is experiments and analysis. The conclusion is shown in Section 7. The final part is acknowledgment.


## 2. Problem Statement and Mathematical Model

Consider the following two related definitions whereIn={1,2,…,n} and n is the number of rectangles.Definition 1.
As shown in Figure2, let the origin of the Cartesian coordinate system be the center of the container. Let Ri denote the ith (i=1,2,…,n) rectangle and let (xi,yi), li, wi, mi, and θi be its center, length, width, mass, and direction angle between its long side and the positive direction of the x-axis, respectively. Then a layout scheme of n rectangles Ri (xi,yi,li,wi,mi,θi) (i=1,2,…,n) can be denoted by X′ (xi,yi,θi∣i=1,2,…,n).Figure 2
The definition of a rectangle.Definition 2.
For a layout schemeX′, if θi=0° or 90°, then X′ is an orthogonal rectangle packing scheme, Ri (i∈In) is an orthogonal rectangle, and the packing is the orthogonal rectangle packing (see Figure 3).Figure 3
The orthogonal rectangle packing scheme.Herein this paper considers only orthogonal rectangle packing schemes.Suppose that the center of each rectangle coincides with its mass center. LetT be a rectangle set {R1,R2,…,Rn}; then the mathematical model of this problem can be described as follows. Find a solution X=(xi,yi,θi∣i=1,2,…,n)T and X satisfies Formulas (1)–(4). Consider
(1)min⁡f(X)(2)s.t.int⁡Ri∩int⁡Rj=Ø,i,j=1,2,…,n,i≠j(3)int⁡(Ri)∩int⁡(Rc)=int⁡(Ri)i=1,2,…,n(4)JX=∑i=1nmixi2+∑i=1nmiyi2≤δ.In Formula (1), f(X) denotes the radius of the enveloping circle of the scheme X whose circular center is at (0,0). Formula (2) indicates that there is no overlap region between two rectangles Ri and Rj. Formula (3) indicates that all rectangles are contained in the container. In Formulas (2) and (3), int⁡(Ri) denotes the interior region of the rectangle Ri. Formula (4) means that the static imbalance J(X) of the solution X is less than its threshold δ, where δ>0.


## 3. Compact and Feasible Solution Strategy

Based on the potential energy function of the embedded degree between two circles, Huang et al. [38–40] proposed the quasiphysical strategy and its variants for the circle packing problem. Inspired by the quasiphysical idea, we suggest a compact and feasible strategy for BCOURP.


### 3.1. Embedded Degree Function and Related Properties

Xu et al. [34] defined the embedded degrees between two rectangles and between the rectangle and container by Definitions 3 and 4, respectively.Definition 3.
Letri′ and rj′ (i,j=1,2,…,n and i≠j) denote the radii of the circumscribed circles of two rectangles Ri and Rj, respectively, and dij (see Figure 4(a)) the embedded degree between them (see Figure 4(a)); then dij can be calculated by
(5)dij=ri′+rj′-xi-xj2+yi-yj2ifRiandRjoverlapi,j=1,2,…,n,i≠j0otherwise.Two embedded degree definitions in [34].
(a)
The embedded degree between two rectangles
(b)
The embedded degree between the rectangle and containerDefinition 4.
LetRc and ri′ (i=1,2,…,n) denote the radii of the container and circumscribed circle of the rectangle Ri, respectively, and d0i (see Figure 4(b)) the embedded degree between the rectangle and container; then d0i can be calculated by
(6)d0i=xi2+yi2+ri′-RcifRioverlapwiththecontaineri=1,2,…,n0otherwise.Both of the above two embedded degree functions are discontinuous in the critical state from overlapping to separating, as has been discussed by Stoyan and Yaskov [41]. For example, as shown in Figure 5, by moving one rectangle along a direction, two rectangles with the overlap area of 10-5 (state 1) are changed into Ri(2.5,5,6,5,30,0°) and Rj(0,0,5,4,20,90°) (state 2). By Formula (5), we know that dij=ri+rj-OiOj≈1.52 for state 1, but dij=0 for state 2. So, dij in Definition 3 is discontinuous where dij=0 (i,j=1,2,…,n and i≠j). Similarly, d0i (i=1,2,…,n) in Definition 4 is also discontinuous (see Figure 6). Owing to their discontinuity, it is difficult to select an appropriate step length to obtain the feasible and compact layout scheme for the gradient iteration of CA-PSLS. Inspired by [41], Definitions 5 and 6 are given for the considered QPDAA.Figure 5
The embedded degree between two rectangles in the critical state.Figure 6
The embedded degree between the rectangle and container in the critical state.Definition 5.
For two rectanglesRi and Rj (θi,θj=0° or 90°, i,j=1,2,…,n and i≠j) (shown in Figure 7), let ri and rj be the radii of their circumscribed circles, respectively, and let dij denote their embedded degree; then dij can be calculated by
(7)dij=ri+rjlogai+aju2+logbi+bjv2+1,If0<u≤1,0<v≤10Otherwise.
In Formula (7), u=(ai+aj-2|xi-xj|)/(ai+aj), v=(bi+bj-2|yi-yj|)/(bi+bj). Here, if θi=0°, ai=li, aj=lj, bi=wi, and bj=wj (see Figure 7(a)); otherwise, ai=wi, aj=wj, bi=li, and bj=lj (see Figure 7(b)).Two cases of the embedded degree definition between two rectangles.
(a)
θ
i
-
θ
j
=
0
(b)
θ
i
-
θ
j
>
0In Formula (7), the embedded degree between two rectangles is the moving distance of the rectangle Rj from an overlap state with the stationary Ri to the separation state along the direction from the center (xi,yi) to the center (xj,yj). If Ri and Rj are two squares, and the center of Rj is on the diagonal line of Ri and enough close to its center (i.e., xi→xj and yi→yj), the moving distance of Rj from the initial state (shown in Figure 8(a)) to the separate state (shown in Figure 8(b)) along the direction of their diagonal lines is about ri+rj. Thus in the initial state, their embedded degree dij is close to the maximal value ri+rj. In addition, when 2|xi-xj|→ai+aj and/or 2|yi-yj|→bi+bj, u→0 and/or v→0. That is, dij→0.The geometric interpretation of definition of the embedded degree between two rectangles.
(a)
Initial state
(b)
Separation stateDefinition 6.
For the rectangleRi (θi=0° or 90°, i=1,2,…,n) and the circle container (0,0,Rc) as shown in Figure 7, let d0i denote the embedded degree between the rectangle Ri and container; then d0i can be calculated by
(8)d0i=xi+li22+yi+wi22-Rcxi+li22+yi+wi22>Rc0xi+li22+yi+wi22≤Rci=1,2,…,n.
The geometric interpretation of Definition6 is that when the farthest vertex of the rectangle Ri (i=1,2,…,n) from the coordinate origin is within the container, their embedded degree d0i=0; otherwise it is the length of the straight line segment pointed by d0i in Figure 9.Figure 9
The schematic diagram overlapped between the orthogonal rectangle and container.For embedded degree functions in Definitions3 and 5, their geometric figures are two curved semi-cone surfaces shown in Figures 10(a) and 10(b), respectively, where it is obvious that there is a gap between the semi-cone surface and xoy plane in Figure 10(a) but there is no gap between them in Figure 10(b). It is not difficult to assert that the difference of geometric figures of two embedded degree functions in Definitions 4 and 6 is the same as the above one. After describing Lemma 7, we propose properties of two embedded degree functions in Definitions 5 and 6, respectively.The curved semi-cone surface of the embedded degree of two orthogonal rectangles.
(a)
Definition3
(b)
Definition5Lemma 7.
If a binary functionf(x,y) is continuous for each variable in a domain, respectively, and is monotonous for the variable x or y, then the function f(x,y) is continuous in the domain.Property 1.
∀
i
,
j
∈
I
n, let Ri and Rj (i≠j and θi,θj=0° or 90°) be two rectangles, and the domain D={u≤1andv≤1}. Then dij(u,v) in Definition 5 is a continuous binary function in the domain D.Proof.
∀
i
,
j
∈
I
n and i≠j, set D1={(u,v)∣0<u≤1and0<v≤1}. From Definition 5, we know that the function dij(u,v) is continuous on both D1 and D-D1. Here, we prove that it is continuous on the domain D2{(u,v)∣(u,v)∈Dandu=0orv=0}.
For(u,v)∈D1,
(9)lim⁡u→0dij(u,v)=lim⁡u→0ri+rjlogai+aju2+logbi+bjv2+1=0.
Simultaneously,
(10)lim⁡v→0diju,v=lim⁡u→0,v→0diju,v=0foru,v∈D1.
This is because
(11)∂diju,v∂u=-ri+rjai+ajlogai+ajuuln⁡ai+ajlogai+aju2+logbi+bjv2+12>0foru,v∈D1.
According to Lemma7, the binary function dij(u,v) is continuous on the domain D2. Therefore, dij(u,v) is continuous on the domain D.Property 2.
∀
i
,
j
∈
I
n and i≠j, for the container with the radius Rc and rectangle Ri (θi=0° or 90°, i=1,2,…,n), set u=xi and v=yi; then the binary function d0i in Definition 6 is continuous on the domain D3{(u,v)∣-∞<u<+∞and-∞<v<+∞}.


### 3.2. Extruded Force and Energy Function

In order to quickly decrease the overlapping area of the rectangle packing system, we define the extruded forces between two rectangles and between the rectangle and container.Definition 8.
LetRi and Rj be two rectangles with the embedded degree dij (i,j=1,2,…,n and i≠j). Then the extruded force Fji→ between Ri and Rj is calculated by
(12)Fji→=αdjidji→dji→i,j=1,2,…,n,i≠j.Definition 9.
LetRi (i=1,2,…,n) and Rc denote the rectangle i and container. Then the extruded force F0i→ between Ri and Rc can be calculated by Formula (13), whose direction is the direction from the center of the container to the furthermost rectangular vertex (see Figure 6):
(13)F0i→=βd0id0i→d0i→i=1,2,…,n.
By experiments, we can know thatα>β.
So, the extruded resultant forceFi→ of Ri (i=1,2,…,n) in the rectangle packing scheme can be calculated by
(14)Fi→=∑j=0,i≠jnFji→.Definition 10.
LetEji and E0i (i,j=1,2,…,n and i≠j) denote extruded potential energies of Ri with respect to Rj and the container, respectively. Then Eji can be calculated by Formula (15), where dij and di0 denote two embedded degrees between two rectangles Ri and Rj and between the rectangles Ri and container:
(15)Eji=dji2i=1,2,…,n,j=0,1,…,n,i≠j.Definition 11.
The total extruded potential energyEi of Ri can be calculated by
(16)Ei=∑j=0,j≠inEjii,j=1,2,…,n,i≠j.
LetSi be the area of the rectangle Ri; then Ei and Ei/Si (i=1,2,…,n) are its absolute and relative extruded potential energies, respectively.


### 3.3. Compact and Feasible Solution Strategy

By predetermining envelope radiusR0 of this problem, the extruded force and direction can be calculated by Formula (13). The extruded force of the envelope circle makes each rectangle close to the center of the container in the direction. For each rectangle, the extruded forces of all others with respect to the rectangle drive away themselves to relieve the pressure in respective direction and their extruded resultant force is calculated by Formula (12). In this paper, the above two steps are used to decrease the overlapping area of the packing scheme and make it compact.


## 3.1. Embedded Degree Function and Related Properties

Xu et al. [34] defined the embedded degrees between two rectangles and between the rectangle and container by Definitions 3 and 4, respectively.Definition 3.
Letri′ and rj′ (i,j=1,2,…,n and i≠j) denote the radii of the circumscribed circles of two rectangles Ri and Rj, respectively, and dij (see Figure 4(a)) the embedded degree between them (see Figure 4(a)); then dij can be calculated by
(5)dij=ri′+rj′-xi-xj2+yi-yj2ifRiandRjoverlapi,j=1,2,…,n,i≠j0otherwise.Two embedded degree definitions in [34].
(a)
The embedded degree between two rectangles
(b)
The embedded degree between the rectangle and containerDefinition 4.
LetRc and ri′ (i=1,2,…,n) denote the radii of the container and circumscribed circle of the rectangle Ri, respectively, and d0i (see Figure 4(b)) the embedded degree between the rectangle and container; then d0i can be calculated by
(6)d0i=xi2+yi2+ri′-RcifRioverlapwiththecontaineri=1,2,…,n0otherwise.Both of the above two embedded degree functions are discontinuous in the critical state from overlapping to separating, as has been discussed by Stoyan and Yaskov [41]. For example, as shown in Figure 5, by moving one rectangle along a direction, two rectangles with the overlap area of 10-5 (state 1) are changed into Ri(2.5,5,6,5,30,0°) and Rj(0,0,5,4,20,90°) (state 2). By Formula (5), we know that dij=ri+rj-OiOj≈1.52 for state 1, but dij=0 for state 2. So, dij in Definition 3 is discontinuous where dij=0 (i,j=1,2,…,n and i≠j). Similarly, d0i (i=1,2,…,n) in Definition 4 is also discontinuous (see Figure 6). Owing to their discontinuity, it is difficult to select an appropriate step length to obtain the feasible and compact layout scheme for the gradient iteration of CA-PSLS. Inspired by [41], Definitions 5 and 6 are given for the considered QPDAA.Figure 5
The embedded degree between two rectangles in the critical state.Figure 6
The embedded degree between the rectangle and container in the critical state.Definition 5.
For two rectanglesRi and Rj (θi,θj=0° or 90°, i,j=1,2,…,n and i≠j) (shown in Figure 7), let ri and rj be the radii of their circumscribed circles, respectively, and let dij denote their embedded degree; then dij can be calculated by
(7)dij=ri+rjlogai+aju2+logbi+bjv2+1,If0<u≤1,0<v≤10Otherwise.
In Formula (7), u=(ai+aj-2|xi-xj|)/(ai+aj), v=(bi+bj-2|yi-yj|)/(bi+bj). Here, if θi=0°, ai=li, aj=lj, bi=wi, and bj=wj (see Figure 7(a)); otherwise, ai=wi, aj=wj, bi=li, and bj=lj (see Figure 7(b)).Two cases of the embedded degree definition between two rectangles.
(a)
θ
i
-
θ
j
=
0
(b)
θ
i
-
θ
j
>
0In Formula (7), the embedded degree between two rectangles is the moving distance of the rectangle Rj from an overlap state with the stationary Ri to the separation state along the direction from the center (xi,yi) to the center (xj,yj). If Ri and Rj are two squares, and the center of Rj is on the diagonal line of Ri and enough close to its center (i.e., xi→xj and yi→yj), the moving distance of Rj from the initial state (shown in Figure 8(a)) to the separate state (shown in Figure 8(b)) along the direction of their diagonal lines is about ri+rj. Thus in the initial state, their embedded degree dij is close to the maximal value ri+rj. In addition, when 2|xi-xj|→ai+aj and/or 2|yi-yj|→bi+bj, u→0 and/or v→0. That is, dij→0.The geometric interpretation of definition of the embedded degree between two rectangles.
(a)
Initial state
(b)
Separation stateDefinition 6.
For the rectangleRi (θi=0° or 90°, i=1,2,…,n) and the circle container (0,0,Rc) as shown in Figure 7, let d0i denote the embedded degree between the rectangle Ri and container; then d0i can be calculated by
(8)d0i=xi+li22+yi+wi22-Rcxi+li22+yi+wi22>Rc0xi+li22+yi+wi22≤Rci=1,2,…,n.
The geometric interpretation of Definition6 is that when the farthest vertex of the rectangle Ri (i=1,2,…,n) from the coordinate origin is within the container, their embedded degree d0i=0; otherwise it is the length of the straight line segment pointed by d0i in Figure 9.Figure 9
The schematic diagram overlapped between the orthogonal rectangle and container.For embedded degree functions in Definitions3 and 5, their geometric figures are two curved semi-cone surfaces shown in Figures 10(a) and 10(b), respectively, where it is obvious that there is a gap between the semi-cone surface and xoy plane in Figure 10(a) but there is no gap between them in Figure 10(b). It is not difficult to assert that the difference of geometric figures of two embedded degree functions in Definitions 4 and 6 is the same as the above one. After describing Lemma 7, we propose properties of two embedded degree functions in Definitions 5 and 6, respectively.The curved semi-cone surface of the embedded degree of two orthogonal rectangles.
(a)
Definition3
(b)
Definition5Lemma 7.
If a binary functionf(x,y) is continuous for each variable in a domain, respectively, and is monotonous for the variable x or y, then the function f(x,y) is continuous in the domain.Property 1.
∀
i
,
j
∈
I
n, let Ri and Rj (i≠j and θi,θj=0° or 90°) be two rectangles, and the domain D={u≤1andv≤1}. Then dij(u,v) in Definition 5 is a continuous binary function in the domain D.Proof.
∀
i
,
j
∈
I
n and i≠j, set D1={(u,v)∣0<u≤1and0<v≤1}. From Definition 5, we know that the function dij(u,v) is continuous on both D1 and D-D1. Here, we prove that it is continuous on the domain D2{(u,v)∣(u,v)∈Dandu=0orv=0}.
For(u,v)∈D1,
(9)lim⁡u→0dij(u,v)=lim⁡u→0ri+rjlogai+aju2+logbi+bjv2+1=0.
Simultaneously,
(10)lim⁡v→0diju,v=lim⁡u→0,v→0diju,v=0foru,v∈D1.
This is because
(11)∂diju,v∂u=-ri+rjai+ajlogai+ajuuln⁡ai+ajlogai+aju2+logbi+bjv2+12>0foru,v∈D1.
According to Lemma7, the binary function dij(u,v) is continuous on the domain D2. Therefore, dij(u,v) is continuous on the domain D.Property 2.
∀
i
,
j
∈
I
n and i≠j, for the container with the radius Rc and rectangle Ri (θi=0° or 90°, i=1,2,…,n), set u=xi and v=yi; then the binary function d0i in Definition 6 is continuous on the domain D3{(u,v)∣-∞<u<+∞and-∞<v<+∞}.


## 3.2. Extruded Force and Energy Function

In order to quickly decrease the overlapping area of the rectangle packing system, we define the extruded forces between two rectangles and between the rectangle and container.Definition 8.
LetRi and Rj be two rectangles with the embedded degree dij (i,j=1,2,…,n and i≠j). Then the extruded force Fji→ between Ri and Rj is calculated by
(12)Fji→=αdjidji→dji→i,j=1,2,…,n,i≠j.Definition 9.
LetRi (i=1,2,…,n) and Rc denote the rectangle i and container. Then the extruded force F0i→ between Ri and Rc can be calculated by Formula (13), whose direction is the direction from the center of the container to the furthermost rectangular vertex (see Figure 6):
(13)F0i→=βd0id0i→d0i→i=1,2,…,n.
By experiments, we can know thatα>β.
So, the extruded resultant forceFi→ of Ri (i=1,2,…,n) in the rectangle packing scheme can be calculated by
(14)Fi→=∑j=0,i≠jnFji→.Definition 10.
LetEji and E0i (i,j=1,2,…,n and i≠j) denote extruded potential energies of Ri with respect to Rj and the container, respectively. Then Eji can be calculated by Formula (15), where dij and di0 denote two embedded degrees between two rectangles Ri and Rj and between the rectangles Ri and container:
(15)Eji=dji2i=1,2,…,n,j=0,1,…,n,i≠j.Definition 11.
The total extruded potential energyEi of Ri can be calculated by
(16)Ei=∑j=0,j≠inEjii,j=1,2,…,n,i≠j.
LetSi be the area of the rectangle Ri; then Ei and Ei/Si (i=1,2,…,n) are its absolute and relative extruded potential energies, respectively.


## 3.3. Compact and Feasible Solution Strategy

By predetermining envelope radiusR0 of this problem, the extruded force and direction can be calculated by Formula (13). The extruded force of the envelope circle makes each rectangle close to the center of the container in the direction. For each rectangle, the extruded forces of all others with respect to the rectangle drive away themselves to relieve the pressure in respective direction and their extruded resultant force is calculated by Formula (12). In this paper, the above two steps are used to decrease the overlapping area of the packing scheme and make it compact.


## 4. Dynamic Adjustment Strategy

Considering the problem of the low efficiency and possible local optimum (e.g., large static imbalance) of the iteration of two steps in Section3.3, we propose Property 3 and dynamic adjustment strategy for QPDAA.


### 4.1. Related Property

For optimizing the static imbalance of the layout scheme, we introduce Property3.Property 3.
AssumeA1(xm,ym) is the mass center of an orthogonal packing scheme X1 of this problem and A1(xm,ym)≠(0,0) and X2 is another scheme obtained by interchanging centers of two rectangles Ri with a mass mi and Rj (i,j∈In and i≠j) with a mass mj in X1. If mj>mi, dj>di, centers (xi,yi) and (xi,yi) satisfy Formula (17), then J(X1)>J(X2), where dk=(xk2+yk2)1/2 (k=i,j):
(17)2xj-xixm∑k=1nmk+2yj-yiym∑k=1nmk>mj-midij2.
In Formula (17), dij=((xj-xi)2+(yj-yi)2)1/2.Proof .
Consider(18)∵J2X1=∑k=1nmkxk2+∑k=1nmkyk2J2X2=∑k=1nmkxk-mixi-mjxj+mixj+mjxi2+∑k=1nmkyk-miyi-mjyj+miyj+mjyi2∴J2X1-J2X2=mixi+mjxj-mixj-mjxi×2∑k=1nmkxk-mixi-mjxj+mixj+mjxi+miyi+mjyj-miyj-mjyi×2∑k=1nmkyk-miyi-mjyj+miyj+mjyi2=mi-mjxi-xj×2xm∑k=1nmkxk-mi-mjxi-xj+mi-mjyi-yj×2ym∑k=1nmkyk-mi-mjyi-yj=2(xj-xi)xm∑k=1nmk+2(yj-yi)ym∑k=1nmk-(mj-mi)dij2>0.
Property3 indicates that, for selecting rectangle Ri∈X1, we can find a rectangle Rj in the sector area A1OA2 with an angle φ (shown as in Figure 11) and interchange them to obtain X2 whose static imbalance is less than X1. Here, the angle φ satisfies
(19)2∑k=1nmkxm2+ym21/2xj-xi2+yj-yi21/2cos⁡(φ)=mj-midij2.Figure 11
The geometric area of Formula (17).


### 4.2. Dynamic Adjustment Strategy

LetX=(xk,yk,θk∣k=1,2,…,n); we consider the following dynamic adjustment strategy.


#### 4.2.1. Rectangle-Interchanging

According to Property3, the static imbalance of the packing scheme can be decreased by interchanging positions of two rectangles.Two rectangles,Ri with a smaller mass and Rj with a larger mass (i,j∈In,di<0.5R0,0.5R0<dj<R0), are selected from X. If Ri and Rj satisfy Formula (17), then we update X by xi↔xj, yi↔yj, θi↔θj.


#### 4.2.2. Rotation and Off-Trap

(i) A rectangle with a larger pain degree is found out fromX and is rotated 90° round its center counterclockwise direction to relieve its pain. (ii) A rectangle with a larger pain degree is found out from X and is moved to such a place in the container where its pain degree is smaller. We know that the role of (ii) is similar to a construction of the nonisomorphic layout pattern [42, 43].


#### 4.2.3. Center Translation

If its mass centerPm(xm,ym)≠O(0,0), then X=(xk-xm,yk-ym,θk∣k=1,2,…,n).


## 4.1. Related Property

For optimizing the static imbalance of the layout scheme, we introduce Property3.Property 3.
AssumeA1(xm,ym) is the mass center of an orthogonal packing scheme X1 of this problem and A1(xm,ym)≠(0,0) and X2 is another scheme obtained by interchanging centers of two rectangles Ri with a mass mi and Rj (i,j∈In and i≠j) with a mass mj in X1. If mj>mi, dj>di, centers (xi,yi) and (xi,yi) satisfy Formula (17), then J(X1)>J(X2), where dk=(xk2+yk2)1/2 (k=i,j):
(17)2xj-xixm∑k=1nmk+2yj-yiym∑k=1nmk>mj-midij2.
In Formula (17), dij=((xj-xi)2+(yj-yi)2)1/2.Proof .
Consider(18)∵J2X1=∑k=1nmkxk2+∑k=1nmkyk2J2X2=∑k=1nmkxk-mixi-mjxj+mixj+mjxi2+∑k=1nmkyk-miyi-mjyj+miyj+mjyi2∴J2X1-J2X2=mixi+mjxj-mixj-mjxi×2∑k=1nmkxk-mixi-mjxj+mixj+mjxi+miyi+mjyj-miyj-mjyi×2∑k=1nmkyk-miyi-mjyj+miyj+mjyi2=mi-mjxi-xj×2xm∑k=1nmkxk-mi-mjxi-xj+mi-mjyi-yj×2ym∑k=1nmkyk-mi-mjyi-yj=2(xj-xi)xm∑k=1nmk+2(yj-yi)ym∑k=1nmk-(mj-mi)dij2>0.
Property3 indicates that, for selecting rectangle Ri∈X1, we can find a rectangle Rj in the sector area A1OA2 with an angle φ (shown as in Figure 11) and interchange them to obtain X2 whose static imbalance is less than X1. Here, the angle φ satisfies
(19)2∑k=1nmkxm2+ym21/2xj-xi2+yj-yi21/2cos⁡(φ)=mj-midij2.Figure 11
The geometric area of Formula (17).


## 4.2. Dynamic Adjustment Strategy

LetX=(xk,yk,θk∣k=1,2,…,n); we consider the following dynamic adjustment strategy.


### 4.2.1. Rectangle-Interchanging

According to Property3, the static imbalance of the packing scheme can be decreased by interchanging positions of two rectangles.Two rectangles,Ri with a smaller mass and Rj with a larger mass (i,j∈In,di<0.5R0,0.5R0<dj<R0), are selected from X. If Ri and Rj satisfy Formula (17), then we update X by xi↔xj, yi↔yj, θi↔θj.


### 4.2.2. Rotation and Off-Trap

(i) A rectangle with a larger pain degree is found out fromX and is rotated 90° round its center counterclockwise direction to relieve its pain. (ii) A rectangle with a larger pain degree is found out from X and is moved to such a place in the container where its pain degree is smaller. We know that the role of (ii) is similar to a construction of the nonisomorphic layout pattern [42, 43].


### 4.2.3. Center Translation

If its mass centerPm(xm,ym)≠O(0,0), then X=(xk-xm,yk-ym,θk∣k=1,2,…,n).


## 4.2.1. Rectangle-Interchanging

According to Property3, the static imbalance of the packing scheme can be decreased by interchanging positions of two rectangles.Two rectangles,Ri with a smaller mass and Rj with a larger mass (i,j∈In,di<0.5R0,0.5R0<dj<R0), are selected from X. If Ri and Rj satisfy Formula (17), then we update X by xi↔xj, yi↔yj, θi↔θj.


## 4.2.2. Rotation and Off-Trap

(i) A rectangle with a larger pain degree is found out fromX and is rotated 90° round its center counterclockwise direction to relieve its pain. (ii) A rectangle with a larger pain degree is found out from X and is moved to such a place in the container where its pain degree is smaller. We know that the role of (ii) is similar to a construction of the nonisomorphic layout pattern [42, 43].


## 4.2.3. Center Translation

If its mass centerPm(xm,ym)≠O(0,0), then X=(xk-xm,yk-ym,θk∣k=1,2,…,n).


## 5. The Proposed Algorithm

Through an organic combination of the compact and feasible solution strategy and dynamic adjustment strategy, we present QPDAA for BCOURP.LetR0 and r* be the predetermined value and an allowable maximum of the envelope radius of the solution, respectively; n is the number of rectangles. Pm(xm,ym), f(X), and E(X) denote the mass center, envelope radius, and extruded potential energy of the packing scheme X, respectively. Ek(X) (k=1,2,…,n) is the extruded potential energy of the rectangle Rk; h is the step length; N is the maximum translation times. Then steps of the proposed QPDAA are shown in Algorithm 1.Algorithm 1
DefiniteX, X1, X2, R0, r*, h, ε, k, j, N, α, β, δ and initialize δ=6, h=0.8, ε=10-20, α=18, β=56, k=0, j=0, N=120;
Do
{
Randomly generateX1 with the envelope radius R0 and calculate E(X1); j=0;
If(E(X1)<ε)
Continue;
Else break;
While (1)
{   Do
{  j=j+1; for i=1,2,…,n, calculate Fi→ of Ri and X2i=X1i+h·Fi→;
CalculateE(X2) and f(X2);
If (E(X2)<ε and f(X2)≤r*) {X=X2;j=N+1}
Else if(E(X2)≥ε){Calculate|∇E|=((1/n)∑i=1n∣Fji→∣2)1/2;X1=X2;}
Else if (f(X2)>r*)  {j=-1; break;}
} While (|∇E| <  1 and j<N);
If (j=-1 or j>N) break;
If (J(X2)>δ) find Ri and Rj which satisfy Formula (17) in X2 and xi↔xj, yi↔yj, θi↔θj;
Find p so that Ep(X2)/Sp=max⁡{Ei(X2)/Si,i=1,2,…,n};
If (k≠p) {by rotating Rp, X1 is obtained;
If (Ep(X1)>0.75Ep(X2)) update  X1 by moving (xp,yp), k=p;}
Else find q so that Eq(X2)=min⁡{Ei(X2),i=1,2,…,n}, and update  X1 by rotating Rp;
If (Eq(X1)>0.75Eq(X2)), update X1 by moving (xq,yq) out, k=q;
}
} while (f(X1)>r*);
Calculate the mass centerPm(xm,ym), and X=(xk-xm,yk-ym,θk∣k=1,2,…,n), and calculate f(X);
Output the layout schemeX and envelope radius f(X);
End the algorithm.


## 6. Experiments and Analysis

### 6.1. Experiments

The proposed QPDAA is coded in VC++ 6.0 and carried on a Pentium 3 GHZ PC with 512 MB memory. CA-PSLS [34], GA-HA [35] are coded in VC++ 6.0 and two algorithms are carried on a Pentium 1.83 GHZ with 512 MB memory; IGA [44] is carried on an IBM 586 166 MHz.Experiment 1.
Five examples are taken from [33, 35] and are used in testing the performance of the proposed QPDAA. Data of all examples are shown in Table 1. For the proposed algorithm, we take α=18, β=56, ε=10-20, h=0.8, δ=6, and N=120, respectively. For Examples 1–5, we take R0 = 11.4, 14.3, 17.5, 22.3, and 115.5 and take r*=1.05R0, 1.05R0, 1.07R0, 1.07R0, and 1.05R0, respectively. Running the proposed QPDAA 30 times for each example (the success rate is 100%), we show its average running time, average envelope radius, standard variance of the radius, and the maximum and minimum envelope radii in Table 2; for each example, its layout scheme diagraph is shown in Figure 12; the other data in Table 2 is taken from [33–35]. The optimal layout schemes of the proposed QPDAA are shown in Tables 3, 4, 5, and 6 for 5 examples.Table 1
Parameters of rectangles for five layout examples.
Example  1
(length, width, mass)  (8, 6, 12), (8, 8, 16), (10, 6, 15), (12, 4, 12), (6, 6, 9)
Example 2
(length, width, mass)  (8, 6, 12), (8, 8, 16), (10, 6, 15), (10, 8, 20), (10, 10, 25), (12, 6, 18)
Example 3
(length, width, mass)  (8, 6, 12), (8, 8, 16), (10, 6, 15), (10, 8, 20), (10, 10, 25), (12, 6, 18), (12, 4, 12), (12, 8, 24) (12, 10, 30)
Example 4
(length, width, mass)  (8, 5, 10), (4, 8, 8), (10, 6, 15), (7, 8, 14), (10, 3, 7.5), (12, 6, 18), (12, 4, 12), (12, 6, 18), (8, 10, 20), (7, 3, 6), (8, 6, 6), (8, 3, 15), (10, 6, 20), (10, 8, 17.5), (10, 7, 15), (12, 5, 15), (12, 4, 12), (10, 8, 20), (12, 10, 30), (6, 6, 9)
Example 5
(length, width, mass)  (26, 26, 8), (22, 28, 16), (20, 30, 16), (20, 34, 15), (34, 22, 17), (20, 32, 15), (30, 20, 14), (28, 26, 15),(20, 28, 14), (26, 38, 13), (34, 30, 12), (26, 36, 17), (30, 34, 12), (28, 24, 17) (32, 24, 10), (30, 38, 11), (30, 20, 18), (22, 22, 17), (30, 32, 11), (28, 28, 10), (20, 38, 18), (22, 30, 13) (32, 32, 14), (26, 26, 17), (34, 20, 14), (26, 32, 18), (38, 22, 19), (36, 34, 18), (36, 24, 13), (26, 30, 15) (26, 38, 12), (30, 38, 19), (28, 24, 15), (38, 34, 19), (26, 20, 14), (32, 36, 16), (28, 22, 13), (24, 28, 19), (38, 22, 17), (20, 38, 16)Table 2
Performance comparisons of four algorithms.
Example number
Size
Algorithm
Averager
Standard deviation
Minimalr
Maximalr
Averaget/s
1
5
GA + HA [35]
11.7703
0.0335
11.7597
11.8655
0.242
CA-PSLS [34]
12.2181
0.5214
11.5443
13.0982
11.657
QPDAA
11.6756
0.0235
11.4737
11.8533
0.953
2
6
IGA [44]
—
—
14.62000
—
18.000
CA-PSLS [34]
15.19402
—
14.39625
—
19.904
QPDAA
14.68374
—
14.344996
14.909841
4.963
3
9
GA + HA [35]
18.1709
0.2361
17.8988
18.6041
1.262
CA-PSLS [34]
20.0899
1.1957
18.3758
22.0803
58.126
QPDAA
18.2461
0.0694
17.6880
18.5983
1.110
4
20
GA + HA [35]
23.2713
0.4728
22.6396
24.0605
9.989
CA-PSLS [34]
32.7216
4.0065
27.2863
38.5048
321.071
QPDAA
22.8368
0.0222
22.3510
23.7884
2.625
5
40
GA [35]
119.2396
1.5087
115.836
120.7099
62.795
CA-PSLS [34]
253.4165
43.8096
195.5914
306.2740
1367.573
QPDAA
119.1383
0.6887
115.6252
120.5102
3.375Table 3
The layout schemes of the proposed QPDAA for Examples  1 and  2.
Example  1
Example  2
i
x
i
y
i
i
x
i
y
i
1
5.017966
−4.093750
1
−5.810001
−7.386930
2
4.932835
2.906250
2
5.686532
6.537550
3
−3.982034
−4.093750
3
8.827469
−0.519116
4
−5.067165
0.906250
4
3.371405
−7.538003
5
−2.067165
5.906250
5
−3.346021
6.667169
6
−7.636339
−1.338337Table 4
The layout schemes of the proposed QPDAA for Example  3.
i
x
i
y
i
1
0.074698
−3.832386
2
2.329571
3.285391
3
4.944505
−10.373944
4
3.514680
11.503878
5
11.343280
1.762618
6
−6.074076
−9.903838
7
10.077353
−5.359918
8
−10.295647
−2.839607
9
−7.690402
6.187573Table 5
The layout scheme of the proposed QPDAA for Example  4.
i
x
i
y
i
1
2.275791
−8.061370
2
0.693375
15.930070
3
8.143939
8.438630
4
−4.806625
15.930070
5
−5.021757
−17.061370
6
5.978243
−15.573636
7
0.275791
−3.561370
8
−12.856061
7.930070
9
−5.724209
−10.561370
10
6.193375
17.938630
11
−16.608718
1.930070
12
7.143939
3.938630
13
−7.608718
1.930070
14
16.143939
1.426364
15
−1.856061
8.430070
16
9.143939
13.938630
17
3.391282
0.438630
18
−14.724209
−5.069930
19
12.275791
−7.573636
20
−12.724209
−12.069930Table 6
The layout scheme of the proposed QPDAA for Example  5.
i
x
i
y
i
1
−20.484058
−97.670716
2
96.802177
−23.135827
3
−32.957579
−3.670716
4
−17.484058
−67.670716
5
−34.765848
92.329284
6
−16.197823
−34.670716
7
49.515942
−85.946702
8
−5.847798
30.463901
9
24.515942
−86.536099
10
−55.957579
−24.941525
11
−93.957579
1.531453
12
22.042421
4.053298
13
23.234152
85.053298
14
71.802177
−25.946702
15
−71.484058
−59.468547
16
92.042421
9.864173
17
23.152202
57.053298
18
3.515942
−83.536099
19
−32.847798
65.329284
20
−41.484058
−57.941525
21
−32.957579
30.329284
22
66.042421
1.053298
23
9.802177
−56.536099
24
−4.765848
88.463901
25
−59.957579
4.058475
26
−4.847798
59.463901
27
12.802177
−29.536099
28
−86.957579
−30.468547
29
52.515942
−63.946702
30
−64.765848
69.531453
31
44.802177
−32.946702
32
−85.957579
35.531453
33
86.152202
40.864173
34
57.234152
69.864173
35
21.152202
32.053298
36
−6.957579
−0.536099
37
−56.957579
25.058475
38
−45.484058
−85.941525
39
53.152202
35.053298
40
45.042421
5.053298The layout diagraphs of five examples for the proposed QPDAA.
(a)
(b)
(c)
(d)
(e)Experiment 2.
For testing the effects ofR0 and r* on the minimal radius and running time with the proposed QPDAA, we take another set of R0 and r* (five examples and other parameters are the same as those of  Experiment 1) and run the proposed QPDAA procedure 30 times for each example. The minimal radii and running times are given in Table 7. Their layout schemes and layout diagraphs are shown in Tables 8, 9, 10, and 11 and Figure 13. It can be found from Table 7 that changing values of R0 and r* we can obtain the packing scheme with a smaller envelop radius, but it costs more time for each example. So, values R0 and r* in Experiment 1 can be applied to make a tradeoff between the computational effectiveness and solution quality.Table 7
The effect of parametersR0 and r* on the optimal radius and running time for the proposed QPDAA.
Experiment number
1
2
3
4
5
Size
5
6
9
20
40
R
0
11.4
14.3
17.5
22.3
115.5
r
*
1.05R0
1.05R0
1.07R0
1.07R0
1.05R0
The optimal radius
11.4737
14.344996
17.6880
22.3510
115.6252
Running time
0.953
3.5872
1.110
2.625
2.625
R
0
11.4
14.3
17.5
22.06
114.8
r
*
1.02R0
1.02R0
1.03R0
1.01R0
1.01R0
The optimal radius
11.450458
14.309924
17.597856
22.141009
115.042385
Running time
1.297
8.963
7.906
12.920
17.125Table 8
The optimal layout schemes of Examples  1 and  2 for the proposed QPDAA.
i
x
i
y
i
i
x
i
y
i
1
−2.954693
−5.470039
1
4.948526
8.054106
2
5.045307
−2.429991
2
4.903437
−6.945894
3
−2.408844
4.570009
3
−4.140424
−8.010294
4
−4.954693
−0.429991
4
5.911271
1.054106
5
5.591156
4.570009
5
−4.088729
5.989706
6
−5.096563
−2.010294Table 9
The optimal layout schemes of Example  3 for the proposed QPDAA.
i
x
i
y
i
1
8.952825
−8.127957
2
11.192355
3.872043
3
−11.893145
0.866506
4
−7.807645
7.896834
5
−7.161996
−7.133494
6
11.084588
−2.235259
7
−0.893145
0.866506
8
1.838004
−10.127957
9
2.125081
10.168689Table 10
The optimal layout scheme of Example  4 for the proposed QPDAA.
i
x
i
y
i
1
−7.913018
−16.1629110
2
−11.4301555
13.766710
3
−2.797531
7.599405
4
14.854397
8.176985
5
3.751568
4.136671
6
−14.476432
−7.582581
7
13.305438
−9.941647
8
−8.088653
−7.608034
9
3.747621
15.611128
10
−2.290583
−18.311460
11
−5.543514
1.554382
12
11.758080
13.883226
13
−14.800586
1.537640
14
16.662225
0.074950
15
−3.889690
15.762332
16
−13.867726
7.136671
17
−2.96.2478
−7.489430
18
6.210196
−4.937357
19
5.257463
−14.032250
20
8.273430
7.563706Table 11
The optimal layout scheme of Example  5 for the proposed QPDAA.
i
x
i
y
i
1
−35.716569
−20.219336
2
19.295868
92.929139
3
−66.464390
−69.791544
4
−0.799905
−80.612101
5
−8.704132
97.929139
6
−38.754325
−49.219336
7
60.543358
20.832873
8
47.933196
−29.082316
9
−42.456642
21.911290
10
−6.576451
43.929139
11
4.543358
7.350623
12
60.568942
−69.995791
13
−74.792262
52.886007
14
57.004507
44.832873
15
33.5433588
0.917684
16
97.933196
−2.928148
17
71.933196
−4.167127
18
14.886008
67.929139
19
−41.5764518
50.911290
20
−93.27781098
23.736930
21
−67.7165699
−2.088710
22
90.543358
27.071852
23
−41.704132
81.911290
24
−65.456642
20.911290
25
−58.7543259
−29.088710
26
28.423549
35.350623
27
0.535610
−101.612101
28
48.2958689
75.832873
29
−80.754325
−36.263070
30
−9.113992
71.929139
31
28.245675
−56.649377
32
79.933196
−36.928148
33
81.004507
52.071852
34
−37.464390
−82.649377
35
29.200095
−79.649377
36
−6.716569
−25.649377
37
20.283431
−29.082316
38
−98.716569
−4.263070
39
−9.754325
−54.649377
40
−22.456642
11.780664The optimal layout scheme diagraphs of five examples for the proposed QPDAA.
(a)
(b)
(c)
(d)
(e)In order to further test the effectiveness of the proposed QPDAA, we consider Experiment3.Experiment 3.
Numbers of rectangles (generated randomly) of three examples are 50, 55, and 60 and their lengths and widths are between 20 and 40. For the proposed QPDAA, we takeα=18, β=56, ε=10-20, h=0.8, δ=10, N=120, R0 = 125.9, 133.8, 137.2, and r* = 126.8, 134.6, 138.8 for Examples 1–3, respectively. For GA + HA, the population size, mutation probability, and max number of the iteration are 30, 0.125, and 50, respectively. By running HA + GA and the proposed QPDAA 30 times for three examples, respectively, their optimal envelop radii and average times are shown in Table 12, respectively. The optimal packing scheme diagrams of GA + HA and the proposed QPDAA are shown in Figures 14(a)–14(c) and Figures 14(d)–14(f). We can know from Table 12 that both the solution quality and computational quality of the proposed QPDAA are obviously higher than those of GA + HA.Table 12
The effect ofR0 and r* on the optimal radius and running time for the proposed QPDAA.
Example number
Size
HA + GA
QPDAA
The optimal radius
Running time (s)
The optimal radius
Running time (s)
1
50
127.667244
30.170088
126.567311
13.345431
2
55
134.844782
42.654031
134.105091
19.056438
3
60
139.072606
66.908203
137.833657
37.01790Packing scheme diagrams of GA + HA and the proposed QPDAA for Experiment3.
(a)
GA_HA for 50 rectangles
(b)
GA_HA for 55 rectangles
(c)
GA_HA for 60 rectangles
(d)
QPDAA for 50 rectangles
(e)
QPDAA for 55 rectangles
(f)
QPDAA for 60 rectanglesNote that, in Experiment3, the procedure of GA + HA is coded by author and is carried on a Pentium 3 GHZ with 512 MB memory.


### 6.2. Analysis

From data of Tables2, 7, and 12, we know that the solution quality of the proposed QPDAA algorithm is higher than those of CA-PSLS and GA-HA. Compared with those of CA-PSLS, embedded degree functions of the proposed QPDAA can make the layout scheme more compact. Due to the fixed candidate positions of GA + HA, it is difficult to find the best position for some rectangles close to the marginal region of the container. The deficiency of a mechanism of decreasing the static balance in the process of packing rectangles also limits the solution quality of GA + HA. The experimental results illustrate the effectiveness of the proposed QPDAA.The computational efficiency of the proposed QPDAA is one magnitude higher than those of CA-PSLS. There are two reasons. (i) Owing to orthogonal packing, searching the optimal solution in the 2D solution of the proposed QPDAA is easier than that in the 3D solution space of CA-PSLS. (ii) In order to improve the solution quality of CA-PSLS, PSO is used to optimize the feasible solution obtained through the gradient method based on two discontinuous embedded degree functions, but the proposed QPDAA need not do the PSO optimization without reducing its solution quality. Except for Example 1, the computational efficiency of the proposed QPDAA is higher than that of GA + HA. And with the increase of the size of the packing problem, the advantage of the proposed QPDAA is more obvious. This is because computational complexities of the extruded resultant force and potential energy areO(n) in this paper, but the computational complexity of noninterference judgment is O(n2). In addition, for GA + HA, with the increasing of the number of rectangles, the number of candidate positions of each rectangle increases dramatically. These reasons lead to the computational efficiency of the proposed QPDAA higher than that of GA + HA for the BCOURP with a large size.


## 6.1. Experiments

The proposed QPDAA is coded in VC++ 6.0 and carried on a Pentium 3 GHZ PC with 512 MB memory. CA-PSLS [34], GA-HA [35] are coded in VC++ 6.0 and two algorithms are carried on a Pentium 1.83 GHZ with 512 MB memory; IGA [44] is carried on an IBM 586 166 MHz.Experiment 1.
Five examples are taken from [33, 35] and are used in testing the performance of the proposed QPDAA. Data of all examples are shown in Table 1. For the proposed algorithm, we take α=18, β=56, ε=10-20, h=0.8, δ=6, and N=120, respectively. For Examples 1–5, we take R0 = 11.4, 14.3, 17.5, 22.3, and 115.5 and take r*=1.05R0, 1.05R0, 1.07R0, 1.07R0, and 1.05R0, respectively. Running the proposed QPDAA 30 times for each example (the success rate is 100%), we show its average running time, average envelope radius, standard variance of the radius, and the maximum and minimum envelope radii in Table 2; for each example, its layout scheme diagraph is shown in Figure 12; the other data in Table 2 is taken from [33–35]. The optimal layout schemes of the proposed QPDAA are shown in Tables 3, 4, 5, and 6 for 5 examples.Table 1
Parameters of rectangles for five layout examples.
Example  1
(length, width, mass)  (8, 6, 12), (8, 8, 16), (10, 6, 15), (12, 4, 12), (6, 6, 9)
Example 2
(length, width, mass)  (8, 6, 12), (8, 8, 16), (10, 6, 15), (10, 8, 20), (10, 10, 25), (12, 6, 18)
Example 3
(length, width, mass)  (8, 6, 12), (8, 8, 16), (10, 6, 15), (10, 8, 20), (10, 10, 25), (12, 6, 18), (12, 4, 12), (12, 8, 24) (12, 10, 30)
Example 4
(length, width, mass)  (8, 5, 10), (4, 8, 8), (10, 6, 15), (7, 8, 14), (10, 3, 7.5), (12, 6, 18), (12, 4, 12), (12, 6, 18), (8, 10, 20), (7, 3, 6), (8, 6, 6), (8, 3, 15), (10, 6, 20), (10, 8, 17.5), (10, 7, 15), (12, 5, 15), (12, 4, 12), (10, 8, 20), (12, 10, 30), (6, 6, 9)
Example 5
(length, width, mass)  (26, 26, 8), (22, 28, 16), (20, 30, 16), (20, 34, 15), (34, 22, 17), (20, 32, 15), (30, 20, 14), (28, 26, 15),(20, 28, 14), (26, 38, 13), (34, 30, 12), (26, 36, 17), (30, 34, 12), (28, 24, 17) (32, 24, 10), (30, 38, 11), (30, 20, 18), (22, 22, 17), (30, 32, 11), (28, 28, 10), (20, 38, 18), (22, 30, 13) (32, 32, 14), (26, 26, 17), (34, 20, 14), (26, 32, 18), (38, 22, 19), (36, 34, 18), (36, 24, 13), (26, 30, 15) (26, 38, 12), (30, 38, 19), (28, 24, 15), (38, 34, 19), (26, 20, 14), (32, 36, 16), (28, 22, 13), (24, 28, 19), (38, 22, 17), (20, 38, 16)Table 2
Performance comparisons of four algorithms.
Example number
Size
Algorithm
Averager
Standard deviation
Minimalr
Maximalr
Averaget/s
1
5
GA + HA [35]
11.7703
0.0335
11.7597
11.8655
0.242
CA-PSLS [34]
12.2181
0.5214
11.5443
13.0982
11.657
QPDAA
11.6756
0.0235
11.4737
11.8533
0.953
2
6
IGA [44]
—
—
14.62000
—
18.000
CA-PSLS [34]
15.19402
—
14.39625
—
19.904
QPDAA
14.68374
—
14.344996
14.909841
4.963
3
9
GA + HA [35]
18.1709
0.2361
17.8988
18.6041
1.262
CA-PSLS [34]
20.0899
1.1957
18.3758
22.0803
58.126
QPDAA
18.2461
0.0694
17.6880
18.5983
1.110
4
20
GA + HA [35]
23.2713
0.4728
22.6396
24.0605
9.989
CA-PSLS [34]
32.7216
4.0065
27.2863
38.5048
321.071
QPDAA
22.8368
0.0222
22.3510
23.7884
2.625
5
40
GA [35]
119.2396
1.5087
115.836
120.7099
62.795
CA-PSLS [34]
253.4165
43.8096
195.5914
306.2740
1367.573
QPDAA
119.1383
0.6887
115.6252
120.5102
3.375Table 3
The layout schemes of the proposed QPDAA for Examples  1 and  2.
Example  1
Example  2
i
x
i
y
i
i
x
i
y
i
1
5.017966
−4.093750
1
−5.810001
−7.386930
2
4.932835
2.906250
2
5.686532
6.537550
3
−3.982034
−4.093750
3
8.827469
−0.519116
4
−5.067165
0.906250
4
3.371405
−7.538003
5
−2.067165
5.906250
5
−3.346021
6.667169
6
−7.636339
−1.338337Table 4
The layout schemes of the proposed QPDAA for Example  3.
i
x
i
y
i
1
0.074698
−3.832386
2
2.329571
3.285391
3
4.944505
−10.373944
4
3.514680
11.503878
5
11.343280
1.762618
6
−6.074076
−9.903838
7
10.077353
−5.359918
8
−10.295647
−2.839607
9
−7.690402
6.187573Table 5
The layout scheme of the proposed QPDAA for Example  4.
i
x
i
y
i
1
2.275791
−8.061370
2
0.693375
15.930070
3
8.143939
8.438630
4
−4.806625
15.930070
5
−5.021757
−17.061370
6
5.978243
−15.573636
7
0.275791
−3.561370
8
−12.856061
7.930070
9
−5.724209
−10.561370
10
6.193375
17.938630
11
−16.608718
1.930070
12
7.143939
3.938630
13
−7.608718
1.930070
14
16.143939
1.426364
15
−1.856061
8.430070
16
9.143939
13.938630
17
3.391282
0.438630
18
−14.724209
−5.069930
19
12.275791
−7.573636
20
−12.724209
−12.069930Table 6
The layout scheme of the proposed QPDAA for Example  5.
i
x
i
y
i
1
−20.484058
−97.670716
2
96.802177
−23.135827
3
−32.957579
−3.670716
4
−17.484058
−67.670716
5
−34.765848
92.329284
6
−16.197823
−34.670716
7
49.515942
−85.946702
8
−5.847798
30.463901
9
24.515942
−86.536099
10
−55.957579
−24.941525
11
−93.957579
1.531453
12
22.042421
4.053298
13
23.234152
85.053298
14
71.802177
−25.946702
15
−71.484058
−59.468547
16
92.042421
9.864173
17
23.152202
57.053298
18
3.515942
−83.536099
19
−32.847798
65.329284
20
−41.484058
−57.941525
21
−32.957579
30.329284
22
66.042421
1.053298
23
9.802177
−56.536099
24
−4.765848
88.463901
25
−59.957579
4.058475
26
−4.847798
59.463901
27
12.802177
−29.536099
28
−86.957579
−30.468547
29
52.515942
−63.946702
30
−64.765848
69.531453
31
44.802177
−32.946702
32
−85.957579
35.531453
33
86.152202
40.864173
34
57.234152
69.864173
35
21.152202
32.053298
36
−6.957579
−0.536099
37
−56.957579
25.058475
38
−45.484058
−85.941525
39
53.152202
35.053298
40
45.042421
5.053298The layout diagraphs of five examples for the proposed QPDAA.
(a)
(b)
(c)
(d)
(e)Experiment 2.
For testing the effects ofR0 and r* on the minimal radius and running time with the proposed QPDAA, we take another set of R0 and r* (five examples and other parameters are the same as those of  Experiment 1) and run the proposed QPDAA procedure 30 times for each example. The minimal radii and running times are given in Table 7. Their layout schemes and layout diagraphs are shown in Tables 8, 9, 10, and 11 and Figure 13. It can be found from Table 7 that changing values of R0 and r* we can obtain the packing scheme with a smaller envelop radius, but it costs more time for each example. So, values R0 and r* in Experiment 1 can be applied to make a tradeoff between the computational effectiveness and solution quality.Table 7
The effect of parametersR0 and r* on the optimal radius and running time for the proposed QPDAA.
Experiment number
1
2
3
4
5
Size
5
6
9
20
40
R
0
11.4
14.3
17.5
22.3
115.5
r
*
1.05R0
1.05R0
1.07R0
1.07R0
1.05R0
The optimal radius
11.4737
14.344996
17.6880
22.3510
115.6252
Running time
0.953
3.5872
1.110
2.625
2.625
R
0
11.4
14.3
17.5
22.06
114.8
r
*
1.02R0
1.02R0
1.03R0
1.01R0
1.01R0
The optimal radius
11.450458
14.309924
17.597856
22.141009
115.042385
Running time
1.297
8.963
7.906
12.920
17.125Table 8
The optimal layout schemes of Examples  1 and  2 for the proposed QPDAA.
i
x
i
y
i
i
x
i
y
i
1
−2.954693
−5.470039
1
4.948526
8.054106
2
5.045307
−2.429991
2
4.903437
−6.945894
3
−2.408844
4.570009
3
−4.140424
−8.010294
4
−4.954693
−0.429991
4
5.911271
1.054106
5
5.591156
4.570009
5
−4.088729
5.989706
6
−5.096563
−2.010294Table 9
The optimal layout schemes of Example  3 for the proposed QPDAA.
i
x
i
y
i
1
8.952825
−8.127957
2
11.192355
3.872043
3
−11.893145
0.866506
4
−7.807645
7.896834
5
−7.161996
−7.133494
6
11.084588
−2.235259
7
−0.893145
0.866506
8
1.838004
−10.127957
9
2.125081
10.168689Table 10
The optimal layout scheme of Example  4 for the proposed QPDAA.
i
x
i
y
i
1
−7.913018
−16.1629110
2
−11.4301555
13.766710
3
−2.797531
7.599405
4
14.854397
8.176985
5
3.751568
4.136671
6
−14.476432
−7.582581
7
13.305438
−9.941647
8
−8.088653
−7.608034
9
3.747621
15.611128
10
−2.290583
−18.311460
11
−5.543514
1.554382
12
11.758080
13.883226
13
−14.800586
1.537640
14
16.662225
0.074950
15
−3.889690
15.762332
16
−13.867726
7.136671
17
−2.96.2478
−7.489430
18
6.210196
−4.937357
19
5.257463
−14.032250
20
8.273430
7.563706Table 11
The optimal layout scheme of Example  5 for the proposed QPDAA.
i
x
i
y
i
1
−35.716569
−20.219336
2
19.295868
92.929139
3
−66.464390
−69.791544
4
−0.799905
−80.612101
5
−8.704132
97.929139
6
−38.754325
−49.219336
7
60.543358
20.832873
8
47.933196
−29.082316
9
−42.456642
21.911290
10
−6.576451
43.929139
11
4.543358
7.350623
12
60.568942
−69.995791
13
−74.792262
52.886007
14
57.004507
44.832873
15
33.5433588
0.917684
16
97.933196
−2.928148
17
71.933196
−4.167127
18
14.886008
67.929139
19
−41.5764518
50.911290
20
−93.27781098
23.736930
21
−67.7165699
−2.088710
22
90.543358
27.071852
23
−41.704132
81.911290
24
−65.456642
20.911290
25
−58.7543259
−29.088710
26
28.423549
35.350623
27
0.535610
−101.612101
28
48.2958689
75.832873
29
−80.754325
−36.263070
30
−9.113992
71.929139
31
28.245675
−56.649377
32
79.933196
−36.928148
33
81.004507
52.071852
34
−37.464390
−82.649377
35
29.200095
−79.649377
36
−6.716569
−25.649377
37
20.283431
−29.082316
38
−98.716569
−4.263070
39
−9.754325
−54.649377
40
−22.456642
11.780664The optimal layout scheme diagraphs of five examples for the proposed QPDAA.
(a)
(b)
(c)
(d)
(e)In order to further test the effectiveness of the proposed QPDAA, we consider Experiment3.Experiment 3.
Numbers of rectangles (generated randomly) of three examples are 50, 55, and 60 and their lengths and widths are between 20 and 40. For the proposed QPDAA, we takeα=18, β=56, ε=10-20, h=0.8, δ=10, N=120, R0 = 125.9, 133.8, 137.2, and r* = 126.8, 134.6, 138.8 for Examples 1–3, respectively. For GA + HA, the population size, mutation probability, and max number of the iteration are 30, 0.125, and 50, respectively. By running HA + GA and the proposed QPDAA 30 times for three examples, respectively, their optimal envelop radii and average times are shown in Table 12, respectively. The optimal packing scheme diagrams of GA + HA and the proposed QPDAA are shown in Figures 14(a)–14(c) and Figures 14(d)–14(f). We can know from Table 12 that both the solution quality and computational quality of the proposed QPDAA are obviously higher than those of GA + HA.Table 12
The effect ofR0 and r* on the optimal radius and running time for the proposed QPDAA.
Example number
Size
HA + GA
QPDAA
The optimal radius
Running time (s)
The optimal radius
Running time (s)
1
50
127.667244
30.170088
126.567311
13.345431
2
55
134.844782
42.654031
134.105091
19.056438
3
60
139.072606
66.908203
137.833657
37.01790Packing scheme diagrams of GA + HA and the proposed QPDAA for Experiment3.
(a)
GA_HA for 50 rectangles
(b)
GA_HA for 55 rectangles
(c)
GA_HA for 60 rectangles
(d)
QPDAA for 50 rectangles
(e)
QPDAA for 55 rectangles
(f)
QPDAA for 60 rectanglesNote that, in Experiment3, the procedure of GA + HA is coded by author and is carried on a Pentium 3 GHZ with 512 MB memory.


## 6.2. Analysis

From data of Tables2, 7, and 12, we know that the solution quality of the proposed QPDAA algorithm is higher than those of CA-PSLS and GA-HA. Compared with those of CA-PSLS, embedded degree functions of the proposed QPDAA can make the layout scheme more compact. Due to the fixed candidate positions of GA + HA, it is difficult to find the best position for some rectangles close to the marginal region of the container. The deficiency of a mechanism of decreasing the static balance in the process of packing rectangles also limits the solution quality of GA + HA. The experimental results illustrate the effectiveness of the proposed QPDAA.The computational efficiency of the proposed QPDAA is one magnitude higher than those of CA-PSLS. There are two reasons. (i) Owing to orthogonal packing, searching the optimal solution in the 2D solution of the proposed QPDAA is easier than that in the 3D solution space of CA-PSLS. (ii) In order to improve the solution quality of CA-PSLS, PSO is used to optimize the feasible solution obtained through the gradient method based on two discontinuous embedded degree functions, but the proposed QPDAA need not do the PSO optimization without reducing its solution quality. Except for Example 1, the computational efficiency of the proposed QPDAA is higher than that of GA + HA. And with the increase of the size of the packing problem, the advantage of the proposed QPDAA is more obvious. This is because computational complexities of the extruded resultant force and potential energy areO(n) in this paper, but the computational complexity of noninterference judgment is O(n2). In addition, for GA + HA, with the increasing of the number of rectangles, the number of candidate positions of each rectangle increases dramatically. These reasons lead to the computational efficiency of the proposed QPDAA higher than that of GA + HA for the BCOURP with a large size.


## 7. Conclusions

Taking the layout design of a satellite module as the application background, we have proposed the QPDAA for the BCOURP problem in this paper. Two continuous embedded functions between orthogonal rectangles and between the rectangle and container are constructed to overcome the weakness of embedded functions in [34]. And the suggestion of the extruded resultant force formula and the potential energy function of the rectangle packing system based on the proposed embedded functions make solving the BCOURP problem simple and effective as solving the circle packing problem [37–40]. The proposed dynamic adjustment strategy can quickly decrease the static imbalance of the packing scheme and make the iteration skip the local optimum. The experiment results show that the proposed QPDAA is superior to existing algorithms in performance for the BCOURP problem, especially for the BCOURP problem with the large size. The next work is to extend the above algorithm into solving the 3D satellite module payload packing problem.



---

*Source: 657170-2014-12-02.xml*