多约束下矩形件排样问题的混合求解算法研究

doi:10.16182/j.issn1004731x.joss.22-1258

系统仿真学报 ›› 2024, Vol. 36 ›› Issue (3): 743-755.doi: 10.16182/j.issn1004731x.joss.22-1258

多约束下矩形件排样问题的混合求解算法研究

刘野¹(), 吉卫喜¹^,²(), 苏璇¹, 赵宏轩¹

^1.江南大学机械工程学院，江苏无锡 214122
^2.江苏省食品制造装备重点实验室，江苏无锡 214122

收稿日期:2022-10-20 修回日期:2022-12-16 出版日期:2024-03-15 发布日期:2024-03-14
通讯作者: 吉卫喜 E-mail:13151006307@163.com;ji_weixi@126.com
第一作者简介:刘野(1996-)，男，满族，硕士生，研究方向为智能制造，排样技术。E-mail：13151006307@163.com
基金资助:
山东省重大科技创新工程基金(2019JZZY020111)

Research on Hybrid Solution Algorithm for Layout Problem of Rectangular Parts with Multiple Constraints

Liu Ye¹(), Ji Weixi¹^,²(), Su Xuan¹, Zhao Hongxuan¹

^1.School of Mechanical Engineering, Jiangnan University, Wuxi 214122, China
^2.Jiangsu Provincial Key Laboratory of Food Manufacturing Equipment, Wuxi 214122, China

Received:2022-10-20 Revised:2022-12-16 Online:2024-03-15 Published:2024-03-14
Contact: Ji Weixi E-mail:13151006307@163.com;ji_weixi@126.com

摘要/Abstract

摘要：

针对板材和玻璃下料过程中存在的矩形件排样问题，提出了一种基于分割匹配算法与改进蚁群算法的混合算法进行求解。建立了以最大化均方利用率和剩余加工时间为目标的排样优化模型；利用蚁群算法作为排样顺序算法确定部分零件的排样顺序以满足零件的加工时间限制，为了提高蚁群算法搜索效率，提出了自适应信息素更新策略，引入基于遗传变异和2-opt变异的混合变异策略来增强局部搜索能力。针对于零件在毛坯上位置的排布问题，为提高毛坯的均方利用率同时又满足一刀切约束条件，提出分割匹配算法进行矩形件排布优化。将改后的算法与其他优化算法用国际标准测试案例和企业实际案例进行对比分析，验证了所提混合算法的有效性。

关键词: 矩形件排样, 蚁群算法, 一刀切, 多约束, 混合变异策略

Abstract:

A hybrid algorithm based on a cutting and matching algorithm and an improved ant colony algorithm was proposed to solve the layout problem of rectangular parts in the process of wood and glass blanking. A layout optimization model was established to maximize the mean square utilization and the remaining processing time; the ant colony algorithm was used as the layout sequence algorithm to determine the layout sequence of some parts and meet the processing time constraint. In order to improve the search efficiency of the ant colony algorithm, an adaptive pheromone updating strategy was proposed, and a hybrid mutation strategy based on genetic mutation and 2-opt mutation was introduced to enhance the local search capability. For the arrangement of parts on the workblank, in order to improve the mean square utilization of the workblank and meet the guillotine constraint, a cutting and matching algorithm was proposed to optimize the layout of rectangular parts. Finally, the improved algorithm was compared with other optimization algorithms by international standard test cases and actual enterprise cases, and the effectiveness of the proposed hybrid algorithm was verified.

Key words: layout of rectangular parts, ant colony algorithm, guillotine, multiple constraints, hybrid mutation strategy

中图分类号:

TP391.9

刘野,吉卫喜,苏璇等 . 多约束下矩形件排样问题的混合求解算法研究[J]. 系统仿真学报, 2024, 36(3): 743-755.

Liu Ye,Ji Weixi,Su Xuan,et al . Research on Hybrid Solution Algorithm for Layout Problem of Rectangular Parts with Multiple Constraints[J]. Journal of System Simulation, 2024, 36(3): 743-755.

图/表 15

图1

图2

图3

图4

图5

图6

图7

图8

图9

表1

图10

表2

表3

表4

表5

参考文献 17

1	Ortmann Frank G, Ntene Nthabiseng, H van Vuuren Jan. New and Improved Level Heuristics for the Rectangular Strip Packing and Variable-sized Bin Packing Problems[J]. European Journal of Operational Research, 2010, 203(2): 306-315.
2	张怀宇, 杨根科, 白杰. 二维Strip Packing问题的嵌套启发式算法[J]. 系统仿真学报, 2012, 24(8): 1601-1605, 1623.
	Zhang Huaiyu, Yang Genke, Bai Jie. Nested Heuristic Algorithm for Two-dimensional Strip Packing Problem[J]. Journal of System Simulation, 2012, 24(8): 1601-1605, 1623.
