Using tree search bounds to enhance a genetic algorithm approach to two rectangle packing problems

Citation

Dowsland KA, Herbert EA, Kendall G & Burke E (2006) Using tree search bounds to enhance a genetic algorithm approach to two rectangle packing problems. European Journal of Operational Research, 168 (2), pp. 390-402. https://doi.org/10.1016/j.ejor.2004.04.030

Abstract
A popular approach when using a genetic algorithm in the solution of constrained problems is to exploit problem specific information by representing individuals as ordered lists. A construction heuristic is then often used as a decoder to produce a solution from each ordering. In such a situation further information is often available in the form of bounds on the partial solutions. This paper uses two two-dimensional packing problems to illustrate how this information can be incorporated into the genetic operators to improve the overall performance of the search. Our objective is to use the packing problems as a vehicle for investigating a series of modifications of the genetic algorithm approach based on information from bounds on partial solutions.

Keywords
genetic algorithms; branch and bound; cutting; packing

Journal
European Journal of Operational Research: Volume 168, Issue 2