J.F. Gonçalves and M.G.C. Resende
International J. of Production Economics, published online 18 April 2013
ABSTRACT
We present a
novel multi-population biased random-key genetic algorithm (BRKGA) for
the 2D and 3D bin packing problem. The approach uses a
maximal-space representation to manage the free spaces in the bins. The
proposed algorithm uses a decoder based on a novel placement procedure
within a multi-population genetic algorithm based on random keys. The
BRKGA is used to evolve the order in which the boxes are packed into
the bins and the parameters used by the placement procedure. Two
heuristic procedures are used to determine the bin and the free maximal
space where each box is placed. A novel fitness function that improves
significantly the quality of the solutions produced is also developed.
The new approach is extensively tested on 858 problem instances from
the literature. The computational experiments demonstrate not only that
the approach performs extremely well, but that it obtains the best
overall results when compared with other approaches published in the
literature. It reduced the total number of bins used from 9803 to 9772
for the 3D instances and from 7241 to 7234 for the 2D instances.
PDF file of full paper
Mauricio G.C. Resende's Home Page
Last modified: 22 April 2013