A family of genetic algorithms for the pallet loading problem

This paper is concerned with a family of genetic algorithms for the pallet loading problem. Our algorithms differ from previous applications of genetic algorithms to two-dimensional packing problems in that our coding contains all the information needed to produce the packing it represents, rather than relying on a packing algorithm to decode each individual solution. We experiment with traditional one-dimensional string representations, and a two-dimensional matrix representation which preserves the notion of closeness between positions on the pallet. Two new crossover operators are introduced for the two-dimensional case. Our definition of solution space includes both feasible and infeasible solutions and we suggest a number of different fitness functions which penalise infeasibility in different ways and a repair operator which allows our populations to maintain feasibility. The results of experiments designed to test the effectiveness of these features are presented.