An Optimization Nesting Method for Rectangular Parts Based on Elite Genetic Strategy and Dynamic Gap-filling Mechanism

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

Abstract

Abstract:

An optimized rectangular nesting method integrating an elitist genetic strategy with a dynamic gap-filling mechanism was proposed for the rectangular nesting problem involving multiple varieties and varying production scales. The classification rules for rectangular nesting priorities were established based on two performance parameters including dimensional tolerance $ε$ and aspect ratio $α$ . A decimal integer sequence was used to encode part information， and an elite initial population was generated according to the defined priorities. This elite genetic strategy accelerates the convergence of the algorithm toward better solutions. Using the lowest horizontal line in the nesting process as a reference， the matching degree between the current part and each available gap was computed based on the classification rules. By searching all available gaps， the optimal placement for the part was selected， thereby achieving dynamic gap-filling. Through various case studies， the sensitivity of variable $ε$ and variable $α$ to the material utilization rate was analyzed. Their optimal values were determined using the highest average material utilization as the criterion. Comparative experiments on large-， medium-， and small-scale nesting instances， along with two real-world production instances introduced from domestic manufacturing enterprises， were conducted using the proposed method， methods reported in the literature， and a commercial software. The proposed method demonstrates significant advantages in material utilization and algorithm stability， verifying its feasibility and effectiveness.

Key words: rectangular nesting, elite genetic strategy, decimal encoding, rectangular part classification, dynamic gap-filling

摘要：

针对多品种、不同规模的矩形件排样问题，提出了一种精英型遗传策略和空隙动态填充机制相融合的矩形件优化排样方法。根据矩形件容差 $ε$ 和长宽比 $α$ 两个性能参数制定矩形件排样优先级的分类规则，并采用十进制整数序列编码矩形件信息，按矩形件排样优先级生成一种精英型初始种群，通过精英型遗传策略实现算法朝着更优解的方向加速收敛。以排样过程中最低水平线为基准，结合矩形件分类规则，计算当前待排矩形件与每个空隙间的匹配度，通过搜索排样空隙找出矩形件最佳填充位置，实现空隙动态填充。通过多种算例分析 $ε$ 和 $α$ 对材料利用率的敏感性，以最高平均材料利用率为评价指标确定 $ε$ 和 $α$ 的最优值；针对大中小规模的矩形件排样算例和国内制造企业的两个真实生产案例，利用所提出方法、文献中方法和商用软件求解，对比分析其排样结果。结果表明，所提出方法在材料利用率和算法稳定性上表现出显著优势，验证了该方法的可行性和有效性。

关键词: 矩形件排样, 精英型遗传策略, 十进制编码, 矩形件分类, 空隙动态填充

CLC Number:

TH16

WU Dianjian, HUANG Shuaikang, DING Zican, ZHANG Sanqiang, CAO Weidong. An Optimization Nesting Method for Rectangular Parts Based on Elite Genetic Strategy and Dynamic Gap-filling Mechanism[J]. China Mechanical Engineering, 2026, 37(10): 2418-2427.

吴电建, 黄帅康, 丁子璨, 张三强, 曹卫东. 基于精英型遗传策略和空隙动态填充机制的矩形件优化排样方法[J]. 中国机械工程, 2026, 37(10): 2418-2427.

Figures/Tables 21

References 18

[1]	吴电建，张三强，杨光友. 复杂下料工艺约束下的二维不规则零件优化排样方法［J］. 中国机械工程， 2023， 34（21）： 2615-2621.
	WU Dianjian， ZHANG Sanqiang， YANG Guangyou. Optimal Layout Method of 2D Irregular Parts under Complex Cutting Process Constraints［J］. China Mechanical Engineering， 2023， 34（21）： 2615-2621.
[2]	韩伟，张子成. 基于模拟退火的贯通约束不规则排样［J］. 中国机械工程， 2016， 27（24）： 3326-3331.
	HAN Wei， ZHANG Zicheng. A Simulated Annealing Algorithm for Irregular Guillotine Packing Problems［J］. China Mechanical Engineering， 2016， 27（24）： 3326-3331.
