This paper presents a multi-population biased random-key genetic algorithm (BRKGA) for the Single Container Loading Problem (CLP) where several rectangular boxes of different sizes are loaded into a single rectangular container. The approach uses a maximal-space representation to manage the free spaces in the container. The proposed algorithm hybridizes a novel placement procedure with a multi-population genetic algorithm based on random keys. The BRKGA is used to evolve the order in which the box types are loaded into the container and the corresponding type of layer used in the placement procedure. A heuristic is used to determine the maximal space where each box is placed. A novel procedure is developed for joining free spaces in the case where full support from below is required. The approach is extensively tested on the complete set of test problem instances of Bischoff and Ratcliff (1995) and Davies and Bischoff (1999) and is compared with other approaches. The test set consists of weakly to strongly heterogeneous instances. The experimental results validate the high quality of the solutions as well as the effectiveness of the proposed heuristic.
Citation
AT&T Labs Research Technical Report, AT&T Labs Research, Florham Park, NJ 07932 USA, July 2010.