基于母板滑动策略的大理石板材排样算法

A Method for Packing Marble Slabs Based on Original Plate Sliding Strategy

摘要

为了解决大理石板的下料问题，确保成品矩形板材的纹理和色差一致，同时提高材料的利用率，采取轮廓提取算法对大理石母板可排样区域进行轮廓提取，提出了基于母板滑动策略的矩形件排样方法。采用齐头切约束下的最低水平线算法构建样件域，提出融合人工蜂群算法和黑寡妇算法的混合算法（ABWO）对样件域进行优化。通过母板在样件域中进行滑动与旋转寻优，以母板填充率作为评价指标，实现了最优排样方案的高效求解。实验结果表明：在单一规格矩形的排样实验中，所提方法排样时间缩短90%以上，排样填充率与传统方法相当，排样结果满足一刀切约束，有利于后续切割下料；非单一规格矩形排样实验中，采用ABWO算法对零件排入顺序进行优化，样件域填充率提高5%。结合母板滑动策略，最终排样填充率与传统排样方法相比提高了3%。

Abstract

In order to solve the issues of cutting marble slabs and ensure consistent texture and color difference in the final rectangular panels while improving material utilization， a contour extraction algorithm was adopted to extract the contours of the usable areas on the original marble plate and a rectangle packing method was proposed based on an original plate sliding strategy. The lowest horizontal search algorithm under the guillotine constraint was used to construct the part domains and the ABWO algorithm， which integrates the artificial bee colony algorithm and the black widow optimization algorithm was introduced to optimize the part domains. By sliding and rotating the original plate within the part domains and using the utilization rate as an evaluation metric， an efficient solution for the optimal cutting scheme was achieved. The experimental results indicate that in the packing experiments with single size rectangular parts， the proposed method reduces the packing time by more than 90%， while achieving a filling rate comparable to traditional methods. The packing results meet the guillotine constraint， which is beneficial for subsequent cutting processes. In the experiments with non-single size rectangular parts， the implementation of the ABWO algorithm optimizes the order of parts placement， resulting in a 5% increase in the filling rate of the part domains. By combining part domains with the original plate sliding strategy， the final filling rate is improved by 3% compared to traditional packing methods.

Graphical abstract

关键词

大理石 / 板材下料 / 齐头切约束 / 最低水平线算法 / 启发式算法

Key words

marble / sheet cutting / guillotine constraint / lowest horizontal search algorithm / heuristic algorithm

0 引言

用于建筑领域的大理石板材通过将天然大理石荒料切割成大理石母板，然后对母板进行矩形板材下料获得。大理石母板普遍存在一定的缺陷，如缺口、颜色差异、裂纹等。为了装修风格的整体美观，通常情况下不能将存在颜色差异的区域排在同一块成品中，同时在切割下料时还应避开缺口、裂纹等缺陷。这就要求在排样下料前对大理石母板进行精确提取。然而，存在颜色差异的区域、缺口和裂纹一般都是不规则的，即排样时实际的母板是不规则的形状，因此，不规则母板条件下的矩形排样问题是大理石板材下料过程中最常见的问题，即需要将相同尺寸或不同尺寸的矩形轮廓最优地排列在一个或多个较大尺寸的不规则母板上。通过合理的排样，可以最大限度地利用大理石板材，减少废料，提高材料利用率。

二维排样问题主要涉及零件定位策略和定序策略^［1-2］两个方面。定位策略使样件与样件、样件与母板之间实现紧密靠接，且不发生重叠；定序策略是优化样件排入母板的先后次序。在定位策略方面，贾志欣等^［3］提出了最低水平线算法，排样过程中记录目标区域中已经排放的矩形零件的高度和矩形件所形成的最高边框线，便于进行下一个零件的排样；李满江等^［4］将所有未排样的区域进行矩形划分，提出剩余矩形算法，将矩形件或类矩形件进行动态排样；刘璐^［5］在此基础上引入最大高度，优先将零件排入位置最低的剩余矩形空间内。不规则母板的边界可能存在曲线、凹陷或凸出部分，这增加了排样的复杂程度。顾振华等^［6］采用轨迹线法生成内拟合多边形（IFP），实现了矩形件在不规则母板中的下料。袁哲等^［7］建立了凸板材区域中单一尺寸矩形件排样算法的数学模型，再结合启发式算法求解该模型，取得了较好的效果。YUAN等^［8］采用斜率算法来获取不规则母板和矩形件的IFP，并结合树搜索方法实现不规则母板情况下矩形件的排样。CHEN等^［9］通过改进最低水平线算法，并将母板横向划分为多个子板，计算矩形在子板中的可移动位置，并对边角料进行适当填充，从而实现在带有缺陷的石板中进行矩形板材的下料。

