A caving degree approach for the single container loading problem

摘要

Inspired by ail old adage "Gold corner, silver side and strawy void", and improved by a new observation "Maximum value ill diamond cave", it new heuristic approach is proposed for solving the three-dimensional single container loading problem. Differing from several previous approaches, its key issue is to pack the outside item into it corner or even a cave in the container such that the item is as compactly and closely as possible with other packed items. Experiments are on two groups of public and difficult benchmarks. For the 47 without-orientation-constraint instances from the OR-Library, experiments indicate an average packing utilization of 94.9%, which improves current best result reported in the literature by 3.9%. For the 800 strongly heterogeneous instances among 1500 representative benchmarks proposed by Bischoff et A., (100 instances in a set), experiments show an average packing utilization of 87.97%, which improves current best record reported ill the literature by 0.28%, Besides, new best records are achieved on the latter five sets among the eight sets of strongly heterogeneous benchmarks. (C) 2008 Elsevier B.V. All rights reserved.