moitvivt Моделирование, оптимизация и информационные технологии Modeling, Optimization and Information Technology 2310-6018 Издательство 10.26102/2310-6018/2023.43.4.011 1454 Программное обеспечение для решения интегрированной задачи оптимизации раскроя материала и маршрутизации инструмента для оборудования листовой резки с числовым программным управлением Software for solving the integrated nesting and routing problem applied to CNC sheet cutting machines 0000-0001-9770-4298 Таваева Анастасия Фидагилевна Tavaeva Anastasiya Fidagilevna tavaeva_a_f@bk.ru aff-1 0000-0003-2540-1305 Петунин Александр Александрович Petunin Aleksandr Aleksandrovich aapetunin@urfu.ru aff-2 Уральский оптико-механический завод» им. Э.С. Яламова Уральский федеральный университет имени первого Президента России Б.Н. Ельцина Joint-Stock Company "Production Association "Ural Optical and Mechanical Plant named after Mr. E.S. Yalamov" Ural Federal University Уральский федеральный университет имени первого Президента России Б.Н. Ельцина Институт математики и механики им. Н.Н. Красовского Ural Federal University N.N. Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences 01 01 2026 1 1 10.26102/2310-6018/2023.43.4.011 Copyright © Авторы, 2026 2026 This work is licensed under a Creative Commons Attribution 4.0 International License

В статье рассматривается вопрос разработки алгоритмов и программного обеспечения для решения интегрированной задачи раскроя и маршрутизации (The Integrated Nesting and Routing Problem (INRP)). Эта задача объединяет две известные задачи – задачу двумерного фигурного раскроя (принадлежит к классу задач раскроя-упаковки) и задачу оптимизации маршрута режущего инструмента для машин с числовым программным управлением (задача оптимизации траектории). В интегрированной задаче рассматривается единая целевая функция, рассчитываемая как сумма стоимости использованного для раскроя материала и стоимости процесса резки. В настоящей статье предлагается общая структура программного обеспечения и функциональная модель подсистемы автоматического раскроя и маршрутизации для решения интегрированной задачи применительно к оборудованию листовой резки с числовым программным управлением. В подсистеме автоматического раскроя и маршрутизации реализованы алгоритмы нахождения допустимого варианта раскроя для некоторых типов деталей и соответствующие этому варианту раскроя алгоритмы проектирования маршрута инструмента, ориентированные на минимизацию интегрированного показателя стоимости. Разработанные алгоритмы реализованы в виде открытого программного обеспечения на языке программирования Python. В статье приводятся результаты численных экспериментов, проведенных для лазерного комплекса листовой резки с ЧПУ. Разработанное программное обеспечение опробовано также для широкого класса практических задач при подготовке управляющих программ для различного оборудования листовой резки.

