改进动态规划算法求解同尺寸物品的装箱问题

The Dynamic Programming Algorithm for Solving Packing Problem of Identical Objects

装箱问题是在一个容量有限的箱内尽可能多的装入各类物品。文中研究同尺寸的物品装箱问题,在一个集装箱中装入大小规格一致的小箱,使集装箱的空间利用率最大,即装入的小箱数量最多。采用分层装载思想和同质条带的布局方式设计装箱方案,利用改进的动态规划算法求解层装的布局问题,使用背包算法求解同质条带内的小箱布局问题。与已有文献算法相比,文中算法的运行速度更快,得到的装箱方案更便捷,利于装箱操作,而且在一定程序上提高了装箱率。使用国际标准尺寸的集装箱和随机尺寸的物品小箱进行实验,结果表明文中算法比传统的动态规划算法有更好的求解效果,可适用于实际的集装箱物品装载。

The packing problem is to pack as many items as possible into a box with limited capacity.This paper studies the pack⁃ing problem of articles of the same size.Small boxes of the same size and specification are packed into a container to maximize the space utilization of the container,that is,the largest number of small boxes are loaded.The packing scheme is designed with the idea of layered loading and the layout of homogeneous strips.The improved dynamic programming algorithm is used to solve the layout problem of layered packing,and the backpack algorithm is used to solve the layout problem of small boxes in homogeneous strips.Compared with the existing literature algorithms,the algorithm in this paper runs faster,the packing scheme obtained is more convenient,conducive to the packing operation,and improves the packing rate in a certain program.The experimental re⁃sults show that the algorithm is better than the traditional dynamic programming algorithm,and can be applied to the actual container loading.