面向纸板三维装箱问题的剩余空间最优算法  

Optimal Algorithm of Remaining Space for 3D Packing Problem of Paperboard

作　　者：王程 陈正鸣 吕嘉 WANG Cheng;CHEN Zheng-ming;LYU Jia(College of Internet of Things Engineering, Hohai University, Changzhou 213022, China)

机构地区：[1]河海大学物联网工程学院,江苏常州213022

出　　处：《计算机与现代化》2021年第3期28-34,共7页Computer and Modernization

基　　金：国家自然科学基金资助项目(61772172)。

摘　　要：针对瓦楞纸板在装箱过程中遇到的多种实际约束,提出一种基于剩余空间最优和多种实际约束的快速求解算法。该算法先根据纸板的先进后出和组合装载约束,确定纸板的装箱序列,接着将三维装箱问题转换成带高度约束的二维装箱问题,再基于剩余空间最优策略,选择空间的分割方式和纸板的放置方式,并对剩下的空间进行合并和重新分割,从而求解得到纸板装载放置的结果,实现容器空间利用率最高和使用数目最小的目标。通过计算随机算例和实际算例,以及对结果的三维可视化显示,验证该算法能实现多种约束,空间利用率高,运算效率高并具有有效性和实用性。Aiming at the various practical constraints encountered in the packing process of corrugated board,a fast algorithm based on the optimal remaining space and various practical constraints is proposed.Firstly,according to the first in,last out and combination of loading constraints,the packing sequence of paperboard is determined.Then,the three-dimensional packing problem is transformed into a two-dimensional packing problem with height constraints.Based on the optimal strategy of remaining space,the space partition mode and cardboard placement mode are selected,and the remaining space is merged and repartitioned,so as to obtain the result of cardboard loading and placement and achive the goal of the highest utilization rate of container space and the minimum number of container space.Through the calculation of random and practical examples,as well as the three-dimensional visualization of the results,it is proved that the algorithm can achieve a variety of constraints,high space utilization and high operation efficiency.The effectiveness and practicability of the method are verified.

关 键 词：三维装箱问题 剩余空间 多目标 实际约束 瓦楞纸板 

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