The multi-contour cutting application in algorithms of shortest cutting tool path generation

The cutting path problem for sheet cutting machines with computer numerical control (further - CNC) is considered in this article. The classification of routing problem is given and description of algorithms for solving this problem is given too. The method of Intermittent Cutting Problem is proposed. This method based on application of multi-contour cutting techniques, namely common cut (when several contours are cut by one motion of cutter). The proposed method is to be combined parts in «blocks» and cutting of contours is performed by common cut application usually with one piercing. The three classes of parts (rectangular, triangular and parts with outer contour type like trapezium) are highlighted for which the proposed method is applicable. At the same time presence of inner contours is allowed. The some results of computing experiments are given compared with problem solution obtained by CCP-Relax algorithm (where the standard cutting technique is used). The calculation was performed for nesting maps from open library CPPLib.

1. Verkhoturov M.A., Tarasenko P.Yu. Matematicheskoe obespechenie zadachi optimizatsii puti rezhushchego instrumenta pri ploskom figurnom raskroe na osnove tsepnoi rezki. Vestnik UGATU. Upravlenie, VTiT. 2008;2(27):123-130. (In Russ)

2. Petunin A.A. Modeling of tool path for the CNC sheet cutting machines. AIP: proceedings inter. conf. 2015. Available at: http://www.scopus.com/inward/record.url?scp=85078881584&partnerID=8YFLogxK. DOI: 10.1016/j.ifacol.2019.11.609 (accessed 10.07.2021).

3. Hoeft J., Palekar U. S. Heuristics for the plate-cutting traveling salesman problem. IIE Transactions. 1997;29(9). DOI: 10.1023/A:1018582320737.

4. Dewil R., Vansteenwegen P., Cattrysse D. A review of cutting path algorithms for laser cutters. International Journal of Advanced Manufacturing Technology. 2016;87(5). DOI: 10.1007/s00170-016-8609-1.

5. Petunin A. A., Stylios C. Optimization Models of Tool Path Problem for CNC Sheet Metal Cutting Machines. IFAC-PapersOnLine. 2016;49(12). Available at: http://www.scopus.com/inward/record.url?scp=84992362161&partnerID=8YFLogxK. DOI: 10.1016/j.ifacol.2016.07.544 (accessed 10.07.2021).

6. Chentsov A.G. Ekstremal'nye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii. M.; Izhevsk: NITs «Regulyarnaya i khaoticheskaya dinamika»; 2008. (In Russ)

7. Chentsov A.G., Khachai D.M. Effektivnyi metod resheniya zadachi obkhoda megapolisov pri ogranicheniyakh predshestvovaniya spetsial'nogo tipa. Proceedings 47th Internetional Youth School -Conference «Modern Problems in Mathematics and its Applications». 2016;(1662):191-199. (In Russ)

8. Petunin A.A, Chentsov A.A., Chentsov A.G., Chentsov P.A. Elements of dynamic programming in local improvement constructions for heuristic solutions of routing problems with constraints. Automation and Remote Control. 2017;78(4). DOI: 10.1134/S0005117917040087.

9. Tamajidy M., Paslar S., Baharuding H., Hibs T., Arrifin M. Biogeography based optimization (BBO) algorithm to minimize non-productive time during hole-making process. International Journal of Production Research. 2015;53(6). DOI: 10.1080/00207543.2014.965356.

10. Yun Y, Chung H., Moon C. Hybrid genetic algorithm approach for precedence-constrained sequencing problem. Computers and Industrial Engineering. 2013;(65):137-147.

11. Murzakaev R.T., Shilov V.S., Burylov A.V. Primenenie metaevristicheskikh algoritmov dlya minimizatsii dliny kholostogo khoda rezhushchego instrumenta. Vestnik PNIPU. Elektrotekhnika, informatsionnye tekhnologii, sistemy upravleniya. 2015;(14):123-136. (In Russ)

12. Yang W., Zhao Y., Jie J., Wang W. An effective algorithm for tool path airtime optimization during leather cutting. Advanced Material Research. 2010:373-377. DOI: 10.4028/www.scientific.net/AMR.102-104.373.

13. Veeramani S., Kumar D. Optimization of the nibbling operation of the NC turret punch press. International Journal of Production Research. 1998;36(7):1901-1916.

14. Vicencio K., Davis B., Gentilini I. Multi-goal path planning based on the generalized Traveling Salesman Problem with neighborhoods. IEEE/RSJ International Conference on Intelligent Robots and Systems. 2014. DOI: 10.1109/IROS.2014.6942974.

15. Petunin A. A., Polishchuk E.G., Ukolov, S.S. On the new algorithm for solving continuous cutting problem. IFAC-PapersOnLine. 2019;52(13):2320-2325. DOI: 10.1016/j.ifacol.2019.11.552.

16. Tavaeva A.F., Petunin A.A. The accurate calculation of parts treatment cost from sheet metal on the CNC laser cutting machine in problem of tool routing optimization. Modeling, Optimization and Information Technology. 2018;4(23). Available at: https://moit.vivt.ru/wp-content/uploads/2018/10/TavaevaPetunin_4_18_1.pdf. DOI: 10.26102/2310-6018/2018.23.4.022 (accessed 10.07.2021). (In Russ)

17. Petunin A., Khalyavka A., Khachay M., Kudriavtsev A., Chentsov P., Polishchuk E., Ukolov S. Library of Sample Image Instances for the Cutting Path Problem. Lecture Notes in Computer Science. 2021;(12665). DOI: 10.1007/978-3-030-68821-9_21.