设计知识驱动的不规则多边形排样算法及应用

doi:10.13196/j.cims.2023.02.020

计算机集成制造系统 ›› 2023, Vol. 29 ›› Issue (2): 593-603.DOI: 10.13196/j.cims.2023.02.020

设计知识驱动的不规则多边形排样算法及应用

冯毅雄^1,2,钟锐锐^1,2,张志峰^1,2+,黄城^1,2,李中凯^1,3,胡炳涛^1,2,洪兆溪^1,2,谭建荣^1,2

1.浙江大学流体动力与机电系统国家重点实验室
2.浙江大学设计工程及数字孪生浙江省工程研究中心
3.中国矿业大学机电工程学院

出版日期:2023-02-28 发布日期:2023-03-04
基金资助:
浙江省重点研发计划资助项目(2023C01214);国家自然科学基金资助项目(52105281,52075479)。

Irregular polygons nesting algorithm driven by design knowledge and application

FENG Yixiong^1,2,ZHONG Ruirui^1,2,ZHANG Zhifeng^1,2+,HUANG Cheng^1,2,LI Zhongkai^1,3,HU Bingtao^1,2,HONG Zhaoxi^1,2,TAN Jianrong^1,2

1.State Key Laboratory of Fluid Power & Mechatronic Systems,Zhejiang University
2.Engineering Research Center for Design Engineering and Digital Twin of Zhejiang Province,Zhejiang University
3.School of Mechatronics Engineering,China University of Mining and Technology

Online:2023-02-28 Published:2023-03-04
Supported by:
Project supported by the Key Research and Development Program of Zhejiang Province,China (No.2023C01214),and the National Natural Science Foundation,China (No.52105281,52075479).

摘要/Abstract

摘要： 为高效解决实际生产制造中的二维不规则多边形排样问题,提出一种设计知识驱动的启发式算法。利用临界多边形判定多边形之间的相对位置,并建立局部适应度数学模型用于衡量多边形的贴合程度;根据设计知识建立数学模型来评价多边形待摆放位置,利用基于局部搜索的贪心算法完成排样。通过对国际通用基准用例进行实验测试并与现有智能优化算法进行对比,证明了所提算法在排样质量与时间性能上不但具有一定优势,而且稳定性高。通过实际生产中样片数据的实验测试证明了所提算法的实用性。

关键词: 不规则排样问题, 临界多边形, 知识驱动, 启发式算法

Abstract: To efficiently solve the problem of two-dimensional irregular polygon packing in actual production,a heuristic algorithm driven by design knowledge was proposed.No Fit Polygon (NFP) was used to judge the relative positions between irregular polygons,and a mathematical model of local fitness was established to measure the fitting degree of irregular polygons.Then,a mathematical model driven by design knowledge was established to evaluate the position of irregular polygons to be placed.A greedy algorithm based on local search strategy was used to complete the packing.The experimental testing of international common benchmark cases and comparison with existing intelligent optimization algorithms proved that the proposed algorithm had certain advantages in layout quality and time performance with high stability.Besides,the experimental test of the sample data in actual production proved that the proposed algorithm had the value of being applied to actual production applications.

Key words: irregular packing problem, no fit polygon, knowledge-driven, heuristic algorithms

中图分类号:

TP391

冯毅雄, 钟锐锐, 张志峰, 黄城, 李中凯, 胡炳涛, 洪兆溪, 谭建荣. 设计知识驱动的不规则多边形排样算法及应用[J]. 计算机集成制造系统, 2023, 29(2): 593-603.

FENG Yixiong, ZHONG Ruirui, ZHANG Zhifeng, HUANG Cheng, LI Zhongkai, HU Bingtao, HONG Zhaoxi, TAN Jianrong. Irregular polygons nesting algorithm driven by design knowledge and application[J]. Computer Integrated Manufacturing System, 2023, 29(2): 593-603.

[1]	李小林, 司佳佳, 尹传传, 李玉鹏. 考虑工件释放时间和柔性维护的单机调度问题[J]. 计算机集成制造系统, 2023, 29(2): 581-592.
[2]	郭羽含, 冯玥, 刘万军, 张宇. 有限产能和库存的生产批量与双模式维护联合优化[J]. 计算机集成制造系统, 2022, 28(9): 2894-2908.
[3]	李珍萍, 韩倩倩, 仪明超. 设置货箱缓存区的自动小车存储及取货系统订单分批拣选问题[J]. 计算机集成制造系统, 2022, 28(8): 2605-2618.
[4]	黄子钊, 庄子龙, 滕浩, 秦威, 秦涛, 邹鹰. 自动化码头出口箱箱位分配优化超启发式算法[J]. 计算机集成制造系统, 2022, 28(8): 2619-2632.
[5]	崔建双, 吕玥, 徐子涵. 基于Q—学习的超启发式模型及算法求解多模式资源约束项目调度问题[J]. 计算机集成制造系统, 2022, 28(5): 1472-1481.
[6]	汪逸晖,高亮. 乌鸦搜索算法的改进及其在工程约束优化问题中的应用[J]. 计算机集成制造系统, 2021, 27(7): 1871-1883.
[7]	高勃,张红艳,朱明皓. 面向智能制造的不规则零件排样优化算法[J]. 计算机集成制造系统, 2021, 27(6): 1673-1680.
[8]	顾文斌,李育鑫,钱煜晖,肖紫涵,秦展鹏. 基于激素调节机制IPSO算法的相同并行机混合流水车间调度问题[J]. 计算机集成制造系统, 2021, 27(10): 2858-2871.
[9]	冷龙龙,赵燕伟,蒋海青,张春苗,王舜. 求解物流配送同时取送货低碳选址—路径问题的量子超启发式算法[J]. 计算机集成制造系统, 2020, 26(第3): 815-828.
[10]	曹浩,莫蓉,万能. 面向支撑力分布的桁架结构设计方法[J]. 计算机集成制造系统, 2020, 26(7): 1763-1770.
[11]	林煊,陈庆新,毛宁. 板式家具高速自动分拣系统出库及打包调度策略[J]. 计算机集成制造系统, 2020, 26(7): 1843-1854.
[12]	张景玲,刘金龙,赵燕伟,王宏伟,冷龙龙,冯勤炳. 时间依赖型同时取送货VRP及超启发式算法[J]. 计算机集成制造系统, 2020, 26(7): 1905-1917.
[13]	冷龙龙,赵燕伟,张春苗. 基于共享机制的自适应超启发式算法求解区域化低碳选址—路径问题[J]. 计算机集成制造系统, 2020, 26(5期): 1407-1424.
[14]	王亚娜,江文辉,王桐远,李延来. 垂直差异产品的产品组合、价格与库存联合决策[J]. 计算机集成制造系统, 2020, 26(11): 3129-3141.
[15]	吴秀丽,张志强,赵宁,李俊青. 超启发式文化基因算法优化生产与预维修集成调度问题[J]. 计算机集成制造系统, 2019, 25(第8): 1885-1896.

设计知识驱动的不规则多边形排样算法及应用

Irregular polygons nesting algorithm driven by design knowledge and application

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics