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

doi:10.3969/j.issn.1004-132X.2025.10.023

摘要/Abstract

摘要：

为了解决大理石板的下料问题，确保成品矩形板材的纹理和色差一致，同时提高材料的利用率，采取轮廓提取算法对大理石母板可排样区域进行轮廓提取，提出了基于母板滑动策略的矩形件排样方法。采用齐头切约束下的最低水平线算法构建样件域，提出融合人工蜂群算法和黑寡妇算法的混合算法（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.

Key words: marble, sheet cutting, guillotine constraint, lowest horizontal search algorithm, heuristic algorithm

中图分类号:

T985

郭保苏, 王永春, 马健明, 孙万诚, 王世运, 黄传真. 基于母板滑动策略的大理石板材排样算法[J]. 中国机械工程, 2025, 36(10): 2343-2350.

Baosu GUO, Yongchun WANG, Jianming MA, Wancheng SUN, Shiyun WANG, Chuanzhen HUANG. A Method for Packing Marble Slabs Based on Original Plate Sliding Strategy[J]. China Mechanical Engineering, 2025, 36(10): 2343-2350.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: https://www.cmemo.org.cn/CN/10.3969/j.issn.1004-132X.2025.10.023

https://www.cmemo.org.cn/CN/Y2025/V36/I10/2343

图/表 20

图1 具有裂纹和色差的原始大理石板

Fig.1 Original marble slabs with cracks and chromatic aberrations

图2 滤波前后大理石板图像

Fig.2 Images of marble slabs before and after filtering

图3 初始掩模图像

Fig.3 Initial mask image

图4 最终掩模图像

Fig.4 The final mask image

图5 大理石母板轮廓

Fig.5 The outline of the marble plate

图6 3×3像素图

Fig.6 3×3 pixel map

图7 3×3像素图实例

Fig.7 An example of a 3×3 pixel map

图8 待排样母板轮廓

Fig.8 The outline of the plate for packing

图9 基于不规则母板滑动策略的矩形排样方法

Fig.9 Rectangular layout method based on irregular plate sliding strategy

图10 齐头切约束下的最低水平线方法

Fig.10 Lowest horizontal line method under guillotine constraint

图11 变异操作算子

Fig.11 Mutation operator

图12 不规则母板滑动策略与传统排样方法示意图

Fig.12 Schematic diagram of irregular plate sliding strategy and traditional layout method

图13 单一规格矩形排样结果

Fig.13 Single size rectangular layout results

表1 本文方法与传统排样方法的对比结果

Tab.1 The results of comparison between the proposed method and the traditional layout method

No.	传统排样方法		本文方法
No.	排入数量	运行时间/s	排入数量	运行时间/s
1	56	10.211	54	0.159
2	20	2.022	20	0.149
3	28	3.411	26	0.099
4	29	1.252	29	0.092
5	29	4.429	28	0.096
6	42	9.774	41	0.151
7	32	7.841	30	0.098
8	46	23.234	46	0.113
9	105	44.236	113	0.201

图14 9个不规则母板的排样结果

Fig.14 The layout results for 9 irregular plates

表2 4种启发式算法对样件域的布局优化结果 (%)

Tab.2 The layout optimization results of part domain by 4 heuristic algorithms

算法	编号	利用率	平均利用率
Tabu	（1）	87.372	87.616
	（2）	87.685
	（3）	87.790
ABC	（1）	87.592	88.189
	（2）	88.328
	（3）	88.648
BWO	（1）	88.482	88.899
	（2）	89.006
	（3）	89.209
ABWO	（1）	93.719	93.839
	（2）	93.852
	（3）	93.945

图15 不同顺序优化算法下非单一规格矩形排样结果

Fig. 15 Results of non-single size rectangular layout under different sequential optimization algorithms

表3 不同顺序优化算法下非单一规格矩形排样填充率

Tab.3 Filling rate of non-single rectangular layout under different sequential optimization algorithms