The paper discusses the issue of developing algorithms and software for solving the integrated nesting and routing problem (INRP). This problem combines two known matters: 2D nesting problem (belongs to the class of Cutting & Packing) and the problem of cutting process optimization (Cutting Path Problem). The integrated additive objective function in INRP is a sum of used material cost for nesting and cutting process cost. The paper proposes a general software structure and a functional model of the automatic nesting and routing subsystem for solving an integrated problem in relation to the CNC sheet cutting equipment. The subsystem of automatic cutting and routing implements algorithms for finding an admissible nesting pattern for some types of parts and corresponding to this nesting pattern algorithms for the tool path generation focused on minimizing the integrated cost criterion. The algorithms are implemented as open source software using Python. The paper presents the results of numerical experiments for the CNC laser complex of sheet cutting. The developed software has also been tested for several types of practical tasks in control programs generation for various sheet cutting equipment.

 оборудование листовой резки с ЧПУ интегрированная задача раскроя и маршрутизации листовой раскрой маршрут инструмента стоимость процесса резки оптимизация CNC sheet cutting machine integrated nesting and routing problem sheet cutting tool path cutting process cost optimization Работа выполнена при поддержке Российского Научного Фонда (грант № 23-21-00343) The research was funded by the Russian Science Foundation (grant No. № 23-21-00343). References Romanova T., Stoyan Y., Pankratov A., Litvinchev I., Marmolejo J.A. Decomposition algorithm for irregular placement problems. Advances in Intelligent Systems and Computing. 2020;1072:214–221. DOI: 10.1007/978-3-030-33585-4_21. Wӓscher G., Hauβner H., Schumann H. An improved typology of cutting and packing problems. European Journal of Operational Research. 2007;183:1109–1130. DOI: 10.1016/j.ejor.2005.12.047. Dewil R., Vansteenwegen P., Cattrysse D. A review of cutting path algorithms for laser cutters. Int.J. Adv. Manuf. Technol. 2016;87(5-8):1865–1884. DOI: 10.1007/s00170-016-8609-1. Петунин А.А., Ченцов А.Г., Ченцов П.А. Оптимальная маршрутизация инструмента машин фигурной листовой резки с числовым программным управлением. Математические модели и алгоритмы. Екатеринбург: УрФУ; 2020. 247 с. Kuznetsov P.M., Yagopol’skii A.G. Optimizing the idling path of large metal-cutting machines. Russian Engineering Research. 2020:1081–1083. DOI: 10.3103/S1068798X20120382. Chentsov A.G., Chentsov A.A. A discrete – continuous routing problem with precedence constraints. Proceedings of the Steklov Institute of Mathematics. 2018;300(1):56–71. DOI: 10.1134/S0081543818020074. Tavaeva A.F., Petunin A.A. Algorithm for solving the integrated problem of the rectangular parts nesting and tool routing for CNC sheet cutting machines. Lecture Notes in Electrical Engineering (in press). Oliveira L., Silva E., Oliveira J. et al. Integrating irregular strip packing and cutting path determination problems: A discrete exact approach. Comput. Ind. Eng. 2020;149:1–9. DOI: 10.1016/j.cie.2020.106757. Qi D., Rao Y. An integrated approach on cut planning and nesting for metal structures manufacturing. Journal of Engineering Manufacture. 2014;228(4):527–539. DOI: 10.1177/0954405413500979. Salem K.H., Oliveira J.F., Silva E. Cutting and packing problems under uncertainty: literature review and classification framework. International Transactions in Operational Research. 2023;30(13). DOI: 10.1111/itor.13318. Eapen N., Heckendorn R.B. PENGRAV: a practical polynomial time algorithm for optimizing the engraving path of an automatic engraving machine using a 3/2 approximation algorithm. Int. J. of Advanced Manufacturing Technology. 2022;123(3). DOI: 10.1007/s00170-022-10148-9. Lui X., Chang D. An improved method for optimizing CNC laser cutting paths for ship hull components with thicknesses up to 24 mm. Journal of Marine Science and Engineering. 2023;11(3). DOI: 10.3390/jmse11030652. Cuellar D., Palacio A., Ospina E., Botero M. et al. Modeling and solving the endpoint cutting problem. Int. Transactions in Operational Research. 2021;30(12). DOI: 10.1111/itor.13091. Leao A., Toledo F., Oliveria J., Carravilla M. Irregular packing problems: A review of mathematical models. European journal of operational research. 2019;282(3):803–822. DOI: 10.1016/j.ejor.2019.04.045. Guo B., Zhang Y., Hu J et al. Two-dimensional irregular packing problems: A review. Front. Mech. Eng. 2022;79:1–15. DOI: 10.3389/fmech.2022.966691. Mezghani S., Haddar B., Chabchoub H. The evolution of rectangular bin packing problem – A review of research topics, applications, and cited papers. Journal of Industrial and Management Optimization. 2022;19(5). DOI: 10.3934/jimo.2022088. Nascimento D., Cherri A., Oliveira J. The two-dimensional cutting stock problem with usable leftovers: mathematical modelling and heuristic approaches. Oper Res Int J. 2022;22:5363–5403. DOI: 10.1007/s12351-022-00735-9. Amaro J., Santos M., de Carvalho G et al. Metaheuristics for the minimum time cut path problem with different cutting and sliding speeds. Algorithms. 2021;14(11):305. DOI: DOI: 10.3390/a14110305. Junior B., Carvalho G., Santos M. Evolutionary algorithms for optimization sequence of cut in the laser cutting Path Problem. Applied Sciences. 2023;13(18). DOI: 10.3390/app131810133. Hajad M., Saerang V., Jaturanonda C., Dumkum C. Laser cutting path optimization with minimum heat accumulation. The International Journal of Advanced Manufacturing Technology. 2019;105(3). DOI: 10.1007/s00170-019-04455-x. Levichev N., García A., Dewil R et al. A virtual sensing approach for quality and productivity optimization in laser flame cutting. The International Journal of Advanced Manufacturing Technology. 2022;121(9-10). DOI: 10.1007/s00170-022-09750-8. Tavaeva A., Petunin A., Polishchuk E. Methods of cutting cost minimizing in problem of tool route optimization for CNC laser machines. International Conference on Industrial Engineering. 2020:447–455. DOI: 10.1007/978-3-030-22063-1_48. Таваева А.Ф., Петунин А.А. Алгоритм решения интегрированной задачи раскроя и маршрутизации на примере типовых деталей для оборудования листовой резки с числовым программным управлением. Вестник Башкирского университета. 2022;27(3):535–540. DOI: 10.33184/bulletin-bsu-2022.3.8. Таваева А.Ф., Петунин А.А. Новый алгоритм раскроя и маршрутизации для систем автоматизированного проектирования управляющих программ оборудования листовой резки с числовым программным управлением. Вестник уральского государственного университета путей сообщения. 2022;56(4):21–27. DOI: 10.20291/2079-0392-2022-4-21-27. Ascheuer N., Junger M., Reinelt G. A Branch & cut algorithm for the asymmetric traveling salesman problem with precedence constraints. Computational Optimization and Applications. 2000;17(1):61–84. DOI: 10.1023/A:1008779125567. Malik A., Sharma A., Saroha V. Greedy Algorithm. International Journal of Scientific and Research Publications. 2013:3(8). Tavaeva A., Petunin A., Ukolov S. et al. A Cost Minimizing at Laser Cutting of Sheet Parts on CNC Machines. Mathematical Optimization Theory and Operations Research. Communications in Computer and Information Science. 2019;1090:422–437. DOI: 10.1007/978-3-030-33394-2_33.

The authors declare that there are no conflicts of interest present.