在非单一规格矩形件的排样问题中，不同的排样顺序会导致最终的材料利用率差异巨大。针对这一问题，研究人员提出了众多启发式、元启发式算法和精确搜索方法^［10-11］。MIRJALILI等^［12］从狼群的等级制度和捕食猎物等活动中获得启示，抽象出一种群体智能算法——灰狼算法（GWO）。罗强^［13］在此基础上采用十进制编码，重新定义了狼与狼之间的距离，离散化设计了狼群游走、包围与围猎等搜索行为，提出一种十进制的编码GWO。全雪峰等^［14］对模拟退火算法进行改进，避免了由于温度下降过快而导致的丢失极值点问题和温度下降过慢而导致的算法收敛速度降低的问题。黑寡妇优化算法^［15］（BWO）是受黑寡妇蜘蛛独特的交配行为启发而提出的，算法在早期收敛方面具有优势，突变过程控制搜索过程从全局阶段转向局部阶段，推动向最佳解决方案的逼近。人工蜂群算法^［16］（ABC）因其简单、鲁棒性好而被广泛应用于求解组合优化问题，具有较好的全局搜索能力。在这种方法中，个体的解决方案通过模拟蜜蜂觅食的过程来迭代改进。然而，标准的ABC算法在复杂的搜索空间中可能陷入局部最优解，这促使人们探索ABC算法的增强变体，以提高其搜索能力和整体性能。

当前，矩形母板排样问题的相关研究已取得了显著的成果。研究人员采用最左最下（BL）、剩余矩形算法等多种定位策略，旨在高效合理地在母板上排布矩形零件，以最大程度地减少材料浪费，提高材料利用率。在母板不规则的情况下，除了定位策略外，需要采用内拟合多边形法或移动碰撞法来确定样件可行的放置位置，而这些方法计算复杂，在非凸多边形母板情况下处理齐头切约束效果不理想。为解决不规则母板下矩形排样问题，本文提出了一种基于不规则母板滑动策略的二维矩形排样方法，该方法先以大理石齐头切割工艺为约束构建矩形样件排样区域（简称“样件域”），然后通过动态调整不规则母板在样件域中的位置和角度，让不规则母板“框出”尽可能多的样件。将黑寡妇算法中的变异过程引入人工蜂群算法，提出混合算法（ABWO）。针对非单一规格矩形排样，采用ABWO算法对样件域进行优化，进一步提高排样填充率。

1 排样区域分割与轮廓提取算法

在大理石板材加工领域，排样前对母板轮廓的精确提取至关重要，尤其是针对具有明显色差特性的大理石坯料，不同的色彩区域对应不同的石材纹理和颜色。为了合理利用石材资源，应该根据这些特性进行区域分割，确保不同色系的坯料区域用于适配零件的下料，从而提高最终产品的整体观感。以图1a中原始大理石母板为例，根据大理石母板不同区域的颜色差异，大理石母板可分为图1b所示的4个可排样区域。为了便于表示排样区域，本文将一个大理石母板中颜色样式i的第j个区域命名为Ai-j，例如，A1-1表示颜色样式1的第1个区域，A2-1表示颜色样式2的第1个区域。

1.1 基于双边滤波的大理石图像降噪

图像上的噪声通常表现为引起较强视觉效果的单独像素点或一整片像素点，往往是在图像获取过程中或在图像信号传输过程中产生。由于信号的记录设备和传输介质的不完善，大理石图像（母板图像）一般都会不可避免地引入噪声。这些噪声严重影响大理石图像的质量，在一定程度上干扰后续对大理石的颜色筛选和对母板的提取。

