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.
Citation
AT&T Labs Research Technical Report, Shannon Laboratory, Florham Park, NJ, April 2012.
Article
View A biased random-key genetic algorithm for a 2D and 3D bin packing problem