School of Astronautics, Beihang University, Beijing, China.
PLoS One. 2022 May 31;17(5):e0268514. doi: 10.1371/journal.pone.0268514. eCollection 2022.
The bin packing problem has a wide range of applications in industry. With the upgrade of the task difficulty, the traditional 2d rectangular layout algorithm can no longer meet the needs of modern industry, such as express packing task and exoplanet ore collection task. The express or ore samples come in heterogeneous shapes so they cannot all be treated as rectangular pieces. In this paper, we propose a three-stage method called covering, corner-searching and occupying (C,S&O) to solve the two-dimensional multishape part packing problem. The objective of the packing problem variant is to ensure maximum use of the raw material and minimize the trim loss. The algorithm cannot make use of information about the sequence of future objects that are going to arrive, only knowing the shape and size of the coming one, and the coming part must be packed into the bin immediately after its arrival without buffering or readjusting. The method of C,S&O hybridizes the idea of "gold corners, silver edges and grass belly" in the Chinese game Go and the method of finding picture corners in machine vision. In the first stage, the rectangular bin and the coming part are transformed into matrix representation, and generating the position matrix that indicates possible ways of packing the part into the bin. In the second stage, the suitable layout position of the coming part is obtained using machine vision image processing technology for reference. The third stage is calculating the environment matching degree to determine the current optimal placement orientation. In order to facilitate the display of the simulation results, only three shapes of parts are considered in the simulation, rectangle, circle and triangle. The experimental results show the effectiveness of this method. Consulting the literature, it is found that this paper is the first to propose a layout method for multishape manufacturing parts.
装箱问题在工业中有广泛的应用。随着任务难度的提升，传统的二维矩形布局算法已经不能满足现代工业的需求，例如快递包装任务和系外行星矿石收集任务。快递或矿石样本形状各异，不能都视为矩形块。在本文中，我们提出了一种称为覆盖、角搜索和占用（C，S&O）的三阶段方法，用于解决二维多形状零件的装箱问题。包装问题变体的目标是确保最大限度地利用原材料并最小化修剪损失。该算法不能利用关于即将到来的未来对象的顺序的信息，只能知道即将到来的对象的形状和大小，并且必须在其到达后立即将即将到来的部分装入箱子中，而无需缓冲或重新调整。C，S&O 方法混合了中国围棋游戏中的“金角、银边、草肚皮”思想和机器视觉中寻找图像角的方法。在第一阶段，将矩形箱子和即将到来的部分转换为矩阵表示，并生成表示将部分装入箱子的可能方式的位置矩阵。在第二阶段，使用机器视觉图像处理技术参考获得即将到来的部分的合适布局位置。第三阶段是计算环境匹配度以确定当前的最佳放置方向。为了便于显示模拟结果，在模拟中仅考虑了三种零件形状：矩形、圆形和三角形。实验结果表明了该方法的有效性。查阅文献发现，本文首次提出了一种多形状制造零件的布局方法。
