A pure quasi-human algorithm for solving the cuboid packing problem

作者：Huang WenQi; He Kun^*

来源：Science in China - Series F: Information Sciences , 2009, 52(1): 52-58.

DOI：10.1007/s11432-009-0005-0

• packing problem
• NP-hard
• heuristic
• quasi-human approach
• caving degree

We excavate the wisdom from an old Chinese proverb "gold corner, silver side and strawy void", and further improve it into "maximum value in diamond cave" for solving the NP-hard cuboid packing problem. We extract, integrate and formalize the idea by west modern mathematical tools, and propose a pure quasi-human algorithm. The performance of the algorithm is evaluated on two sets of public benchmarks. For 100 strongly heterogeneous difficult benchmarks, experiments show an average packing utilization of 87.31%, which surpasses current best record reported in the literature by 1.83%. For 47 difficult benchmarks without orientation constraint, experiments show an average volume utilization of 92.05%, which improves current best record reported in the literature by 1.05%.

• 出版日期2009-1
• 单位华中科技大学