A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces

Bortfeldt, A

doi:10.1016/j.ejor.2004.11.016

Return

A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces

2006-08-01

187

PRE

Bortfeldt, A

DOI：10.1016/j.ejor.2004.11.016

Original

Original request for help

Save

Abstract

En 中文

Given a set of rectangular pieces and a container of fixed width and variable length, the two-dimensional strip packing problem (2D-SPP) consists of orthogonally placing all the pieces within the container, without overlapping, such that the overall length of the layout is minimised. Until now mainly heuristics, for example genetic algorithms (GA), were proposed for the 2D-SPP which use encoded solutions that are manipulated by standard operators. In this paper a GA for the 2D-SPP is suggested that works without any encoding of solutions. Rather fully defined layouts are manipulated as such by means of specific genetic operators. Two additional constraints, namely the orientation constraint and the guillotine constraint, can be taken into account. The GA is subjected to a comprehensive test using benchmark instances with up to 5000 pieces. Compared to eleven competing methods from the literature the GA performs best. (c) 2004 Elsevier B.V. All rights reserved.

Keywords:

packing

two-dimensional strip packing problem

rectangular pieces

genetic algorithm

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.