3	张子成. 基于矩形拼接的"一刀切"矩形排样优化设计[J]. 现代制造工程, 2018(4): 103-107, 157.
	Zhang Zicheng. Optimal Design of Rectangular Layout Based on Rectangular Mosaic with Guillotine Constraints[J]. Modern Manufacturing Engineering, 2018(4): 103-107, 157.
4	刘诚, 孙远升, 花军, 等. 基于遗传-贪心混合搜索的人造板下料算法[J]. 林业工程学报, 2021, 6(4): 127-133.
	Liu Cheng, Sun Yuansheng, Hua Jun, et al. Cutting of Wood-based Panel Based on Genetic Greedy Hybrid Search[J]. Journal of Forestry Engineering, 2021, 6(4): 127-133.
5	Liu Ya, Chu Chengbin, Wang Kanliang. A Dynamic Programming-based Heuristic for the Variable Sized Two-dimensional Bin Packing Problem[J]. International Journal of Production Research, 2011, 49(13): 3815-3831.
6	Hong Shaohui, Zhang Defu, Lau H C, et al. A Hybrid Heuristic Algorithm for the 2D Variable-sized Bin Packing Problem[J]. European Journal of Operational Research, 2014, 238(1): 95-103.
7	Wei Lijun, Wee Chong Oon, Zhu Wenbin, et al. A Goal-driven Approach to the 2D Bin Packing and Variable-sized Bin Packing Problems[J]. European Journal of Operational Research, 2013, 224(1): 110-121.
8	Martin Mateus, Morabito Reinaldo, Munari Pedro. A Bottom-up Packing Approach for Modeling the Constrained Two-dimensional Guillotine Placement Problem[J]. Computers & Operations Research, 2020, 115: 104851.
9	Gardeyn Jeroen, Wauters Tony. A Goal-driven Ruin and Recreate Heuristic for the 2D Variable-sized Bin Packing Problem with Guillotine Constraints[J]. European Journal of Operational Research, 2022, 301(2): 432-444.
10	Bennell J A, Lai Soon Lee, Potts C N. A Genetic Algorithm for Two-dimensional Bin Packing with Due Dates[J]. International Journal of Production Economics, 2013, 145(2): 547-560.
11	Arbib Claudio, Marinelli Fabrizio, Pizzuti Andrea. Number of bins and Maximum Lateness Minimization in Two-dimensional Bin Packing[J]. European Journal of Operational Research, 2021, 291(1): 101-113.
12	Liu Qiang, Cheng Huibing, Tian Tian, et al. Algorithms for the Variable-sized Bin Packing Problem with Time Windows[J]. Computers & Industrial Engineering, 2021, 155: 107175.
13	Stodola Petr, Michenka Karel, Nohel Jan, et al. Hybrid Algorithm Based on Ant Colony Optimization and Simulated Annealing Applied to the Dynamic Traveling Salesman Problem[J]. Entropy, 2020, 22(8): 884.
14	Stodola Petr, Otřísal Pavel, Hasilová Kamila. Adaptive Ant Colony Optimization with Node Clustering Applied to the Travelling Salesman Problem[J]. Swarm and Evolutionary Computation, 2022, 70: 101056.
15	胡蓉, 陈文博, 钱斌, 等. 学习型蚁群算法求解绿色多车场车辆路径问题[J]. 系统仿真学报, 2021, 33(9): 2095-2108.
	Hu Rong, Chen Wenbo, Qian Bin, et al. Learning Ant Colony Algorithm for Green Multi-depot Vehicle Routing Problem[J]. Journal of System Simulation, 2021, 33(9): 2095-2108.
16	Yan Yuzhe, Sohn H S, Reyes G. A Modified Ant System to Achieve Better Balance Between Intensification and Diversification for the Traveling Salesman Problem[J]. Applied Soft Computing, 2017, 60: 256-267.
17	Ebadinezhad Sahar. DEACO: Adopting Dynamic Evaporation Strategy to Enhance ACO Algorithm for the Traveling Salesman Problem[J]. Engineering Applications of Artificial Intelligence, 2020, 92: 103649.

规模	毛坯使用种类数	毛坯使用个数	利用率≥90%	利用率≥95%
小	6	7	6	6
中	6	27	23	20
大	6	68	61	59

数据集	IACA-CM	GDRR	BFS	HHA
平均值	95.83	95.76	87.43	94.33
M1	95.3	96.8	91.2	96.8
M2	95.5	94.4	81.0	91.4
M3	96.7	96.1	90.1	94.8

数据集	IACA-CM	GDRR	BFS	HHA
平均值	85.18	83.03	68.18	76.89
Ⅰ	92.8	88.5	78.5	83.7
Ⅱ	93.8	93.1	73.2	92.7
Ⅲ	86.8	84.5	70.2	75.0
Ⅳ	88.2	87.4	70.0	84.0
Ⅴ	83.0	81.7	66.2	71.6
Ⅵ	85.2	86.3	64.2	82.5
Ⅶ	84.8	81.2	65.5	73.4
Ⅷ	83.7	80.3	67.0	73.8
Ⅸ	66.1	60.8	54.2	55.7
Ⅹ	87.4	86.5	75.8	81.5

