Оптимизационные и геометрические проблемы интегрированной задачи нерегулярного 2D раскроя и маршрутизации

А. А. Петунин

Оптимизационные и геометрические проблемы интегрированной задачи нерегулярного 2D раскроя и маршрутизации

А. А. Петунин

Аннотация

В статье рассматривается интегрированная задача 2D раскроя и маршрутизации с единым оптимизационным критерием (Integrated Nesting and Routing Problem, INRP). Эта задача возникает при проектировании технологических процессов раскроя материала на станках листовой резки с ЧПУ. Впервые дается её математическая постановка в общем виде для случая многолистового раскроя и двух типов интегрированного аддитивного оптимизационного критерия, различающихся определением стоимости маршрута режущего инструмента станка с ЧПУ. Задача иллюстрируется точным решением модельного примера. Показывается, что большая часть формальных ограничений связано с технологическими особенностями процесса резки материала при получении из него листовых деталей. Отдельно выделяется класс сложных (с точки зрения математической формализации) ограничений, получивших название «динамических». Отмечается, что соблюдение динамических ограничений задачи маршрутизации инструмента может определяться решениями некоторых геометрических задач на плоскости, а существующие подходы к решению интегрированной задачи INRP, основанные на применении математических моделей дискретной оптимизации, практически не учитывают этот тип ограничений, что приводит к недопустимым технологическим решениям. Описывается подход, основанный на понятии сегмента резки, который обеспечивает учет геометрических ограничений задачи маршрутизации инструмента. В заключении делается вывод о необходимости корректировки форматов данных, используемых для решения второй задачи INRP (Cutting Path Problem), и их дополнении геометрической информацией о раскройной карте и технологической информацией о процессе резки

Ключевые слова

нерегулярный 2D раскрой; cutting path problem; INRP; динамические геометрические ограничения; сегмент резки; endpoint cutting problem; дискретная оптимизация

Полный текст:

PDF

Литература

Wascher G, Hausner H, and Schumann H. (2007) “An improved typology of cutting and packing problems” // European Journal of Operational Research, Vol. 183, No. 3, 2007, pp. 1109-1130. doi:10.1016/j.ejor.2005.12.047.

Guo B, Zhang Y, Hu J, Li J, Wu F, Peng Q, and Zhang Q (2022). “Two-dimensional irregular packing problems: A review” // Front. Mech. Eng 8:966691. doi: 10.3389/fmech.2022.96669.

Romanova T., Stoyan Y., Pankratov A., et al.: (2021) “Optimal layout of ellipses and its application for additive manufacturing” // Int. J. Prod. Res. 2021, 59(2), 560–575.

Dewil R., Vansteenwegen P., and Cattrysse D. (2016). “A review of cutting path algorithms for laser cutters” // International Journal of Advanced Manufacturing Technology, 87(5), 1865–1884. doi:10.1007/s00170-016-8609-1.

Fernandes Silva, Everton (2020) “The cutting path determination problem: input files and solutions' layouts” // Mendeley Data, V5, doi: 10.17632/vffwyvbdzy.5.

Junior B. A.; de Carvalho G. N.; Santos M. C.; Pinheio P. R.; Celedonio J. W. L. “Evolutionary algorithms for optimization sequence of cut in the laser cutting path problem” // Appl. Sci. 2023, 13, 10133. https://doi.org/10.3390/app131810133.

Petunin A. A. (2011) “Development of CAM-system for sheet cutting machines as an innovation example” // Innovative information technology: Theory and practice. International scientific edition: materials of the international workshop (Karlsruhe–Ufa–Dresden, April 8-13, 2011), Ufa: UGATU, pp. 47-50.

Петунин А. А., Котел Н. С., Таваева А. Ф. (2023). Об одном примере оптимального решения интегрированной задачи 2D-раскроя и маршрутизации инструмента станков листовой резки с ЧПУ // Вестник Югорского государственного университета, № 4, стр. 88-101. https://doi.org/10.18822/byusu20230488-101. [[ Petunin A. A., Kotel N. S., Tavaeva A. F. “About one optimal solution example to the integrated 2d nesting and routing problem for CNC sheet cutting machines” // Yugra State University Bulletin. 2023. Vol. 19, No. 4, pp. 88-101. doi: 10.18822/byusu20230488-101. (In Russian). ]].

Верхотуров М. А., Тарасенко П. Ю. Математическое обеспечение задачи оптимизации пути режущего инструмента при плоском фигурном раскрое на основе цепной резки // Вестник УГАТУ. 2008. T. 10, № 2(27). С. 123-130. [[ Verkhoturov M. A., Tarasenko P. Yu. “Mathematical support for the problem of optimizing the path of a cutting tool in flat figured cutting based on chain cutting” // Bulletin of Ufa State Aviation Technical University. 2008. Vol. 10, No. 2(27), pp. 123-130. (In Russian). ]]

Tavaeva A., Petunin A., Ukolov S., Krotov V. (2019) “A cost minimizing at Laser Cutting of Sheet Parts on CNC Machines” // Mathematical Optimization Theory and Operations Research. MOTOR’19. Communications in Computer and Information Science. Springer. doi: 10.1007/978-3-030-33394-2_33.

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, vol.149, pp. 1–9. doi: 10.1016/j.cie.2020.106757.

Oliveira L. T., Carravilla M. A., Oliveira J. F., & Toledo F. M. B. (2023) “A biobjective matheuristic for the integrated solution of the irregular strip packing and the cutting path determination problems” // Pesquisa Operacional, 43. https://doi.org/ 10.1590/0101-7438.2023.043.00275212.

