一种带脆度的尺寸可变装箱问题  

Variable-sized bin-packing problem with fragility

作　　者：刘林浩[1] 杨鼎强[1] 王晨[2] 

机构地区：[1]长沙理工大学计算机与通信工程学院,长沙410004 [2]湖南现代物流职业技术学院物流信息系,长沙410131

出　　处：《计算机工程与应用》2013年第12期263-266,共4页Computer Engineering and Applications

基　　金：湖南省科技厅科技计划资助项目(No.2011GK3120)

摘　　要：作为经典装箱问题的扩展,尺寸可变装箱问题在现实生活中有着极高的应用背景。分析了尺寸可变装箱问题在解决货物装载运输问题上的不足,由此提出了一种带脆度的尺寸可变装箱问题。除了经典装箱问题中物品体积和箱子容量这两个参数,还引入了物品类型和箱子脆度等参数,给出了相关的数学模型。在经典的FFD(First Fit Decreasing)算法的基础上进行了推广,提出了新的启发式算法NFFD,它对箱子的特性进行了预处理,再进行装箱。分析了该算法的复杂性。对NFD、FFD和NFFD算法进行了数值模拟实验,实验结果表明,在相关参数符合均匀分布的条件下,NFFD算法的效果是最好的。As the efftension of classical bin-packing problem, variable-sized bin-packing problem has many important applications. Analysis of the variable size bin packing problem in how to deal with the shortcomings on the issue of transport of cargo, a new variable-sized bin-packing problem with fragility is given. The type of objects and fragility of bins are introduced, as well as the volume of the objects and the capacity of the bins, and math model is established. On the basis of classical First Fit Decreasing （FFD） algorithm, a new heuristic algorithm NFFD is presented, in which inputs are preprocessed by the custom property of item before packing, and the algorithmic complexity is analyzed. By comparing the performance of three algorithms with numerical experiments under the parameters which are uniformly distributed, the effect of NFFD algorithm is the best.

关 键 词：装箱问题 脆度 尺寸可变 降序首次适应算法(FFD) 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]