王岩,潘卫平,陈秋莲,崔耀东.单一尺寸长方体三维装箱问题的一种求解算法[J].包装工程,2015,36(11):96-99.
WANG Yan,PAN Wei-ping,CHEN Qiu-lian,CUI Yao-dong.An Algorithm for Solving the Problem of Three-dimensional Packing of Single-sized Cuboids[J].Packaging Engineering,2015,36(11):96-99. |
| 单一尺寸长方体三维装箱问题的一种求解算法 |
| An Algorithm for Solving the Problem of Three-dimensional Packing of Single-sized Cuboids |
| 投稿时间：2014-11-25 修订日期：2015-06-10 |
| DOI： |
| 中文关键词: 三维装箱 层装载 动态规划 背包问题 |
| 英文关键词: three-dimensional packing layer loading dynamic programming knapsack problem |
| 基金项目:国家自然科学基金 （61363026， 71371058）； 广西自然科学基金 （2014GXNSFAA118357） |
|
| 摘要点击次数: |
| 全文下载次数: |
| 中文摘要: |
| 目的 研究单一尺寸长方体物品的三维装箱问题， 即在一个给定的箱子中装入尽可能多的单一尺寸长方体物品。方法 采用分层装载方案简化装载操作， 首先运用动态规划技术确定所有层中长方体物品的排列方式； 然后求解一维背包问题确定箱中层的最优组合， 得到最优装载方案。将文中算法与文献中三维装箱算法进行对比。结果 文中算法生成的装载方案箱体空间利用率由文献中三维装箱算法的98.10%提高到了99.14%。结论 文中算法可以在合理的时间内得到装载操作简单、 箱体空间利用率较高的装载方案。 |
| 英文摘要: |
| This paper discussed the issue of three-dimensional packing of single-sized cuboid items, namely, arrangement of single-sized cuboid items in a given box as much as possible. Using the hierarchical loading scheme to simplify the loading operation, firstly the dynamic programming technique was used to determine the arrangement of cuboids in all layers, then the one-dimensional knapsack problem was solved to determine the optimal combination of the layers in the box, thus obtaining the optimal loading scheme. The algorithm in this paper was compared with other three-dimensional packing algorithms in literatures. The experimental results showed that the algorithm in this paper can work out a loading scheme which increased the utilization rate of box space from 98.10% to 99.14%. This algorithm can achieve a loading scheme with simple operation and high utilization rate of box space in reasonable time. |
|
查看全文
查看/发表评论 下载PDF阅读器 |
| 关闭 |
渝公网安备 50010702501716号