Optimization Online


A biased random-key genetic algorithm for a 2D and 3D bin packing problem

José F. Gonçalves(jfgoncal***at***fep.up.pt)
Mauricio G.C. Resende(mgcr***at***research.att.com)

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.

Keywords: Bin packing, heuristic, genetic algorithm, biased random-key genetic algorithm, three-dimensional, random keys.

Category 1: Combinatorial Optimization (Meta Heuristics )

Category 2: Applications -- OR and Management Sciences

Citation: AT&T Labs Research Technical Report, Shannon Laboratory, Florham Park, NJ, April 2012.

Download: [PDF]

Entry Submitted: 04/09/2012
Entry Accepted: 04/10/2012
Entry Last Modified: 04/09/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society