3.7.171. Pallet loading

A constraint that can be used for modelling the pallet loading problem. The pallet loading problem consists of packing a maximum number of identical rectangular boxes onto a rectangular pallet in such a way that boxes are placed with their edges parallel to the edges of the pallet. The problem often arises in distribution, when many boxes must be shipped and an increase of the number of boxes on a pallet saves costs. Even if the complexity of the problem is not yet knownΒ [Nelissen94], many solutions have been developed over the past years:

  • Exact algorithms based on tree search procedures extend a partial solution by positioning a new box according to different heuristics. One of the most used heuristics is the so called G4 heuristicsΒ [ScheithauerTerno96] which recursively divides the Β placement space into four huge rectangles. Beside the use of an appropriate heuristics, the key point is the use of upper bounds on the maximum number of boxes that can be packed. Some bounds like the BarnesΒ [Barnes79] and the KeberΒ [Keber85] bounds consider the geometric structure of the problem. Some other bounds are obtained by solving a linear programming problemΒ [Isermann91].

  • Approximate algorithms are based on constructive methods (i.e., methods that either divide the pallet into blocks or methods that divide the pallet in a recursive way) or metaheuristics based on genetic algorithms or tabu searchΒ [AlvarezValdesParrenoTamarit05].

Both in the context of exact and approximates algorithms, the problem is usually first normalised in order to reduce the set of possible solutionsΒ [Dowsland84], [Dowsland85].