为解决图像噪声对大理石的颜色筛选和对母板提取的干扰，本文采用双边滤波对大理石图像进行处理。双边滤波是一种组合滤波，可同时考虑像素点的值域信息和空域信息。图像的像素值在空间中的变化渐进且缓慢，相邻的像素点比较相似。双边滤波的基本思路就是在高斯滤波的基础上加入了像素值权重项，在考虑空间距离因素的同时考虑像素值差异的影响，在像素值相近的地方设置更大的权重。以图2a中的原始大理石板图像为例，使用双边滤波算法处理，结果如图2b所示，可以看出，双边滤波在抑制噪声的同时很好地保留了边缘信息。

1.2 HSV颜色空间下的大理石图像二值化

本文提出的方法主要针对存在色差的天然大理石初始板图像，因此在提取大理石轮廓的同时，还需要将具有色差的石板区域进行分割。为了更准确地提取母板信息，本文对经过滤波处理后的图像在HSV颜色空间下进行二值化处理。

掩模的概念源于半导体行业的“底片”，图像处理中主要用于提取感兴趣区域、屏蔽图像区域和结构特征提取。将图像在HSV颜色空间下进行二值化处理，可以更好地区分大理石色差区域，从而实现更精确的轮廓掩模提取。本文对色相、饱和度和明度参数进行参数寻优，选择最佳的参数组合来提取大理石板图像的初始掩模图像，如图3所示。

从图3中看出，初始掩模图像中存在一些噪声区域，不利于进一步的轮廓提取。为了消除这些噪声，本文进一步采用掏空内部点的方法进行图像处理。具体来说，如果某个黑色点周围的n×n邻域范围内的点都是白色，则将该点变为白色。通过设置不同的n值，可以对掩模图像中大小不一的干扰点进行有效的“掏空”处理，最终获取“干净”的掩模图像，如图4所示。

1.3 排样区域的轮廓提取

采用Canny算子的图像边缘检测方法来提取天然大理石初始坯料的轮廓顶点坐标。首先，通过高斯核卷积滤波进行图像降噪；然后，计算图像梯度来识别像素值的突变；接着，使用非极大值抑制法细化边缘到一个像素宽度，以保留最重要的边缘；最后，采用双阈值处理，高于高阈值的像素点保留为边缘，低于低阈值的点被剔除。该方法能够有效地检测出图像中的边缘，同时过滤掉噪声和不明显的线条，最终的母板提取结果如图5所示。

通过Canny算子提取到的轮廓数据形状复杂，用于排样过程会导致计算量增加。本文采用Zhang-Suen算法^［17］对轮廓进行骨架提取从而降低母板形状复杂度。该方法首先是查找非骨架点。以图6的像素图为例，对于不是零值的像素点P₁，考虑其周围的8个邻域像素点P₂~P₈。

第一阶段，如果满足

\left.\begin{array}{l}\mathrm{2}\le B\left(P_{\mathrm{1}}\right)\le \mathrm{6}\\ A\left(P_{\mathrm{1}}\right)=\mathrm{1}\\ P_{\mathrm{2}}{P}_{\mathrm{4}}{P}_{\mathrm{6}}=\mathrm{0}\\ P_{\mathrm{4}}{P}_{\mathrm{6}}{P}_{\mathrm{8}}=\mathrm{0}\end{array}\right\}（1）

则删除该像素点，否则保留。

其中，A（P₁）表示按P₂→P₉→P₂顺序，从0变为1的次数；B（P₁）表示8邻域范围内非零像素个数。以图7所示的像素图为例，A（P₁）=2，B（P₁）=3。

第二阶段，如果满足

\left.\begin{array}{l}\mathrm{2}\le B\left(P_{\mathrm{1}}\right)\le \mathrm{6}\\ A\left(P_{\mathrm{1}}\right)=\mathrm{1}\\ P_{\mathrm{2}}{P}_{\mathrm{4}}{P}_{\mathrm{8}}=\mathrm{0}\\ P_{\mathrm{2}}{P}_{\mathrm{6}}{P}_{\mathrm{8}}=\mathrm{0}\end{array}\right\}（2）

则删除该像素点，反之，则保留该像素点。

最终，大理石板被提取出这三部分作为排样母板，如图8所示。

2 基于不规则母板滑动策略的矩形排样算法

