An AND/OR-graph approach to the container loading problem

The container loading problem consists of packing boxes of various sizes into available containers in such a way as to optimize an objective function. This paper deals with the special case where there is just one available container and the objective is to maximize the total volume (or the total utility value, supposing that each box has a utility value) of the loaded boxes. It firstly presents three heuristic solution methods for the unconstrained problem. Two of them solve the original three-dimensional problem by layers and by stacks reducing it into several problems with lower dimensions. The third one consists of representing possible loading patterns as complete paths in an AND/OR-graph. Bounds and heuristics are proposed in order to reduce the solution space. A proper heuristic is also given to treat the constrained problem by using the AND/OR-graph approach. Moreover, computational results are presented by solving a number of examples.