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

• Tipo: Artigo em Revista Científica Internacional
• Data: 2012

Autores

Jose Fernando Goncalves (Autor) FEP; Mauricio G C Resende (Autor) Outra

Revista

Título: Computers and Operations Research

Vol. 39 Nº 2

Páginas: 179-190

ISSN: 0305-0548

Editora: Elsevier

Indexação

ISI Web of Knowledge - 75 Citações

ISI Web of Science

Scopus - 101 Citações

Classificação Científica

FOS: Ciências da engenharia e tecnologias > Engenharia civil

CORDIS: Ciências Sociais > Economia > Estudos de gestão

Outras Informações

ID Authenticus: P-002-DSM

DOI: 10.1016/j.cor.2011.03.009

Abstract (EN): This paper presents a multi-population biased random-key genetic algorithm (BRKGA) for the single container loading problem (3D-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 [1] and Davies and Bischoff [2] and is compared with 13 other approaches. The test set consists of 1500 instances from weakly to strongly heterogeneous cargo. The computational experiments demonstrate that not only the approach performs very well in all types of instance classes but also it obtains the best overall results when compared with other approaches published in the literature.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 12