提出的基于不规则母板滑动策略的矩形排样算法的主要思想是让母板在紧密排列的样件区域内进行移动和旋转，让母板尽可能多地去“框入”样件，因此，算法整体由样件域构建和不规则母板滑动策略两部分组成，具体流程如图9所示。

2.1 样件域构建

2.1.1 放置算法

齐头切是一种常用的切割方式，通常用于石材、木材、金属等材料的加工。该方法主要是将工件按照垂直于其边缘的方向进行切割，以使切割边缘保持平直且与工件的一侧边缘平行。齐头切有利于实现切割效率最大化，还可以降低切割过程中出错的风险，确保切口的精确性和一致性。通过一次性切割可减少调整机器和重新定位材料的时间，从而提高生产效率。在石材加工行业中，石材本身具有脆硬特性，齐头切的切割方式还可以防止切割过程中板材出现裂纹和崩碎。

本文考虑石材加工过程中齐头切的约束，在最低水平线算法中引入分层策略作为构建样件域的放置算法，如图10所示。最低水平线算法在每次排入样件时都会记录当前的最低水平线位置。在排入样件时，选择水平线最低的位置进行样件放置。如果无法再在当前层排入任何样件，本文选择该层水平线最高处，并将该水平线扩展至与母板等宽，作为下一层排样的初始高度。如此逐层排入所有样件，从而形成样件域。

2.1.2 基于ABWO算法的排样顺序优化算法

在构建单一规格矩形的样件域时，样件的排入顺序不会影响最终的样件域布局，而对于非单一规格矩形样件，排入顺序对所构建样件域的紧凑程度有重要影响。本文所提出的排样方法不同于传统的逐一将样件排入母板的模式，而是通过母板在样件区域中进行滑动，搜索最佳的排样布局方案。通过顺序优化算法对构建样件域时的排样顺序进行优化，从而保证紧凑的样件域布局，有利于进一步提高最终的排样填充率。对于大规模的排样问题，元启发式搜索算法能够提供较好的可行解决方案，在工程中具有广泛的应用。通过在ABC算法中引入BWO算法中的变异策略，本文提出一种样件顺序优化混合算法（ABWO）。算法的具体步骤如下。

1）算法参数设置。设置人工蜂群算法中的蜜源数N和蜜源最大停滞不变次数t_{\mathrm{l}\mathrm{i}\mathrm{m}}，并且保持蜜源数、雇佣蜂和观察蜂数量相等。

2）种群初始化阶段。采用下式对种群进行随机初始化：

x_{ij}=x_{\mathrm{l}\mathrm{b}}+r(x_{\mathrm{u}\mathrm{b}}-x_{\mathrm{l}\mathrm{b}})（3）

式中：x_{ij}为蜜源i在第j个维度的值（i=1，2，…，N；j=1，2，…，D）；r为（\mathrm{0,1}）范围内的随机数；x_{\mathrm{u}\mathrm{b}}、x_{\mathrm{l}\mathrm{b}}分别为蜜源搜索范围的上下限。

产生N个初始可行解，这些初始解即为蜜源的位置，同时也是雇佣蜂的位置。

3）雇佣蜂阶段。雇佣蜂会在当前可行解附近搜索新的解（蜜源），并计算新解的适应度值。如果新解的适应度值高于原有解的适应度值，则说明新解的质量高于当前解，此时，可以直接用新解代替当前解。若新解的适应度值低于原有解的适应度值，此时当前蜜源的停滞次数加一。新蜜源的更新过程如下：

v_i=x_i+\phi \left(x_i-x_k\right)（4）

式中：x_k为在种群随机产生的一个雇佣蜂x_i的邻居蜜蜂，k=1，2，…，N，且k\ne i；\phi \in (-\mathrm{1,1})。

4）观察蜂阶段。通过轮盘赌策略挑选雇佣蜂作为观察蜂的搜索位置。雇佣蜂所在位置的蜜源品质越高，即适应度值越高，它被选择的概率就越大。随后，观察蜂在雇佣蜂所在的蜜源周围继续寻找新的蜜源，此时，新蜜源的更新过程规则按式（4）。在对新产生的蜜源进行适应度计算后，对新旧蜜源进行比较。如果新蜜源的适应度值高于原蜜源的适应度值，可以直接用新蜜源代替当前蜜源。反之保持不变，当前蜜源停滞次数加一。轮盘赌过程中雇佣蜂被挑选的概率公式为

