Transactions of Materials and Heat Treatment

Title：Layout optimization on two-dimensional irregular parts based on improved genetic tabu search algorithm

Authors： Liang Jinlong1 Mao Wenzhi1 Luan Xianye2 Xu Jinting1

Unit： 1.School of Automotive Engineering Dalian University of Technology 2.Shandong SIASUN Industrial Software Research Institute Co. Ltd.

KeyWords： two-dimensional irregular parts no-fit polygon heuristic rule elitist strategy genetic tabu search algorithm

ClassificationCode：TP391

year,vol(issue):pagenumber：2024,49(4):54-61

Abstract：

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.

Funds：

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

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

Reference：

[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.

Service：

【This site has not yet opened Download Service】【Add Favorite】