求解长方体Packing问题的捆绑穴度算法

Cuboid Arrangement Approach Based on Caving Degree for Solving the Cuboid Packing Problem

在穴度方法的基础上结合捆绑策略,为三维欧氏空间中长方体Packing问题的求解提供了一种高效的启发式算法.试算了由Loh和Nee于1992年提出的15个经典算例,对其中的困难算例LN2,取得了98.2%的空间利用率,比目前的最好纪录高1.6个百分点;对另一个困难算例LN6,取得了96.2%的空间利用率,与目前的最好纪录持平;对其他13个较为容易的算例均取得了最优的布局,与目前的最好纪录持平.总体而言,15个算例的平均空间利用率为70.96%,在整体空间利用率上达到了较好的效果.

Based on the caving degree method, this paper proposes a heuristic approach to solve the cuboid packing problem by incorporating the cuboid arrangement strategy. Experiments on 15 classic LN benchmark instances, performed by Lob and Nee in 1992, have shown that this approach has the potential of performing very well. In the difficult instance of LN2, it achieved a volume utilization of 98.2%, which is an improvement from the current best record by 1.6%. In another difficult instance of LN6, it achieved a volume utilization of 96.2%, which matches that of the current best record. For each of the other 13 instances, it maintains optimal layout that packs all cuboid items into the container, matching current best record. As a whole, the average volume utilization on the 15 LN instances is 70.96%.