This page is dedicated to the article [1]. You can find the data sets and the numerical results presented in [1], as well as the computer implementation of the algorithm in C/C++. You can also run the algorithm through our Web interface.

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.

Recursive Five-block Algorithm

The Recursive Five-block Algorithm [1] is a modified implementation of the algorithm described in [4]. Basically, the 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.

First-order non-guillotine pattern
Partitions produced by a first-order non-guillotine cut.
(49,28,8,3) with 56 boxes packed
Problem (L,W,l,w) = (49,28,8,3) with 56 boxes packed.

L-Algorithm

L-Algorithm has been proposed and described in [2] and [3]. This 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 [1] we describe two new ways of dividing an L-shaped piece into two L-shaped pieces, which were not considered in [3]. Run the L-Algorithm!

Pattern obtained by L-Algorithm.
(49,28,8,3) with 57 boxes packed by
Problem (L,W,l,w) = (49,28,8,3) with 57 boxes packed by L-Algorithm.

Recursive Partitioning Algorithm - A combined algorithm

This algorithm (described in [1]) 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 LW. Then, it will ask you l and w, the dimensions of the rectangular items to be packed, also satisfying lw. 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:

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 [1].

Set Instances Characteristics
Cover IA8274 1 ≤ LW ≤ 3   1 ≤ lw ≤ 4   1 ≤ LWlw < 51
Cover IIA41831 1 ≤ LW ≤ 2.2   1 ≤ lw ≤ 4   51 ≤ LWlw < 101
Cover IB7827 1 ≤ LW ≤ 2   1 ≤ lw ≤ 4   1 ≤ LWlw < 51
Cover IIB40609 1 ≤ LW ≤ 2   1 ≤ lw ≤ 4   51 ≤ LWlw < 101
Cover IIIB98016 1 ≤ LW ≤ 2   1 ≤ lw ≤ 4   101 ≤ LWlw < 151
Ships15 1 < LW < 3   1 < lw < 2   151 < LWlw < 344

The updated Cover IIIB, as described in [1], 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.

Contact

Ernesto G. Birgin Rafael D. Lobato Reinaldo Morabito
www.ime.usp.br/~egbirgin www.ime.usp.br/~lobato www.dep.ufscar.br/docentes/morabito.htm

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).

References

[1] 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, volume 61, pp. 306-320, 2010. [Abstract] [PDF] [PS] [DOI]
[2] E. G. Birgin, R. Morabito and F. H. Nishihara. A note on an L-approach for solving the manufacturer's pallet loading problem. Journal of the Operational Research Society, volume 56, number 12, pp. 1448-1451, 2005. [Abstract] [PDF] [PS] [DOI]
[3] L. Lins, S. Lins and R. Morabito. An L-approach for packing (l,w)-rectangles into rectangular and L-shaped pieces. Journal of the Operational Research Society, volume 54, number 7, pp. 777-789, 2003. [DOI]
[4] R. Morabito and S. Morales. A simple and effective recursive procedure for the manufacturer's pallet loading problem. Journal of the Operational Research Society, volume 49, number 8, pp. 819-828, 1998. [DOI]

DCC - IME - USP

Valid XHTML 1.0 Strict

Valid CSS!