Optimization Online


A parallel multi-population biased random-key genetic algorithm for a container loading problem

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

Abstract: 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.

Keywords: container loading, 3D Packing, genetic algorithm, multi-population, random keys

Category 1: Applications -- OR and Management Sciences (Production and Logistics )

Category 2: Combinatorial Optimization

Category 3: Combinatorial Optimization (Meta Heuristics )

Citation: AT&T Labs Research Technical Report, AT&T Labs Research, Florham Park, NJ 07932 USA, July 2010.

Download: [PDF]

Entry Submitted: 07/26/2010
Entry Accepted: 07/26/2010
Entry Last Modified: 07/26/2010

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 Programming Society