Sherif, S.U., Jawahar, N., Balamurali, M.:(2014) “Sequential optimization approach for nesting and cutting sequence in laser cutting” // J. Manuf. Syst., 2014, 33(4), 624–638. https://doi.org/10.1016/j.jmsy.2014.05.011.

Оптимальная маршрутизация инструмента станков фигурной листовой резки с числовым программным управлением. Математические модели и алгоритмы: монография / А. А. Петунин, А. Г. Ченцов, П. А. Ченцов. Екатеринбург: Изд-во Уральского университета, 2020. 247 с. [[ Optimal Routing of the Tool of Figured Sheet Cutting Machines with Numerical Control. Mathematical Models and Algorithms: Monograph” / A. A. Petunin, A. G. Chentsov, P. A. Chentsov. Ekaterinburg: Publishing House of Ural University, 2020. (In Russian). ]]

Chentsov A. G., Chentsov P. A. (2023) “Two-stage dynamic programming in the routing problem with decomposition” // Autom Remote Control 84, 543–563. https://doi.org/10.1134/S0005117923050053.

Hajad M, Tangwarodomnukun V, Dumkum C, Jaturanonda C. (2020) “Solving the laser cutting path problem using population-based simulated annealing with adaptive large neighborhood search” // KEM 2020; 833:29–34. https://doi.org/ 10.4028/www.scientific.net/kem.833.29.

Amaro Junior B. A., Santos M. C., Carvalho G. N., Araújo L. J., & Pinheiro P. R. (2021). “Metaheuristics for the minimum time cut path problem with different cutting and sliding speeds” // Algorithms, 14, 305.

Dewil R., Vansteenwegen P., Cattrysse D. (2014) “Construction heuristics for generating tool paths for laser cutters” // International Journal of Production Research, Mar. 2014, 1-20. 13, 2015, 1690., pp. 060002-1–060002-7.

Noor Hatem, Yusri Yusof, Aini Zuhra A. Kadir, Mohammed M. A. (2020). “Review of tool path optimization in CNC machines: methods and its applications based on artificial intelligence” // International Journal of Advanced Science and Technology 29 (04), 3368 -. http://sersc.org/journals/index.php/IJAST/article/view/24422.

Salman R., Ekstedt F., Damaschke P. “Branch-and-bound for the precedence constrained generalized traveling salesman problem” // Operations Research Letters, 2020, vol. 48, no. 2, pp. 163–166. DOI: 10.1016/j.orl.2020.01.009.

Kudriavtsev A., Khachay M.: “PCGLNS: adaptive heuristic solver for the precedence constrained GTSP” (2020). https://github.com/AndreiKud/PCGLNS/

Daniil Khachai, Ruslan Sadykov, Olga Battaia, Michael Khachay, “Precedence constrained generalized traveling salesman problem: Polyhedral study, formulations, and branch-and-cut algorithm” // European Journal of Operational Research, Volume 309, Issue 2,2023, Pages 488-505, https://doi.org/10.1016/j.ejor.2023.01.039.

Makarovskikh T., Panyukov A., Savitskiy E.: “Mathematical models and routing algorithms for economical cutting tool paths” // Int. J. Prod. Res. 56(3), 1171–1188 (2018). https://doi.org/10.1080/00207543.2017.1401746.

Makarovskikh T., Panyukov A., Savitsky E. “Software development for cutting tool routing problems” //Procedia Manufacturing. 2019. Vol. 29 No. SHEMET 2019, pp. 567-574. DOI: 10.1016/j.promfg.2019.02.123.

Petunin A., Ukolov S. (2024). “Iterative algorithm for the generalized segmental continuous cutting problem with optimization time constraint” // Intelligent and Fuzzy Systems. INFUS 2024. Lecture Notes in Networks and Systems, vol 1089. Springer, Cham. https://doi.org/10.1007/978-3-031-67195-1_59.

Верхотуров М. А., Верхотурова Г. Н. Об одном способе построения No-Fit Polyhedron при решении задачи плотного размещения трёхмерных объектов // СИИТ. 2023. Т. 5, № 6(15). С. 50-56. EDN WVTNES. [[ Verkhoturov M. A., Verkhoturova G. N. “On one method of constructing No-Fit Polyhedron when solving the problem of dense placement of three-dimensional objects” // SIIT. 2023. Vol. 5, No. 6(15), pp. 50-56. EDN WVTNES. (In Russian). ]]

Верхотуров М. А., Верхотурова Г. Н. О предварительной обработке информации о заготовках в задачах плоского фигурного раскроя // СИИТ. 2023. Т. 5, № 1(10). С. 25-33. EDN BOPKWP. [[ Verkhoturov M. A., Verkhoturova G. N. “Preliminary processing of information about blanks in problems of flat figure cutting” // SIIT. 2023. Vol. 5, No. 1(10), pp. 25-33. EDN BOPKWP. (In Russian). ]]

Усманова А. Р., Валиахметова Ю. И. Особенности задач-триплетов в задаче упаковки // СИИТ. 2023. Т. 5, № 1(10). С. 34 40. EDN VSYIOY. [[ Usmanova A. R., Valiakhmetova Yu. I. “Features of triplet problems in the packing problem” // SIIT. 2023. Vol. 5, No. 1(10), pp. 34-40. EDN VSYIOY. (In Russian). ]]

Усманова А. Р., Валиахметова Ю. И. Особенности метода поиска с запретами для задачи упаковки // СИИТ. 2022. Т. 4, № 2(9). С. 37-42. EDN NASXQA. [[ Usmanova A. R., Valiakhmetova Yu. I. “Features of the tabu search method for the packing problem” // SIIT. 2022. Vol. 4, No. 2(9), pp. 37-42. EDN NASXQA. (In Russian). ]]

Ссылки

На текущий момент ссылки отсутствуют.