Recursive partitioning approach
for the Distributor's Pallet Loading Problem

Introduction - Problem instances - Solutions

This Web site is intended to be served as a supplement to the paper

E. G. Birgin, R. D. Lobato and R. Morabito. Generating unconstrained two-dimensional non-guillotine cutting patterns by a recursive partitioning algorithm. Journal of the Operational Research Society (2012) 63, 183–200. (DOI: 10.1057/jors.2011.6)

whose text is available in PDF and PS formats. We provide here all the instances we have used in our experiments as well as graphical representation of the solutions found by our method. Below there is a brief description of the problem we consider in this work. If you have any questions, please send an e-mail to rafael@lobato.it.

Problem description

Given a pallet with length L and width W, and m types of rectangular pieces, each one of type i with length li, width wi and value vi, the objective is to find an orthogonal cutting pattern which maximizes the sum of the values of the pieces cut. An orthogonal cutting pattern is one in which (i) the pieces do not overlap each other, (ii) they have to be entirely inside the pallet, and (iii) the piece placed into the pallet must have one edge parallel to one edge of the pallet.

The orientation of the pieces is fixed (that is, a piece (li,wi) is different from a piece (wi,li), if li ≠ wi) and the number of times each piece can appear in the solution is unbounded (that is, it's supposed that a large quantity of each piece is available). If vi = liwi for i = 1, …, m (in other words, if the value of each piece is equal to its area), the problem is said to be unweighted. Otherwise, it is said to be weighted.

Guillotine cutting pattern.
Two-staged guillotine cutting pattern. Solution with value 11929561 for instance UU10.
Guillotine cutting pattern
Guillotine cutting pattern. Solution with value 11955852 for instance UU10.

This problem is known as the unconstrained two-dimensional guillotine/non-guillotine cutting problem. According to the typology of cutting and packing problems of Wäscher, Haußner and Schumann, this problem is classified as two-dimensional, rectangular Single Large Object Packing Problem (SLOPP).

First-order non-guillotine cutting pattern
First-order non-guillotine cutting pattern. Solution with value 11995637 for instance UU10.
L-shaped cutting pattern
L-shaped cutting pattern. Solution with value 12001291 for instance UU10.

Sponsor

This work was partially supported by the Brazilian agency FAPESP (Fundação de Amparo à Pesquisa do Estado de São Paulo).