A maximal-space algorithm for the container loading problem. (English) Zbl 1243.90094

Parreño, Francisco; Alvarez-Valdes, Ramón; Tamarit, José Manuel; Oliveira, José Fernando

INFORMS J. Comput. 20, No. 3, 412-422 (2008).

Summary: 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, 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.

MSC:

90B80	Discrete location and assignment
90C27	Combinatorial optimization
90C59	Approximation methods and heuristics in mathematical programming
05B40	Combinatorial aspects of packing and covering

Keywords:

container loading; 3D packing; heuristics; GRASP