[3]	王淑青，陈军，潘健，等. 基于最小包络矩形的不规则凸多边形的三角形处理算法［J］. 计算机应用与软件， 2016， 33（11）： 197-199.
	WANG Shuqing， CHEN Jun， PAN Jian， et al. A Triangle Processing Algorithm for Irregular Convex Polygon Based on Smallest Envelope Rectangle［J］. Computer Applications and Software， 2016， 33（11）： 197-199.
[4]	汤德佑，周子琳. 基于临界多边形的不规则件启发式排样算法［J］. 计算机应用， 2016， 36（9）： 2540-2544.
	TANG Deyou， ZHOU Zilin. No-fit-polygon-based Heuristic Nesting Algorithm for Irregular Shapes［J］. Journal of Computer Applications， 2016， 36（9）： 2540-2544.
[5]	罗立宏，冯开平，叶家玮. 基于图像的2维板件排样方案评价方法研究［J］. 四川大学学报（工程科学版）， 2013， 45（6）： 162-169.
	LUO Lihong， FENG Kaiping， YE Jiawei. Research of Layout Estimating Method of 2-D Parts Packing Based on Image［J］. Journal of Sichuan University （Engineering Science Edition）， 2013， 45（6）： 162-169.
[6]	VERSTICHEL J， de CAUSMAECKER P， VANDEN BERGHE G. An Improved Best-fit Heuristic for the Orthogonal Strip Packing Problem［J］. International Transactions in Operational Research， 2013， 20（5）： 711-730.
[7]	董德威，颜云辉，张尧，等. 矩形件优化排样的自适应遗传模拟退火算法［J］. 中国机械工程， 2013， 24（18）： 2499-2504.
	DONG Dewei， YAN Yunhui， ZHANG Yao， et al. Adaptive Genetic Simulated Annealing Algorithm in Optimal Layout of Rectangular Parts［J］. China Mechanical Engineering， 2013， 24（18）： 2499-2504.
[8]	罗强，李世红，袁跃兰，等. 基于复合评价因子的改进遗传算法求解矩形件排样问题［J］. 锻压技术， 2018， 43（2）： 172-181.
	LUO Qiang， LI Shihong， YUAN Yuelan， et al. Rectangular Workpiece Nesting Based on an Improved Genetic Algorithm of Composite Evaluation Factor［J］. Forging & Stamping Technology， 2018， 43（2）： 172-181.
[9]	张新华. 基于强化学习和蚁群算法的协同依赖多任务网格集群调度［J］. 长沙大学学报， 2016， 30（2）： 50-53.
	ZHANG Xinhua. Grid Cluster Cooperative Dependent Multi Task Scheduling Method Based on Reinforcement Learning and Ant Colony Algorithm［J］. Journal of Changsha University， 2016， 30（2）： 50-53.
[10]	LEUNG S C H， ZHANG D， SIM K M. A Two-stage Intelligent Search Algorithm for the Two-dimensional Strip Packing Problem［J］. European Journal of Operational Research， 2011， 215（1）： 57-69.
[11]	HOPPER E. Two-dimensional Packing Utilising Evolutionary Algorithms and Other Meta-heuristic Methods［D］. Cardiff： Cardiff University， 2000.
[12]	周梓博.大规模不规则矩形件的下料系统设计与实现［D］. 成都：电子科技大学，2024.
	ZHOU Zibo. Design and Implementation of Cutting System for Large-scale Irregular Rectangular Parts［D］. Chengdu：University of Electronic Science and Technology of China， 2024.
[13]	HOPPER E， TURTON B C H. An Empirical Investigation of Meta-heuristic and Heuristic Algorithms for a 2D Packing Problem［J］. European Journal of Operational Research， 2001， 128（1）： 34-57.
[14]	刘志雄. 求解矩形条带装箱问题的改进剩余矩形法［J］. 计算机集成制造系统， 2025， 31（7）： 2605-2617.
	LIU Zhixiong. Improved Surplus Rectangle Algorithm for Rectangle Strip Packing Problem［J］. Computer Integrated Manufacturing Systems， 2025， 31（7）： 2605-2617.
