| 摘要: |
| 在穴度方法的基础上结合捆绑策略,为三维欧氏空间中长方体Packing 问题的求解提供了一种高效的启发式算法.试算了由Loh 和Nee 于1992 年提出的15 个经典算例,对其中的困难算例LN2,取得了98.2%的空间利用率,比目前的最好纪录高1.6 个百分点;对另一个困难算例LN6,取得了96.2%的空间利用率,与目前的最好纪录持平;对其他13 个较为容易的算例均取得了最优的布局,与目前的最好纪录持平.总体而言,15 个算例的平均空间利用率为70.96%,在整体空间利用率上达到了较好的效果. |
| 关键词: 三维布局 装箱 拟人 穴度 捆绑 |
| DOI：10.3724/SP.J.1001.2011.03799 |
| 分类号: |
| 基金项目:国家自然科学基金(60773194); 中央高校基本科研业务费(HUST 2010MS099) |
|
| Cuboid Arrangement Approach Based on Caving Degree for Solving the Cuboid Packing Problem |
|
HE Kun, HUANG Wen-Qi
|
|
School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China
|
| Abstract: |
| 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 Loh 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%. |
| Key words: three-dimensional packing container loading quasi-human caving degree cuboid arrangement |
