Transactions of Materials and Heat Treatment

Title：A hybrid solving algorithm on two-dimensional irregular graphics nesting problem

Authors： Du Bing Guo Xiaoqiang Fang Jie Wang Peng Rao Yunqing

Unit： State Key Laboratory of Digital Manufacturing Equipment and Technology Huazhong University of Science and Technology

KeyWords： two-dimensional irregular graphics nesting problem hybrid nesting algorithm no-fit polygon hybrid placement strategy adaptive genetic algorithm

ClassificationCode：

year,vol(issue):pagenumber：2022,47(3):39-45

Abstract：

For the two-dimensional irregular graphics nesting problem, a hybrid nesting algorithm (AGAHA) based on heuristic placement strategy and adaptive genetic algorithm was implemented. Firstly, considering the problem that the placement strategy of a single index was easy to fall into the local optimum, a hybrid placement strategy based on no-fit polygon (NFP) was proposed, which comprehensively considered the overall compactness and local compactness of the nesting effect. Then, in order to improve the efficiency of searching for the optimal solution, an adaptive genetic algorithm was used when optimizing the order of graphs. Based on the standard genetic algorithm, the crossover and mutation probabilities were adaptively changed according to changes in population fitness. Finally, the standard test cases in the literature and the cases in the actual production were used to test separately. The results show that the AGAHA algorithm is better than the ordinary genetic algorithm combined with BL algorithm in most cases, and in the actual cases, the results of AGAHA algorithm are better than the result of manual nesting.

Funds：

国家自然科学基金资助项目（51975231）；中央高校基本科研业务费专项基金资助项目（2019kfyXKJC043）

作者简介：杜冰（1998-），男，硕士研究生 E-mail：rover_du@qq.com 通信作者：饶运清（1968-），男，教授，博士生导师 E-mail：ryq@hust.edu.cn

Reference：

[1]Freeman H, Shapira R. Determining the minimum-area encasing rectangle for an arbitrary closed curve[J]. Communications of the ACM, 1975, 18(7):409-413.

[2]Jakobs S. On genetic algorithms for the packing of polygons[J]. European Journal of Operational Research, 1996, 88(1):165-181.

[3]Dori D, Benbassat M. Efficient nesting of congruent convex figures[J]. Communications of the ACM, 1984, 27(3):228-23.

[4]贾志欣, 殷国富,罗阳.二维不规则零件排样问题的遗传算法求解[J].计算机辅助设计与图形学学报,2002，(5):467-470.

Jia Z X, Yin G F, Luo Y. Two-dimensional irregular parts packing with genetic algorithm[J]. Journal of Computer-aided Design & Computer Graphics, 2002，(5):467-470.

[5]于洋, 查建中,唐晓君.基于学习的遗传算法及其在布局中的应用[J].计算机学报,2001，(12):1242-1249.

Yu Y, Zha J Z, Tang X J. Learning based GA and application in packing[J]. Chinese Journal of Computers, 2001，(12):1242-1249.

[6]刘海明, 周炯,吴忻生.应用临界多边形方法与小生境遗传算法求解不规则排样问题[J].小型微型计算机系统,2016,37(5):1002-1007.

Liu H M, Zhou J, Wu X S. Using no-fit polygon method and niche genetic algorithm to solve irregular packing problem[J]. Journal of Chinese Mini-micro Computer Systems, 2016,37(5):1002-1007.

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

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

[8]Blazewicz J, Hawryluk P, Walkowiak R. Using a tabu search approach for solving the two-dimensional irregular cutting problem[J]. Annals of Operations Research, 1993, 41(4):313-325.

[9]Pinheiro P R, Amaro Júnior B, Saraiva R D. A random-key genetic algorithm for solving the nesting problem[J]. International Journal of Computer Integrated Manufacturing, 2016, 29(11): 1159-1165.

[10]Baker B S, Coffman J E G, Rivest R L. Orthogonal packing in two dimensions[J]. SIAM Journal on Computing, 1980, 9:846-855.

[11]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:34-57.

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

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

[14]李科林. 基于临界多边形的二维不规则排样问题的研究[D].武汉：华中师范大学,2019.

Li K L. Research of Two-dimensional Irregular Layout Problem Based on No-fit Polygon[D]. Wuhan:Central China Normal University, 2019.

[15]汤德佑, 周子琳.基于临界多边形的不规则件启发式排样算法[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.

[16]唐萍. 衣片排样系统中局部搜索算法及其他相关问题的研究[D].广州：华南理工大学,2011.

Tang P. Research of Local Search Algorithm and Other Related Issues in Clothes Packing System[D]. Guangzhou: South China University of Technology, 2011.

[17]林庆武. 皮革智能排样系统的开发[D].杭州：浙江大学,2006.

Lin Q W. Development of Intelligent Leather Nesting System[D]. Hangzhou: Zhejiang University,2006.

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

[19]Holland J H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence[M]. MIT Press, 1975.

[20]Srinivas M, Patnaik L M. Adaptive probabilities of crossover and mutation in genetic algorithms[J]. IEEE Transactions on Systems, Man, and Cybernetics, 1994, 24(4): 656-667.

[21]ESICUP. EURO special interest group on cutting and packing[EB/OL]. https://www.euro-online.org/websites/esicup, 2021- 01-15.

Service：

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