An algorithm on three-dimensional loading problem

The purpose of this paper is to formulate the three-dimensional loading problem and to develop an exact algorithm. The three-dimensional loading problem is not only to load as many boxes as possible, but also to ensure load stability. In this paper, we propose a formulation by zero–one integer programming (IP). Further we propose as an algorithm the branch-and-bound enforced by efficient bounding criteria. As an upper bound, we use the solution of the Lagrangean relaxation problem which relaxes constraints of zero–one IP, and as a lower bound, we use a heuristic solution induced by the solution of the Lagrangean relaxation problem. Last, we show computational experiments on convergency of upper and lower bounds.