Approximate algorithms for the container loading problem

In this paper we develop several algorithms for solving three-dimensional cutting/packing problems. We begin by proposing an adaptation of the approach proposed in Hifi and Ouafi for solving two-staged unconstrained two-dimensional cutting problems. We show how the algorithm can be polynomially solved for producing a constant approximation ratio. We then extend this algorithm for developing better approximate algorithms. By using hill-climbing strategies, we construct some heuristics which produce a good trade-off between the computational time and the solution quality. The performance of the proposed algorithms is evaluated on different problem instances of the literature, with different sizes and densities (a total of 144 problem instances).