Recursive partitioning approach
for the Manufacturer's Pallet Loading Problem

This page is dedicated to the article

E. G. Birgin, R. D. Lobato and R. Morabito. An effective recursive partitioning approach for the packing of identical rectangles in a rectangle. Journal of the Operational Research Society (2010) 61, 306–320.

The full text is available in PDF and PS formats and can also be found at the journal's official website. You can also find the data sets and the numerical results therein presented, as well as the computer implementation of the algorithm in C/C++. You can also run the algorithm through our Web interface. If you have any questions, please send an e-mail to rafael@lobato.it.

Introduction

The problem consists in arranging, without overlapping, identical rectangular pieces (boxes) with length l and width w in a rectangular pallet with length L and width W. The boxes must be placed orthogonally (i.e., with each side of the boxes orthogonal to one side of the pallet) and only 90-degree rotations are allowed. The objective is to find a pattern with the maximum number of boxes packed. This two-dimensional packing problem is also known as the manufacturer's pallet loading problem. We assume that L, W, l and w are integers and L ≥ W and l ≥ w without loss of generality. Thus, a problem is determined by the quadruple (L,W,l,w).

This packing problem can be classified as 2/B/O/C according to Dyckhoff's typology of cutting and packing problems, and as "two-dimensional, rectangular Identical Item Packing Problem (IIPP)" based on Wäscher, Haußner and Schumann's typology.

Algorithms

Recursive Five-block Algorithm

Basically, the Recursive Five-block Algorithm divides the rectangle into, at most, five regions through first-order non-guillotine cuts, as showed below. Then, the algorithm is called recursively for each region produced. You can run this algorithm online.

L-Algorithm

The L-Algorithm is more general than the Recursive Five-block Algorithm. Besides producing first-order non-guillotine patterns, it also produces other ones that appear when the rectangle is divided in L-shaped regions. The figures below show an example of a pattern obtained by L-shaped cuts and the solution found by L-Algorithm for the problem (L,W,l,w) = (49,28,8,3). In the paper, we describe two new ways of dividing an L-shaped piece into two L-shaped pieces, which were not considered before. Run the L-Algorithm!

Recursive Partitioning Algorithm - A combined algorithm

This algorithm (described in the paper) combines the speed of the Recursive Five-block Algorithm and the robustness of the L-Algorithm. First, it tries to solve the problem with the Recursive Five-block Algorithm. If the solution found is not optimal (or, at least, if it is not possible to prove its optimality), the L-Algorithm is called to solve the problem. Moreover, all information obtained by the first algorithm is used by the second one. Run it through our Web interface.

Download: RecursivePartitioningAlgorithm.tar.gz

How to compile and run

To compile, just type make or, manually:

g++ -O3 RecPartAlgorithm.cpp bd.cpp draw.cpp draw_bd.cpp \
      graphics.cpp sets.cpp util.cpp -o RecPartAlgorithm

The executable file created will be called RecPartAlgorithm.

The program will ask you L and W, the dimensions of the rectangular pallet satisfying L ≥ W. Then, it will ask you l and w, the dimensions of the rectangular items to be packed, also satisfying l ≥ w. After having entered the data of the problem, the program will answer the number of packed rectangles. It will also generate a MetaPost file called solution.mp with a graphical representation of the solution. Alternatively, it will also produce a file called solution.svg with a graphical representation of the solution in SVG (Scalable Vector Graphics) format.

For example, to run the Recursive Partitioning Algorithm to solve the problem (L,W,l,w) = (49,28,8,3), you must type:

./RecPartAlgorithm
L and W: 49 28
l and w: 8 3

The output will be similar to this one:

Phase 1 (Five-block Algorithm)
 - solution found: 56 boxes.
 - runtime:        0.00 second.

Phase 2 (L-Algorithm)
 - solution found: 57 boxes.
 - runtime:        0.26 second.

Solution found: 57 boxes.
Computed upper bound: 57 boxes.
Proven optimal solution.
Runtime: 0.26 second.

Visualizing the solution

The program creates two files, namely, solution.mp and solution.svg, that graphically represent the solution in MetaPost and SVG formats, respectively. There are two options for visualizing the solution found. The first one is by simply using some SVG viewer to view the file solution.svg. For the second option, you need MetaPost and a Latex implementation installed on your system. Then compile the file solution.tex in the same directory of solution.mp.

mpost solution.mp
latex solution.tex

It creates a file called solution.dvi which can be visualized with a DVI viewer. If you wish, you can convert this file into a PDF file:

dvipdf solution.dvi

Data sets

Below you can get the data sets used in the experiments described in the paper.

The updated Cover IIIB, as described in the paper, is available. The last update was made on January 11th, 2009. The detailed progress can also be viewed.

Numerical results

The experiments were run on a 2.4GHz Intel® Core™2 Quad Q6600 with 4.0GB of RAM memory and Linux Operating System. Below you can get our output files.

• Recursive Five-block Algorithm
  CoverIA.out, CoverIIA.out, CoverIB.out, CoverIIB.out and CoverIIIB.out.
• L-Algorithm
  CoverIA.out, CoverIIA.out, CoverIB.out, CoverIIB.out and CoverIIIB.out.
• Recursive Partitioning Algorithm
  CoverIA.out, CoverIIA.out, CoverIB.out, CoverIIB.out, CoverIIIB.out and Ships.out.

Contact

Rafael D. Lobato
E-mail: rafael@lobato.it
Website: lobato.it

Sponsors

This work was partially supported by the Brazilian agencies FAPESP (Fundação de Amparo à Pesquisa do Estado de São Paulo) and CNPq (Conselho Nacional de Pesquisa e Desenvolvimento).