P_i=f_i/{\displaystyle \sum _{n=\mathrm{1}}^N}{f}_n（5）

f_i={\displaystyle \sum _{j=\mathrm{0}}^m}{w}_j{h}_j（6）

式中：P_i为雇佣蜂x_i被选中的概率；f_i为雇佣蜂x_i所在蜜源的适应度值；w_j、h_j分别为母板框入样件j的宽度和高度；m为框入样件的数量。

5）侦察蜂阶段。蜜源i未更新次数t_i达到限制次数t_{\mathrm{l}\mathrm{i}\mathrm{m}}时，这个蜜源就会被遗弃。此时，处于该位置的雇佣蜂角色将变为侦察蜂，从搜索空间中随机寻找新的蜜源，然后直接用找到的新蜜源代替原先被遗弃的蜜源。在此过程中，侦察蜂产生新蜜源的方式为式（4）。这一阶段避免了算法陷入局部最优解，保证算法的全局寻优能力。

6）变异阶段。从种群中随机抽取一个个体，随机交换个体中的两个元素，如图11所示。此阶段与遗传算法的基因互换阶段类似，目的是在局部搜索阶段引入随机因素，从而避免算法陷入局部最优。

2.2 不规则母板滑动策略

不同于传统的样件排入母板中的方式，本文所提出的基于不规则母板滑动策略的矩形排样方法中母板在已排好的样件域内移动，母板的位置决定了最终排样效果。如图12所示，本文将母板在样件域内沿水平方向和竖直方向进行滑动，并且考虑旋转，然后计算某一位置下母板的填充效果。图12a展示了母板滑动的过程。

本文中母板采用多边形的形式进行描述，在实现母板的水平竖直滑动时，仅需要让多边形的所有顶点的横坐标或纵坐标加上移动步长即可。母板所有顶点在样件域中旋转的具体公式为

\left[\begin{array}{c}{x}^{\text{'}}\\ y^{\text{'}}\end{array}\right]=\left[\begin{array}{cc}\mathrm{c}\mathrm{o}\mathrm{s}\theta & -\mathrm{s}\mathrm{i}\mathrm{n}\theta \\ \mathrm{s}\mathrm{i}\mathrm{n}\theta & \mathrm{c}\mathrm{o}\mathrm{s}\theta \end{array}\right]\left[\begin{array}{c}x\\ y\end{array}\right]（7）

考虑对处理后的大理石母板轮廓进行0°、90°、180°和270°四个角度的旋转，从而寻找较为合适的母板旋转角度。

3 实验与分析

3.1 单一规格矩形排样

为了验证基于不规则母板滑动策略的矩形排样方法的实际效果，使用Python编程语言实现该方法，并与传统排样方法^［7-8］进行对比。本节在不规则母板中进行单一规格矩形样件的排样实验。

图13所示为传统排样方法与本文所提出的基于不规则母板滑动策略的矩形件排样方法的对比结果，排入样件个数均为54。本文方法在保证紧凑排样结果的同时，考虑了一刀切的工艺约束，有利于后续的切割处理。为了进一步验证本文方法的适用性，选取9个不规则母板进行单一规格矩形件排样实验，结果对比如表1所示。由表1可以看出，在排入零件数量方面，本文方法与传统排样方法整体相差不多，板材利用率均超过72%。对于不规则母板9，本文方法的提高效果最佳，相比传统排样方法，利用率提高5.64%。本文方法的优点在于保证良好排样效果的同时，还大幅提高了排样速度。最终，所有不规则母板的排样结果如图14所示。

3.2 非单一规格矩形排样

3.2.1 样件域构建

为了保证样件域紧凑的排样布局，本文提出ABWO算法，在构建样件域时对非单一规格矩形样件的排入顺序进行优化。为验证算法的有效性，分别采用禁忌搜索算法（Tabu）、人工蜂群算法、黑寡妇优化算法以及本文提出的ABWO算法对样件域进行排样布局优化，每组实验运行3次，获取平均排样利用率，结果如表2所示。由表2可以看出，采用禁忌搜索算法优化样件域，平均利用率最低，人工蜂群算法和黑寡妇优化算法的表现相差不大，略优于禁忌搜索算法。采用ABWO算法对样件域进行布局优化，最终平均利用率为93.839%，与单一算法相比提高了5%左右。

