A study of exact methods for container loading problems

The container loading problem, a 3D packing problem, consists of allocating a number of items (usually boxes) inside one or more containers. Different characteristic combinations give rise to different variants of the problem. This study addresses four of these variants: the single knapsack problem (SKP), the single large object placement problem (SLOPP), the multiple heterogeneous large object placement problem (MHLOPP) and the open dimension problem (ODP). The SKP occurs when there exists a single container and a set of strongly heterogeneous boxes to be placed inside the container. By contrast, the SLOPP arises if there is a single container and a set of weakly heterogeneous boxes to be allocated. Finally the MHLOPP concerns a set of boxes requiring placement inside a set of weakly or strongly heterogeneous containers. Although these three problems originate from the same source, the SKP and the SLOPP's objective is to maximize the container's occupied volume, whereas the MHLOPP's is to minimize the number of containers. These three problems assume that containers have fixed dimensions. In the ODP not all dimensions of the container are fixed. The most common scenario in this variant is where two dimensions are fixed (width and height, for example) and the objective is to minimize the remaining dimension. This study compares the most significant exact methods proposed in the literature for the four variants of container loading problems considered. These methods include several discrete and continuous mixed integer programming (MIP) models and a specialized branch-and-bound. Regarding the origin of the MIP models, three were taken from the MHLOPP, two from the SKP and one from the ODP literature. The specialized branch-and-bound was taken from the MHLOPP literature. These methods are adapted so as to enable a clear comparison using classic benchmark datasets from the literature concerning addressed problems. The benchmark datasets consist of different configurations, enabling the evaluation of the methods in distinct situations. Eight benchmark sets are considered, with five consisting of a small number of boxes (up to 15), one from 5 to 100 boxes and the two remaining of a larger number of boxes (at least 100). To analyze the methods, the comparison parameters depend on the particular problem type considered. The number of unallocated boxes and total container volume occupation are the comparison parameters available for the SKP. Since all boxes are already inside the container to begin with in the open dimension problem, the comparison criterion is the value of the minimized dimension. The final results are obtained when the optimal solution is found or the execution time limit is reached. The results obtained suggest which exact methods perform best for each container loading problem category. These results provide further insight and aid in the development of new formulations and matheuristics for the considered problems.Editorial consultation provided by Luke Connolly (KU Leuven).status: publishe