A Genetic Algorithm for theTwo-Dimensional Knapsack Problemwith Rectangular Pieces

Given a set of rectangular pieces and a rectangular container, the two-dimensional knapsackproblem (2D-KP) consists of orthogonally packing a subset of the pieces within the container suchthat the sum of the values of the packed pieces is maximized. If the value of a piece is given by itsarea the objective is to maximize the covered area of the container. A genetic algorithm (GA) isproposed 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 beconstrained or unconstrained.[...]

MoreLess

Year of publication:	2008-05-01
Authors:	Bortfeldt, Andreas ; Winter, Tobias
Institutions:	Fernuniversität <Hagen> / Lehrstuhl für Wirtschaftsinformatik
Subject:	Packungsproblem \| Algorithmus

Check Google Scholar |

More access options

In German libraries (KVK)

I need help

1 Introduction
2 Previous work
3 The genetic algorithm for the 2D knapsack problem
3.1 Layer structure of generated packing plans
3.2 Representation of solutions and fitness
3.3 Algorithm of the genetic search and operators
3.4 Completing solutions
3.5 Filling a layer – first heuristic
3.6 Filling a layer – second heuristic
3.7 Heuristic for post-optimization
3.8 Variants of the genetic algorithm
4 Testing the method
4.1 Problem instances and comparison methods for the test
4.2 Numerical results
5 Summary
Bibliography

Persistent link: https://www.econbiz.de/10005867242