3.2.2 基于不规则母板滑动的矩形排样方法

本节采用欧洲运筹学联合会切割与布局问题兴趣小组官网中的t_n数据集（https：∥www.euro-online.org/websites/esicup）。对于基于不规则母板滑动策略，分别采用ABC算法、BWO算法和ABWO算法对样件域进行布局优化对比，最终的排样布局如图15所示。表3所示为不同顺序优化算法下两块母板（母板A和母板B）最终的材料利用率。结果表明，采用ABWO顺序优化算法结合母板滑动策略进行排样，两块母板的排样填充率均超过了90%，效果优异。本文方法比传统排样方法的利用率提高了3%左右；通过对顺序优化算法的改进，结合母板滑动策略，最终排样填充率提高了3%~8%。

最后，对提取的大理石母板轮廓进行非单一规格矩形排样实验，图16和图17分别为样件域优化前后基于母板滑动策略下所获得的排样结果，可以看出，采用排样顺序优化算法对样件域进行布局优化后能够提高排样填充率。

4 结论

1）采用双边滤波算法对大理石坯料图像进行滤波处理能够有效去除原始图片中的噪声，应用掏空内部点法处理大理石坯料掩模图像的干扰点，得到“干净”的掩模。采用Canny边缘检测算法进行母板区域的轮廓提取，并对得到的母板轮廓点进行骨架提取，实现了大理石坯料的色差分区和排样区域的轮廓提取。

2）提出了基于不规则母板滑动策略的二维矩形件排样方法。相较传统的内拟合多边形算法结合启发式算法的排样方式，该方法在大大降低计算复杂性的同时保持了较好的材料利用率。针对矩形件的排样问题，本文方法采用带有齐头切约束的最低水平线算法构建样件域。为了获取更好的布局效果，本文方法以母板的填充面积为评价指标，通过母板在样件域中进行滑动与旋转，寻找确定最优的布局方式。测试结果表明，在对单一规格的矩形件排样中，材料利用率均在72%以上，且与传统排样方法相比利用率有所提高，算法平均运行时间缩减90%以上。

3）基于人工蜂群算法和黑寡妇优化算法提出的混合算法ABWO能够提高非单一规格矩形件排样结果的材料利用率。ABWO算法在人工蜂群算法的框架上加入了黑寡妇优化算法的变异机制，从而改进算法的邻域搜索能力，使算法尽可能的跳出局部最优。最终实验表明，采用ABWO算法进行样件域构建时，样件域的填充率均在93%以上，平均利用率达到93.839%，与其他顺序优化算法对比效果提高了将近5%；在与基于不规则母板滑动策略的矩形排样方法结合使用后，排样填充率得到提高。

参考文献

[1] 韩伟， 张子成. 基于模拟退火的贯通约束不规则排样［J］. 中国机械工程， 2016， 27（24）：3326-3331.

[2] HAN Wei， ZHANG Zicheng. Through Constrained Irregular Nesting Based on Simulated Annealing ［J］. China Mechanical Engineering， 2016， 27（24）：3326-3331.

[3] GUO B S， HU J W， WU F H， et al. Automatic Layout of 2D Free-form Shapes Based on Geometric Similarity Feature Searching and Fuzzy Matching［J］. Journal of Manufacturing Systems， 2020， 56：37-49.

[4] 贾志欣， 殷国富， 罗阳. 二维不规则零件排样问题的遗传算法求解［J］. 计算机辅助设计与图形学学报， 2002， 14（5）：467-470.

[5] JIA Zhixin， YIN Guofu， LUO Yang. Two Dimensional Irregular Parts Packing with Genetic Algorithm［J］. Journal of Computer-aided Design & Computer Graphics， 2002， 14（5）：467-470.

[6] 李满江， 孟祥旭， 王志强. 矩形件和任意多边形排样问题的算法及应用［J］. 贵州工业大学学报（自然科学版）， 2002， 31（4）：126-130.

[7] LI Manjiang， MENG Xiangxu， WANG Zhiqiang. Algorithm and Application of Rectangular and Polygonal Packing Problem［J］. Journal of Guizhou University of Technology （Natural Science Edition）， 2002， 31（4）：126-130.

