Premium
A genetic algorithm for the two‐dimensional knapsack problem with rectangular pieces
Author(s) -
Bortfeldt Andreas,
Winter Tobias
Publication year - 2009
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2009.00701.x
Subject(s) - knapsack problem , genetic algorithm , continuous knapsack problem , mathematical optimization , computer science , cutting stock problem , algorithm , mathematics , optimization problem
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. Compared with recently published methods, the GA yields competitive results.