母板	填充率/%
母板	传统排样方法	ABC	BWO	ABWO
A	88.33	88.31	85.07	91.85
B	90.43	89.28	84.79	93.63

图16 不规则母板滑动策略下的矩形排样结果

Fig.16 Rectangular layout results based on irregular plate sliding strategy

图17 ABWO顺序优化算法结合不规则母板滑动策略下的矩形排样结果

Fig.17 The results of rectangular layout based on irregular plate sliding strategy combined with ABWO sequential optimization algorithm

参考文献 17

[1]	韩伟，张子成. 基于模拟退火的贯通约束不规则排样［J］. 中国机械工程， 2016， 27（24）：3326-3331.
	HAN Wei， ZHANG Zicheng. Through Constrained Irregular Nesting Based on Simulated Annealing ［J］. China Mechanical Engineering， 2016， 27（24）：3326-3331.
[2]	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.
[3]	贾志欣，殷国富，罗阳. 二维不规则零件排样问题的遗传算法求解［J］. 计算机辅助设计与图形学学报， 2002， 14（5）：467-470.
	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.
[4]	李满江，孟祥旭，王志强. 矩形件和任意多边形排样问题的算法及应用［J］. 贵州工业大学学报（自然科学版）， 2002， 31（4）：126-130.
	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.
[5]	刘璐. 基于遗传算法的钣金排样系统研究［D］. 西安：西安工业大学， 2014.
	LIU Lu. Research on Sheet Metal Layout System Based on Genetic Algorithm［D］. Xi'an：Xi'an Technological University， 2014.
[6]	顾振华，何援军，刘胡瑶. 二维不规则图形排料CAD系统的设计［J］. 工程图学学报，2008 （2）：17-22.
	GU Zhenhua， HE Yuanjun， LIU Huyao. The Design of 2D Irregular Nesting CAD System［J］. Journal of Graphics， 2008（2）：17-22.
[7]	袁哲，邓长亮，张岩. 不规则凸域板材中单一尺寸矩形排样算法［J］. 沈阳建筑大学学报（自然科学版），2018，34（1）：158-164.
	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.
[8]	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.
[9]	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.
[10]	董德威，颜云辉，张尧，等. 矩形件优化排样的自适应遗传模拟退火算法［J］. 中国机械工程， 2013， 24（18）：2499-2504.
	DONG Dewei， YAN Yunhui， ZHANG Yao， et al ．Adaptive Genetic Simulated Annealing Algorithm in
	Optical Layout of Rectangular Parts［J］. China Mechanical Engineering， 2013， 24（18）：2499-2504.
[11]	梁利东，钟相强. 粒子群算法在不规则件排样优化中的应用［J］. 中国机械工程， 2010， 21（17）：2050-2052.
	LIANG Lidong， ZHONG Xiangjiang. Applications of Particle Swarm Optimization for Solving Irregular Part Nesting Problems［J］. China Mechanical Engineering， 2010， 21（17）：2050-2052.
[12]	MIRJALILI S， MIRJALILI S M， LEWIS A D. Grey Wolf Optimizer［J］. Advances in Engineering Software， 2014， 69：46-61.
[13]	罗强. 基于灰狼算法的矩形优化排样及其在板式家具开料中的应用［D］. 武汉：华中科技大学， 2019.
	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.
[14]	全雪峰，沈继涛. 基于模拟退火剩余矩形算法的矩形件排样［J］. 软件， 2016， 37（3）：27-29.
	QUAN Xuefeng， SHEN Jitao. Optimum Packing of Rectangles Based on Simulated Annealing and Surplus Rectangle［J］. Software， 2016， 37（3）：27-29.
[15]	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.
[16]	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.
[17]	ZHANG T Y， SUEN C Y. A Fast Parallel Algorithm for Thinning Digital Patterns［J］. Communications of the ACM， 1984， 27（3）：236-239.