[15]	梁利东，钟相强. 粒子群算法在不规则件排样优化中的应用［J］. 中国机械工程， 2010， 21（17）： 2050-2052.
	LIANG Lidong， ZHONG Xiangqiang. Applications of Particle Swarm Optimization for Solving Irregular Part Nesting Problems［J］. China Mechanical Engineering， 2010， 21（17）： 2050-2052.
[16]	吴正佳，李金雄，单飞祥，等. 灰狼算法在定制化家具矩形件排样中的应用［J］. 机电信息， 2023（4）： 85-88.
	WU Zhengjia， LI Jinxiong， SHAN Feixiang， et al. Application of Grey Wolf Algorithm in Layout of Customized Furniture Rectangular Parts［J］. Mechanical and Electrical Information， 2023（4）： 85-88.
[17]	ProgramsOptimal. Cutting Optimization Pro ［CP/OL］. （2024）［2025-11-22］. .
[18]	张国梁，蔡小娜，侯晓鹏，等. 面向零件的人造板材矩形件锯切排样数学建模及遗传算法求解［J］. 林业科学， 2016， 52（5）： 150-159.
	ZHANG Guoliang， CAI Xiaona， HOU Xiaopeng， et al. Part-oriented Cutting Layout Mathematical Modeling and Solving by Genetic Algorithm for Rectangular Wood Based Panel Parts［J］. Scientia Silvae Sinicae， 2016， 52（5）： 150-159.

编号	n	W	H最优	相对误差δ/%
编号	n	W	H最优	SR-DM	PSO-BL	GWO-BL	Cut-OP	EGGF
N1	10	40	40	15.00	10.00	10.00	0	0
N2	20	30	50	24.00	12.00	6.00	4.00	2.00
N3	30	30	50	24.00	10.00	8.00	4.00	2.00
N4	40	80	80	15.00	11.25	6.25	5.00	3.75
C1P1	16	20	20	25.00	10.00	15.00	0	0
C1P2	17	20	20	30.00	20.00	15.00	10.00	5.00
C1P3	16	20	20	15.00	25.00	15.00	10.00	5.00
C2P1	25	40	15	20.00	20.00	20.00	6.67	6.67
C2P2	25	40	15	20.00	20.00	13.33	6.67	6.67
C2P3	25	40	15	0	26.67	20.00	13.33	6.67
t4a	49	200	200	54.00	6.50	11.50	3.50	4.00
t4b	49	200	200	24.50	7.00	10.00	3.00	4.00
t4c	49	200	200	70.00	11.50	10.50	3.00	3.50
t4d	49	200	200	65.50	6.50	12.50	1.50	3.50
t4e	49	200	200	34.50	9.00	11.50	3.00	5.00
小规模算例平均相对误差				29.10	13.69	12.31	4.91	3.85

编号	n	W	H最优	相对误差δ/%
编号	n	W	H最优	SR-DM	PSO-BL	GWO-BL	Cut-OP	EGGF
N1	10	40	40	15.00	10.00	10.00	0	0
N2	20	30	50	24.00	12.00	6.00	4.00	2.00
N3	30	30	50	24.00	10.00	8.00	4.00	2.00
N4	40	80	80	15.00	11.25	6.25	5.00	3.75
C1P1	16	20	20	25.00	10.00	15.00	0	0
C1P2	17	20	20	30.00	20.00	15.00	10.00	5.00
C1P3	16	20	20	15.00	25.00	15.00	10.00	5.00
C2P1	25	40	15	20.00	20.00	20.00	6.67	6.67
C2P2	25	40	15	20.00	20.00	13.33	6.67	6.67
C2P3	25	40	15	0	26.67	20.00	13.33	6.67
t4a	49	200	200	54.00	6.50	11.50	3.50	4.00
t4b	49	200	200	24.50	7.00	10.00	3.00	4.00
t4c	49	200	200	70.00	11.50	10.50	3.00	3.50
t4d	49	200	200	65.50	6.50	12.50	1.50	3.50
t4e	49	200	200	34.50	9.00	11.50	3.00	5.00
小规模算例平均相对误差				29.10	13.69	12.31	4.91	3.85

