Journal of Software:2011.22(5):843-851

求解长方体Packing 问题的捆绑穴度算法
(华中科技大学 计算机科学与技术学院,湖北 武汉 430074)
Cuboid Arrangement Approach Based on Caving Degree for Solving the Cuboid Packing Problem
(School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China)
Chart / table
Similar Articles
Article :Browse 4220   Download 3639
Received:June 19, 2009    Revised:December 02, 2009
> 中文摘要: 在穴度方法的基础上结合捆绑策略,为三维欧氏空间中长方体Packing 问题的求解提供了一种高效的启发式算法.试算了由Loh 和Nee 于1992 年提出的15 个经典算例,对其中的困难算例LN2,取得了98.2%的空间利用率,比目前的最好纪录高1.6 个百分点;对另一个困难算例LN6,取得了96.2%的空间利用率,与目前的最好纪录持平;对其他13 个较为容易的算例均取得了最优的布局,与目前的最好纪录持平.总体而言,15 个算例的平均空间利用率为70.96%,在整体空间利用率上达到了较好的效果.
中文关键词: 三维布局  装箱  拟人  穴度  捆绑
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%.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(60773194); 中央高校基本科研业务费(HUST 2010MS099) 国家自然科学基金(60773194); 中央高校基本科研业务费(HUST 2010MS099)
Foundation items:
Reference text:

何琨,黄文奇.求解长方体Packing 问题的捆绑穴度算法.软件学报,2011,22(5):843-851

HE Kun,HUANG Wen-Qi.Cuboid Arrangement Approach Based on Caving Degree for Solving the Cuboid Packing Problem.Journal of Software,2011,22(5):843-851