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.

Partitions produced by a first-order non-guillotine cut.

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.

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

Recursive Partitioning Algorithm - A combined algorithm

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:

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

mpost solution.mp
latex solution.tex

dvipdf solution.dvi

Data sets

Below you can get the data sets used in the experiments described in [1].

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

• 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

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