数据集	IACA-CM	GDRR	BFS	HHA
平均值	91.00	90.90	70.30	86.86
Nice25i	89.4	99.6	55.6	90.0
Nice50i	90.7	87.5	60.5	79.6
Nice100i	88.9	84.2	64.3	77.9
Nice200i	85.0	85.7	72.4	83.2
Nice300i	89.3	87.0	75.3	84.5
Nice400i	89.0	88.9	73.4	86.4
Nice500i	89.7	87.5	76.9	86.6
Path25i	92.9	100	62.2	94.5
Path50i	92.3	96.2	67.1	90.0
Path100i	93.3	91.2	69.7	87.4
Path200i	92.1	89.3	76.5	87.1
Path300i	94.7	91.3	76.3	90.5
Path400i	93.2	90.9	78.4	89.9
Path500i	93.5	93.3	75.6	88.4

数据集	IACA-CM	GDRR	BFS	HHA
KBH-L1	95.3	90.6	76.3	86.0
KBH-L2	90.7	89.5	69.5	77.2
KBH-L3	93.4	90.4	76.8	87.5
KBH-L4	91.8	88.2	70.0	83.1
KBH-L5	94.1	91.0	79.1	86.3
KBH-L6	93.0	86.9	71.7	79.7
KBH-L7	93.2	90.5	78.9	89.6
KBH-L8	95.7	92.0	77.5	89.7
KBH-L9	94.5	88.2	68.6	87.3
KBH-L10	96.5	91.8	72.5	90.2

多约束下矩形件排样问题的混合求解算法研究

Research on Hybrid Solution Algorithm for Layout Problem of Rectangular Parts with Multiple Constraints

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 15

参考文献 17

相关文章 15

编辑推荐

Metrics

本文评价

[1]	鲍惠芳, 方杰, 张进思, 王传胜. 基于改进蚁群算法的低碳冷链配送路径优化[J]. 系统仿真学报, 2024, 36(1): 183-194.
[2]	冯晨, 游晓明, 刘升. 结合竞争交互策略和淘汰重组机制的异构多蚁群算法[J]. 系统仿真学报, 2024, 36(1): 232-248.
[3]	张立, 贺明玲, 尹秋霜, 李宁, 余乐安. 不确定条件下多周期应急物资配送优化研究[J]. 系统仿真学报, 2023, 35(8): 1669-1680.
[4]	马悦, 吴琳, 郭圣明. 作战任务分配建模及求解方法研究[J]. 系统仿真学报, 2023, 35(4): 887-898.
[5]	梁江涛, 王慧琴. 基于改进蚁群算法的建筑火灾疏散路径规划研究[J]. 系统仿真学报, 2022, 34(5): 1044-1053.
[6]	邓向阳, 张立民, 方伟, 汤淼. 基于双向汇聚引导蚁群算法的机器人路径规划[J]. 系统仿真学报, 2022, 34(5): 1101-1108.
[7]	宁涛, 苟涛, 刘向东. 考虑低碳约束的生鲜农产品冷链物流策略仿真研究[J]. 系统仿真学报, 2022, 34(4): 797-805.
[8]	胡蓉, 陈文博, 钱斌, 郭宁, 向凤红. 学习型蚁群算法求解绿色多车场车辆路径问题[J]. 系统仿真学报, 2021, 33(9): 2095-2108.
[9]	王青云, 焦德忠, 史铄, 彭根燕, 孙俊华, 段雨昕. 改进的蚁群干扰资源分配方法[J]. 系统仿真学报, 2021, 33(12): 2967-2974.
[10]	尤波, 王明睿, 李智, 丁亮. 基于模型预测控制的轮式移动机器人轨迹规划[J]. 系统仿真学报, 2020, 32(4): 591-600.
[11]	杨卫, 曾亮, 康新晨. 基于蚁群算法的群机器人自组织聚集行为建模[J]. 系统仿真学报, 2020, 32(2): 191-200.
[12]	史岩, 张立华, 董受全, 王珏. 基于ACO算法和Bezier曲线优化的巡航导弹航路规划[J]. 系统仿真学报, 2020, 32(1): 122-129.
[13]	徐小平, 朱秋秋, 王峰. 求解圆排列问题的粒子群蚁群优化算法[J]. 系统仿真学报, 2017, 29(2): 248-254.
[14]	范厚明, 郭振峰, 杨宇. 预约机制下送箱集卡多集装箱码头调度问题[J]. 系统仿真学报, 2017, 29(12): 3051-3060.
[15]	张召远, 戴宁, 刘浩, 李大伟. 基于距离变换的蚁群搜索骨架提取方法[J]. 系统仿真学报, 2017, 29(11): 2918-2926.