编号	n	W	H最优	相对误差δ/%
编号	n	W	H最优	SR-DM	PSO-BL	GWO-BL	Cut-OP	EGGF
N5	50	100	100	12.00	21.00	4.00	4.00	3.00
N6	60	50	100	21.00	12.00	7.00	3.00	2.00
N7	70	80	100	34.00	14.00	7.00	4.00	4.00
N8	80	100	80	10.00	8.75	10.00	2.50	2.50
C5P1	73	60	90	5.56	8.89	6.67	4.44	2.22
C5P2	73	60	90	7.78	14.44	8.89	4.44	3.33
C5P3	73	60	90	7.78	13.33	11.11	5.56	2.22
C6P1	97	80	120	10.00	7.50	10.00	2.50	2.50
C6P2	97	80	120	10.83	11.67	8.33	1.67	4.17
C6P3	97	80	120	11.67	8.33	6.67	3.33	2.50
t5a	73	200	200	73.00	8.00	7.50	3.00	4.50
t5b	73	200	200	80.00	7.00	7.50	2.00	4.50
t5c	73	200	200	40.50	8.00	9.00	2.00	4.50
t5d	73	200	200	46.50	10.00	8.00	2.50	5.00
t5e	73	200	200	97.00	7.50	11.50	3.00	3.00
中规模算例平均相对误差				31.17	10.69	8.21	3.20	3.33

编号	n	W	H最优	相对误差δ/%
编号	n	W	H最优	SR-DM	PSO-BL	GWO-BL	Cut-OP	EGGF
N5	50	100	100	12.00	21.00	4.00	4.00	3.00
N6	60	50	100	21.00	12.00	7.00	3.00	2.00
N7	70	80	100	34.00	14.00	7.00	4.00	4.00
N8	80	100	80	10.00	8.75	10.00	2.50	2.50
C5P1	73	60	90	5.56	8.89	6.67	4.44	2.22
C5P2	73	60	90	7.78	14.44	8.89	4.44	3.33
C5P3	73	60	90	7.78	13.33	11.11	5.56	2.22
C6P1	97	80	120	10.00	7.50	10.00	2.50	2.50
C6P2	97	80	120	10.83	11.67	8.33	1.67	4.17
C6P3	97	80	120	11.67	8.33	6.67	3.33	2.50
t5a	73	200	200	73.00	8.00	7.50	3.00	4.50
t5b	73	200	200	80.00	7.00	7.50	2.00	4.50
t5c	73	200	200	40.50	8.00	9.00	2.00	4.50
t5d	73	200	200	46.50	10.00	8.00	2.50	5.00
t5e	73	200	200	97.00	7.50	11.50	3.00	3.00
中规模算例平均相对误差				31.17	10.69	8.21	3.20	3.33

编号	n	W	H最优	相对误差δ/%
编号	n	W	H最优	SR-DM	PSO-BL	GWO-BL	Cut-OP	EGGF
N9	100	50	150	18.00	9.33	6.67	2.00	0.67
N10	200	70	150	8.00	8.00	5.33	2.00	0.67
C7P1	196	160	240	5.83	10.00	5.00	1.67	2.08
C7P2	197	160	240	10.00	8.33	5.83	2.50	1.67
C7P3	196	160	240	8.33	6.25	3.33	1.67	1.67
t7a	197	200	200	63.00	11.50	4.00	1.50	2.00
t7b	199	200	200	48.50	10.50	4.00	2.00	2.50
t7c	199	200	200	47.50	9.00	6.00	3.00	3.00
t7d	199	200	200	32.50	7.50	7.00	2.00	1.50
t7e	199	200	200	79.00	4.50	5.50	2.50	2.50
大规模算例平均相对误差				32.07	8.49	5.27	2.08	1.83