Recursive partitioning approach
for the Distributor's Pallet Loading Problem
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.
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).
Sponsor
This work was partially supported by the Brazilian agency FAPESP (Fundação de Amparo à Pesquisa do Estado de São Paulo).