A genetic algorithm for the two-dimensional 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 ofthe values of the packed pieces is maximized. If the value of a piece is given by its area, the objective is tomaximize the covered area of the container. A genetic algorithm (GA) is proposed addressing the guillotinecase of the 2D-KP as well as the non-guillotine case. Moreover, an orientation constraint may optionally betaken into account and the given piece set may be constrained or unconstrained. The GA is subjected to anextensive test using well-known benchmark instances. Compared with recently published methods, the GAyields competitive results.