A genetic algorithm for the twodimensional Knapsack problem with rectangular pieces
Given a set of rectangular pieces and a rectangular container, the two-dimensional knapsack problem (2D-KP) consists of orthogonally packing a subset of the pieces within the container such that the sum of the values of the packed pieces is maximized. If the value of a piece is given by its area the objective is to maximize the covered area of the container. A genetic algorithm (GA) is proposed addressing the guillotine case of the 2D-KP as well as the non-guillotine case. Moreover, an orientation constraint may optionally be taken into account and the given piece set may be constrained or unconstrained. The GA is subjected to an extensive test using well-known benchmark instances. In a comparison to recently published methods the GA yields competitive results.
Nutzung und Vervielfältigung:
Alle Rechte vorbehalten