锻压技术

基于改进遗传禁忌搜索算法的二维不规则件排样优化

英文标题：Layout optimization on two-dimensional irregular parts based on improved genetic tabu search algorithm

分类号：TP391

出版年,卷(期):页码：2024,49(4):54-61

摘要：

针对二维不规则钣金件排样问题，提出一种融合临界多边形（NFP）定位和改进遗传禁忌搜索算法的排样优化方法。首先，根据零件的几何特征对其进行分类编码，求解零件类间的NFP，避免NFP的重复计算，同时引入以排样高度最小化为目标的启发式规则，给出零件定位策略的综合评价函数，以提高板材利用率。其次，在零件排序优化时，将遗传算法中的精英群体作为禁忌搜索算法的高质量初始解，减少计算资源消耗。最后，利用欧洲切割和包装特别兴趣小组ESICUP提供的标准算例对所提排样方法进行测试。结果表明：相比传统遗传禁忌搜索算法，所提排样方法的计算效率提升了28.32%～80.23%，并且在与两种现有算法的7个基准测试对比中，所提排样方法均取得了最优排样结果。

Aiming at the layout problem of two-dimensional irregular sheet metal parts, an layout optimization method integrating no-fit polygon (NFP) localization and improved genetic tabu search algorithm was proposed. Firstly, the parts were classified and coded according to the geometric characteristics, and the NFP between parts was solved to avoid the repeated calculation of NFP. At the same time, the heuristic rule with the goal of layout height minimization was introduced, and the comprehensive evaluation function of the localization strategy for parts was given to improve the utilization rate of sheet material. Secondly, the elite population in the genetic algorithm was used as the high-quality initial solution of the tabu search algorithm to reduce the consumption of calculational resources in the nesting optimization of parts. Finally, the proposed layout method was tested using benchmark examples provided by the European special interest group on cutting and packing(ESICUP). The results show that compared with the traditional genetic tabu search algorithm, the calculational efficiency of the proposed layout method is improved by 28.32%-80.23%, and the best layout results are achieved by the proposed layout method during the seven benchmark tests compared with the two existing algorithms.

基金项目：

国家自然科学基金资助项目（51975097）

作者简介：梁金龙（1995-），男，硕士研究生 E-mail：liangjinlong523@163.com 通信作者：徐金亭（1980-），男，博士，教授，博士生导师 E-mail：xujt@dlut.edu.cn

参考文献：

[1]Art R C. An Approach to the Twodimensional Irregular Cutting Stock Problem[D]. Cambridge: Massachusetts Institute of Technology, 1966.

[2]Adamowicz M, Albano A. Nesting two dimensional shapes in rectangular modules[J]. Computer Aided Design, 1976, 8(1):27-33.

[3]刘胡瑶. 基于临界多边形的二维排样算法研究[D]. 上海：上海交通大学，2007.

Liu H Y. Research of Two Dimensional Nesting Algorithm Based on No Fit Polygon[D]. Shanghai: Shanghai Jiao Tong University, 2007.

[4]刘虓，叶家玮，刘嘉敏. 基于混合表达图形的二维不规则排样构造算法[J].上海交通大学学报,2018,52(7):825-830.

Liu X, Ye J W, Liu J M. Twodimensional constructive packing algorithm based on hybrid representation graphics[J]. Journal of Shanghai Jiaotong University, 2018, 52(7):825-830.

[5]冯毅雄，钟锐锐，张志峰，等. 设计知识驱动的不规则多边形排样算法及应用[J].计算机集成制造系统,2023,29(2):593-603.

Feng Y X, Zhong R R, Zhang Z F, et al. Irregular polygons nesting algorithm driven by design knowledge and application[J]. Computer Integrated Manufacturing Systems, 2023, 29(2):593-603.

[6]Oliveira J F, Gomes A M, Ferreira J S. TOPOSA new constructive algorithm for nesting problems[J]. ORSpectrum, 2000, 22(2):263-284.

[7]LópezCamacho E, Ochoa G, TerashimaMarín H, et al. An effective heuristic for the twodimensional irregular bin packing problem[J]. Annals of Operations Research, 2013, 206(1):241-264.

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

Dong D W, Yan Y H, Zhang Y, et al. Adaptive genetic simulated annealing algorithm in optimal layout of rectangular parts[J]. China Mechanical Engineering,2013,24(18):2499-2504.

[9]高勃，张红艳，朱明皓. 面向智能制造的不规则零件排样优化算法[J].计算机集成制造系统,2021,27(6):1673-1680.

Gao B, Zhang H Y, Zhu M H. Optimization algorithm of irregular parts layout for intelligent manufacturing[J]. Computer Integrated Manufacturing Systems, 2021, 27(6):1673-1680.

[10]Rao Y Q, Wang P, Luo Q. Hybridizing beam search with tabu search for the irregular packing problem[J]. Mathematical Problems in Engineering, 2021, (2021):1-14.

[11]杜冰，郭晓强，方杰，等. 二维不规则图形排样问题的一种混合求解算法[J].锻压技术,2022,47(3)：39-45.

Du B, Guo X Q, Fang J, et al. A hybrid solving algorithm on twodimensional irregular graphics nesting problem[J]. Forging & Stamping Technology, 2022, 47(3):39-45.

[12]闫嘉，李林峰，林毓培，等. 基于改进免疫遗传算法的汽车零件排样[J].西南大学学报:自然科学版,2023,45(5):204-214.

Yan J, Li L F, Lin Y P, et al. Automobile parts packing based on improved immunogenetics algorithm[J]. Journal of Southwest University: Natural Science Edition, 2023,45(5):204-214.

[13]饶运清，彭灯，杜冰，等.超边界约束条件下异形件排样问题的求解算法研究[J].计算机集成制造系统,2023,29(12):4063-4072.

Rao Y Q, Peng D, Du B, et al. Research on the algorithm for solving the irregular parts packing problem with beyond boundary constraint[J]. Computer Integrated Manufacturing Systems, 2023,29(12):4063-4072.

[14]汤德佑，周子琳. 基于临界多边形的不规则件启发式排样算法[J].计算机应用,2016,36(9):2540-2544.

Tang D Y, Zhou Z L. Nofitpolygonbased heuristic nesting algorithm for irregular shapes[J]. Journal of Computer Applications, 2016, 36(9):2540-2544.

[15]ESICUP. EURO Special Interest Group on Cutting and Packing[EB/OL]. https://www.euroonline.org/websites/esicup, 2023-04-19.

[16]Holland J H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence[M]. Ann Arbor: Control & Artificial Intelligence University of Michigan Press, 1975.

[17]Glover F. Future paths for integer programming and links to artificial intelligence[J]. Computers & Operations Research, 1986, 13(5):533-549.

[18]周子琳. 基于临界多边形的不规则件排样算法研究及实现[D]. 广州：华南理工大学，2014.

Zhou Z L. Research and Implementation of Nofitpolygonbased Irregular Nesting Algorithm[D]. Guangzhou: South China University of Technology, 2014.

[19]王静静，瞿少成，李科林. 一种基于并行交叉遗传算法的二维不规则排样问题求解[J].计算机应用与软件,2020,37(7):188-193.

Wang J J, Qu S C, Li K L. A towdimensional irregular layout problem solving based on parallel cross genetic algorithm[J]. Computer Applications and Software, 2020, 37(7):188-193.

服务与反馈：

【文章下载】【加入收藏】