[8] 刘璐. 基于遗传算法的钣金排样系统研究［D］. 西安：西安工业大学， 2014.

[9] LIU Lu. Research on Sheet Metal Layout System Based on Genetic Algorithm［D］. Xi'an：Xi'an Technological University， 2014.

[10] 顾振华， 何援军， 刘胡瑶. 二维不规则图形排料CAD系统的设计［J］. 工程图学学报，2008 （2）：17-22.

[11] GU Zhenhua， HE Yuanjun， LIU Huyao. The Design of 2D Irregular Nesting CAD System［J］. Journal of Graphics， 2008（2）：17-22.

[12] 袁哲， 邓长亮， 张岩. 不规则凸域板材中单一尺寸矩形排样算法［J］. 沈阳建筑大学学报（自然科学版），2018，34（1）：158-164.

[13] YUAN Zhe， DENG Changliang， ZHANG Yan. Study on Algorithm of Single Size Rectangular Layout in Irregular Convex Plates［J］. Journal of Shenyang Jianzhu University （Natural Science）， 2018， 34（1）：158-164.

[14] YUAN Z， SONG X， AN D， et al. Heuristic Approach for Packing Identical Rectangular Tiles in an Irregular Marble Slab［J］. Mathematical Problems in Engineering， 2022， 2022：1-13.

[15] CHEN K， ZHUANG J， ZHONG S， et al. Optimization Method for Guillotine Packing of Rectangular Items within an Irregular and Defective Slate［J］. Mathematics （Basel）， 2020， 8（11）：1914.

[16] 董德威， 颜云辉， 张尧， 等. 矩形件优化排样的自适应遗传模拟退火算法［J］. 中国机械工程， 2013， 24（18）：2499-2504.

[17] DONG Dewei， YAN Yunhui， ZHANG Yao， et al ．Adaptive Genetic Simulated Annealing Algorithm in

[18] Optical Layout of Rectangular Parts［J］. China Mechanical Engineering， 2013， 24（18）：2499-2504.

[19] 梁利东， 钟相强. 粒子群算法在不规则件排样优化中的应用［J］. 中国机械工程， 2010， 21（17）：2050-2052.

[20] LIANG Lidong， ZHONG Xiangjiang. Applications of Particle Swarm Optimization for Solving Irregular Part Nesting Problems［J］. China Mechanical Engineering， 2010， 21（17）：2050-2052.

[21] MIRJALILI S， MIRJALILI S M， LEWIS A D. Grey Wolf Optimizer［J］. Advances in Engineering Software， 2014， 69：46-61.

[22] 罗强. 基于灰狼算法的矩形优化排样及其在板式家具开料中的应用［D］. 武汉：华中科技大学， 2019.

[23] LUO Qiang. Rectangular Layout Optimization Based on Gray Wolf Algorithm and its Application in the Cutting of Panel Furniture［D］. Wuhan：Huazhong University of Science and Technology， 2019.

[24] 全雪峰， 沈继涛. 基于模拟退火剩余矩形算法的矩形件排样［J］. 软件， 2016， 37（3）：27-29.

[25] QUAN Xuefeng， SHEN Jitao. Optimum Packing of Rectangles Based on Simulated Annealing and Surplus Rectangle［J］. Software， 2016， 37（3）：27-29.

[26] HAYYOLALAM V， KAZEM A A P. Black Widow Optimization Algorithm：a Novel Meta-heuristic Approach for Solving Engineering Optimization Problems［J］. Engineering Applications of Artificial Intelligence， 2020， 87：1-28.

[27] KARABOGA D， BASTURK B. A Powerful and Efficient Algorithm for Numerical Function Optimization：Artificial Bee Colony（ABC） Algorithm［J］. Journal of Global Optimization， 2007， 39（3）：459-471.

[28] ZHANG T Y， SUEN C Y. A Fast Parallel Algorithm for Thinning Digital Patterns［J］. Communications of the ACM， 1984， 27（3）：236-239.

基金资助

国家自然科学基金(52175488)

河北省教育厅高等学校科技计划(BJ2021045)

河北省中央引导地方科技发展资金(236Z1808G)