A new heuristic algorithm for cuboids packing with no orientation constraints

The three-dimensional cuboids packing is NP-hard and finds many applications in the transportation industry. The problem is to pack a subset of cuboid boxes into a big cuboid container such that the total volume of the packed boxes is maximized. The boxes have no orientation constraints, i.e. they can be rotated by 90 degrees in any direction. A new heuristic algorithm is presented that defines a conception of caving degree to judge how close a packing box is to those boxes already packed into the container, and always chooses a packing with the largest caving degree to do. The performance is evaluated on all the 47 related benchmarks from the OR-Library. Experiments on a personal computer show a high average volume utilization of 94.6% with an average computation time of 23 min for the strengthened A1 algorithm, which improves current best records by 3.6%. In addition, the top-10 A2 algorithm achieved an average volume utilization of 91.9% with an average computation time of 55 s, which also got higher utilization than current best records reported in the literature. (C) 2007 Elsevier Ltd. All rights reserved.