A reactive GRASP algorithm for the container loading problem with load-bearing constraints

The container loading problem consists in packing a set of boxes of different dimensions into a large container of fixed dimensions, usually with the objective of maximising the container load. In practical problems, besides the geometric constraints of not exceeding the container dimensions and ensuring the non-overlapping of boxes, other requirements may appear, such as total weight, weight balance or support. In this paper we address the problem of maximising container volume utilisation while respecting a set of practical constraints: full support of boxes, allowed orientations and load-bearing capacity. We have developed different heuristics for solving the problem and we have combined them into a GRASP algorithm. The algorithm is composed of a constructive phase with a reactive method for selecting the heuristics which are best for each instance, and an improving phase in which several improvement methods are applied. An extensive computational study shows the efficiency of the proposed procedure. [Received 1 October 2012; Revised 16 May 2013; Accepted 6 June 2013]