A New Quasi-Human Algorithm for the Strongly Heterogeneous Container Loading Problem

This paper presents a new quasi-human heuristic for the three-dimensional container loading problem. The emphasis is on strongly heterogeneous load, which generally finds lower volume utilization than homogeneous or weakly heterogeneous load. The algorithm defines a conception of caving degree to judge how close a corner-occupied packing box is to the boxes already packed in the container. In the basic heuristic, an action with the maximum caving degree is selected to do at each packing step. In the strengthened heuristic, a superior local search strategy is incorporated to improve the solution quality; Top N candidate actions are pseudo executed through the basic algorithm, and the one with the maximum packing utilization is selected to do at each packing step. Experiments on 100 well-known strongly heterogeneous benchmarks show an average packing utilization of 87.26% This improves current best record reported in the literature by 1.78%