# A Two-Phase Approach for Single Container Loading with Weakly Heterogeneous Boxes
## 2 Block-Loading Hybrid Metaheuristic
### Block Generation  
Some CLP algorithms [4; 7; 8] have received notoriety for loading cuboid blocks of boxes instead of single boxes, thus being properly classified as block-building approaches. By definition, a block is a set of boxes placed compactly inside its _Minimum Bounding Cuboid_ (MBC) [7]. Existing research classifies blocks into two types: simple blocks and guillotine blocks. Simple blocks consist of identical boxes, in the same spatial orientation and occupying the total volume of their respective MBCs. A pseudocode [7] to generate simple blocks is presented in Algorithm 1, which roughly produces valid blocks with \(n_{x}\) boxes in a row, \(n_{y}\) boxes in a column, and \(n_{z}\) boxes in a stack, all of them of the same type, as illustrated in Figure 2.  
```
0: A container with dimensions \(L\), \(W\), and \(H\) and a collection of boxes grouped into types. Each type \(t\) has a length \(l_{t}\), a width \(w_{t}\), a height \(h_{t}\), and a quantity \(q_{t}\) of boxes available to be loaded. 0: Set \(B\) of simple blocks. 1:\(B\leftarrow\emptyset\)
2:for each box type \(t\)do
3:for each allowed orientation of \((l_{t},w_{t},h_{t})\)do
4:for\(n_{x}=1\) to \(q_{t}\)do
5:for\(n_{y}=1\) to \(\frac{q_{t}}{n_{x}}\)do
6:for\(n_{z}=1\) to \(\frac{q_{t}}{n_{x}\times n_{y}}\)do
7:if\(n_{x}\times l_{t}\leq L\) & \(n_{y}\times w_{t}\leq W\) & \(n_{z}\times h_{t}\leq H\)then
8: Create a block \(b\) with dimensions \((n_{x}\times l_{t},n_{y}\times w_{t},n_{z}\times h_{t})\), and add it to \(B\)
9:return\(B\)
```  
**Algorithm 1** Generating simple blocks (adapted from the original paper [7]). Figure 2: A simple block with four boxes in a row, two boxes in a column, and three boxes in a stack. Conversely, guillotine blocks consist of multiple types of boxes possibly placed in different spatial orientations. A pseudocode to generate guillotine blocks, proposed by [PERSON] and [PERSON] [7], is given in Algorithm 2. \(B\), \(PG\), and \(NG\) denote, respectively, the set of blocks generated so far, the set of blocks generated in the previous iteration, and the set of blocks generated in the current generation. Given one block \(b_{1}\) from \(B\) and another block \(b_{2}\) from \(PG\), guillotine blocks are generated by combining the two blocks along the length, width, or height direction of the container, as illustrated in Figure 3.  
```
0: Set \(B\) of simple blocks (see Algorithm 1). 0: Extended set \(B\) of guillotine blocks. 1:\(PG\gets B\)
2:repeat
3:\(NG\leftarrow\emptyset\)
4:for each block \(b_{1}\) in \(PG\)do
5:for each block \(b_{2}\) in \(B\)do
6:for each direction \(dir\) in \(\{L,W,H\}\)do
7: Combine \(b_{1}\) and \(b_{2}\) along the direction \(dir\) to obtain block \(b\)
8: Add \(b\) to \(NG\) if \(b\) is feasible and no equivalent block exists in \(B\)
9:\(B\gets B\cup NG\)
10:\(PG\gets NG\)
11:until \(PG=\emptyset\)
12:return\(B\)
```  
**Algorithm 2** Generating guillotine blocks (adapted from the original paper [7]). _Fully-Supported Blocks_ (FSBs) [7] are blocks complying with the stability constraint. They are generated handling an attribute called _packing area_, which is the rectangular region on the top face of the block that is fully covered by top faces of boxes belonging to its MBC. Obviously, simple blocks are FSBs. Guillotine FSBs are generated according to some rules. For instance, let \(b_{1}\) and \(b_{2}\) be two guillotine FSBs with packing area \(p_{1}\) and \(p_{2}\), respectively. Such blocks can be combined along the length (resp. width) direction if and only if they have the same height (i.e., \(b_{1}.h=b_{2}.h\)) and the sum of the lengths (resp. widths) of their packing areas spans the entire length (resp. width) of their MBCs, i.e., \(p_{1}.l+p_{2}.l=b_{1}.l_{1}+b_{2}.l_{2}\) (resp. \(p_{1}.w+p_{2}.w=b_{1}.w_{1}+b_{2}.w_{2}\)). When \(b_{1}\) and \(b_{2}\) are combined along the length (resp. width) direction, the resultant packing area \(p_{3}\) of the new FSB \(b_{3}\) is given by \(p_{3}.l=p_{1}.l+p_{2}.l\) (resp.