一种新的多约束尺寸可变的装箱问题  

New multi-constrained variable-sized bin packing problem

作　　者：杜少波[1] 张国基[1] 刘清[2] 

机构地区：[1]华南理工大学理学院,广州510640 [2]华南理工大学计算机科学与工程学院,广州510640

出　　处：《计算机工程与应用》2011年第19期242-244,248,共4页Computer Engineering and Applications

摘　　要：多约束尺寸可变的装箱问题作为经典装箱问题的扩展,具有极为广泛的应用背景。在以货车运输为主的物流公司的装载环节中,运输成本不仅仅由车厢的空间利用率决定。分析了该类装箱问题与传统的集装箱装载问题的区别,并据此给出了一种新的尺寸可变装箱问题的定义。除了经典装箱问题中物品体积这一参数,还引入了物品类型、箱子类型等参数,建立了数学模型,将经典的FFD(First Fit Decreasing)算法进行了推广,提出了新的算法MFFD,并分析了相关的算法复杂性。最后对FF、FFD以及MFFD算法进行了模拟实验,实验结果表明,在相关参数符合均匀分布的条件下,MFFD算法效果较好。As the extension of classical bin packing problem,the multi-constrained variable-sized bin packing problem has many extensive applications.In the loading section of logistics it has mainly transported by truck,the transportation cost is not only determined by the bin space utilization.In this paper,the difference between truck loading and classical container bin problem is analyzed,a new definition of variable-sized bin packing problem is given based on the analysis.The type of items and bins are introduced in the mathematical model,as well as the volume of the items.On the base of classical First Fit Decreasing（FFD） algorithm,a new algorithm MFFD is presented,and the algorithmic complexity is analyzed.In the simulation experiments,the proposed algorithm MFFD plays a better performance than other algorithms when the parameters are uniform distributed.

关 键 词：装箱问题 多约束 尺寸可变 FFD算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]