# An Improved Adaptive Genetic Algorithm for Two-Dimensional Rectangular Packing Problem
## 2 Problem Statement  
Assume that there is a set of \(n\) rectangle (\(R=\{r_{1},r_{2},\ldots,r_{n}\}\)) items with \(w_{i}\times h_{i}\) for \(i=1,2,\ldots,n\). The task is to orthogonally place the items without overlapping in the sheet with \(W\times H\) to maximize the filling rate of the sheet, i.e., to maximize the total area of the placed items divided by the area of the sheet. The paper addresses the 2 DRP with the following assumptions [30; 31]:  
1. For any two rectangular items put in, they cannot overlap each other.
2. When the rectangle is put into the sheet, it cannot exceed the boundary of the sheet.
3. The side of the rectangular items must be parallel to the side of the sheet.
4. The rectangular can be rotated \(90^{\lx@math@degree}\).  
Based on the problem description and assumptions, a two-dimensional rectangular coordinate system is established with the bottom left corner of the sheet as the origin of the coordinates, and the coordinates of the bottom left corner of the rectangle \(r_{i}\) are \((x_{i},y_{i})\), as shown in Figure 1. Use variable \(g_{i}\) to indicate whether the rectangle \(r_{i}\) is rotated; \(g_{i}=0\) means no rotation, and \(g_{i}=1\) means rotation. If the rectangle \(r_{i}\) is rotated, the width and height of the rectangle are interchanged.  
Therefore, the actual width and height of the rectangle placed change to \(w_{i}(1-g_{i})+h_{i}g_{i}\) and \(w_{i}g_{i}+h_{i}(1-g_{i})\) respectively, and the coordinates of the top right corner of the rectangle are \((x_{i}+w_{i}(1-g_{i})+h_{i}g_{i},y_{i}+w_{i}g_{i}+h_{i}(1-g_{i}))\). It can be seen that the rectangle \(r_{i}\) is represented by \((x_{i},y_{i},w_{i},h_{i},g_{i})\), which can determine the accurate position of the rectangle in the sheet.  
Figure 1: Coordinate system.  
Let \(\theta_{i}\) be a decision variable, taking the value 1 or 0 accordingly as rectangle \(r_{i}\) is or is not placed. The filling rate \(F\) of the sheet is defined as the ratio of the total area of the rectangles placed in it to the area of the sheet. The mathematical model of the 2 DRP is as follows:  
\[\max F=\frac{\sum\limits_{i=1}^{n}w_{i}h_{i}\theta_{i}}{W\times H} \tag{1}\]  
s. t.  
1. \(x_{i}+w_{i}(1-g_{i})+h_{i}g_{i}\leq W,y_{i}+w_{i}g_{i}+h_{i}(1-g_{i})\leq H\)
2. \(\max\{x_{i1}-x_{i2},x_{j1}-x_{i2},y_{i1}-y_{j2},y_{j1}-y_{i2}\}\theta_{i}\theta _{j}\geq 0\)
3. \((x_{i2}-x_{i1},y_{i2}-y_{i1})\in\{(w_{i},h_{i}),(h_{i},w_{i})\}\)
4. \(\theta_{i}\in\{0,1\},g_{i}\in\{0,1\}\)
5. \(0\leq x_{i}\leq W,0\leq y_{i}\leq H\).  
In constraints (1)-(4), \(i\), \(j\) applies to \(1,2,\ldots,n\) and \(i\
eq j\). Constraint (1) implies that the boundaries of the placed rectangles do not exceed the width and height boundaries of the sheet. Constraint (2) means that the placed rectangles cannot overlap each other. \((x_{i1},y_{i1})\) and \((x_{i2},y_{i2})\) represent the coordinates of the bottom left corner and the top right corner of the placed rectangles, respectively. The coordinates of the top right corner can be calculated with the coordinates of the bottom left corner and the width and height of the actual size of the rectangle. Constraint (3) implies that the placed rectangle is parallel to the side of the sheet and can be rotated by \(90^{\lx@math@degree}\). To sum up, the 2 DRP problem can be described as figuring out the best packing solution that satisfies the constraints and maximizes the filling rate of the sheet.