Content area
Full text
In this paper, a greedy randomized adaptive search procedure (GRASP) for the container loading problem is presented. This approach is based on a constructive block heuristic that builds upon the concept of maximal space, a nondisjoint representation of the free space in a container.
This new algorithm is extensively tested over the complete set of Bischoff and Ratcliff problems [Bischoff, E. E., M. S. W. Ratcliff. 1995. Issues in the development of approaches to container loading. Omega 23 377-390], ranging from weakly heterogeneous to strongly heterogeneous cargo, and outperforms all the known nonparallel approaches that, partially or completely, have used this set of test problems. When comparing against parallel algorithms, it is better on average but not for every class of problem. In terms of efficiency, this approach runs in much less computing time than that required by parallel methods. Thorough computational experiments concerning the evaluation of the impact of algorithm design choices and internal parameters on the overall efficiency of this new approach are also presented.
Key words: container loading; 3D packing; heuristics; GRASP
History: Accepted by Michel Gendreau, Area Editor for Heuristic Search and Learning; received January 2007; revised June 2007, September 2007; accepted November 2007. Published online in Articles in Advance March 25, 2008.
1. Introduction
The single-container loading problem (CLP) is a threedimensional packing problem in which a large parallelepiped, the container, has to be filled with smaller parallelepipeds, the boxes, available in different sizes and limited quantities, so that empty space is minimized (Figure 1). Under the improved typology for cutting and packing problems proposed by Wäscher et al. (2007), the CLP can be classified as a threedimensional rectangular single large object placement problem (3D SLOPP) if the set of boxes is weakly heterogeneous or as a single knapsack problem (3D SKP) if the set of boxes is strongly heterogeneous. The CLP is an NP-hard problem because the NP-hard onedimensional knapsack problem can be transformed into it.
From the applications point of view, this problem arises in practice whenever containers or trucks have to be filled/loaded with boxes, so that the usage of the container is maximized. The minimization of empty space inside the containers is not only an economic requirement but also an ecological issue, given the...