Some applications of optimization routing problems with additional constraints

A. A. Petunin   ; A. G. Chentsov   ; P. A. Chentsov

Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 32 (2022) no. 2, pp. 187-210

Résumé

The paper deals with an extremal routing problem with constraints. In the general formulation, it is assumed that the objects of visiting are any non-empty finite sets — megalopolises. The main applied problem considered in this study is the tool path optimization problem for CNC sheet-cutting machines, known as the Cutting Path Problem. This problem arises at the stage of developing control programs for CNC machines. Other applications are also possible. In particular, the results obtained in the chapter can be used in the problem of minimizing the radiation dose when dismantling a system of radiation-hazardous elements after accidents at nuclear power plants and in transport problems. Among tasks constraints, the precedence constraints are investigated. These constraints can be used to reduce computational complexity. As the main method, the study used broadly understood dynamic programming. The offered realization of the method takes into account the precedence constraints and the dependence of the objective functions on the task list. This dependence belongs to the class of very complex conditions that determine the route admissibility at each routing step, depending on the tasks already completed or, on the contrary, not yet completed. As applied to the Cutting Path Problem, the dependence of the objective function on the task list makes it possible to reduce thermal deformations of the material during cutting. The chapter provides a mathematical formalization of an extremal routing problem with additional constraints, a description of the method, and the exact algorithm obtained with its help. The order of task execution, the specific trajectory of the process, and the starting point are optimized.

Détail

Keywords: dynamic programming, additional constraints, routing, CNC sheet cutting machines, tool path problem.
Mots-clés : megalopolises

Bibliographie

[1] V. V. Korobkin, A. N. Sesekin, O. L. Tashlykov, A. G. Chentsov, Metody marshrutizatsii i ikh prilozheniya v zadachakh povysheniya effektivnosti i bezopasnosti ekspluatatsii atomnykh stantsii, Novye tekhnologii, M., 2012

[2] A. G. Chentsov, “Dynamic programming in routing problems (nuclear power, Engineering)”, AIP Conference Proceedings, 2315:1 (2020), 040011 | DOI

[3] A. A. Petunin, A. G. Chentsov, P. A. Chentsov, Optimalnaya marshrutizatsiya instrumenta mashin figurnoi listovoi rezki s chislovym programmnym upravleniem. Matematicheskie modeli i algoritmy, Uralskii universitet, Ekaterinburg, 2020

[4] A. G. Chentsov, P. A. Chentsov, A. A. Petunin, A. N. Sesekin, “Model of megalopolises in the tool path optimisation for CNC plate cutting machines”, International Journal of Production Research, 56:14 (2018), 4819–4830 | DOI

[5] G. Gutin, A. P. Punnen, The traveling salesman problem and its variations, Springer Science and Business Media, 2006 | MR

[6] W. J. Cook, In pursuit of the traveling salesman: mathematics at the limits of computation, Princeton University Press, 2011 | MR

[7] E. K. Gimadi, M. Yu. Khachai, Ekstremalnye zadachi na mnozhestvakh perestanovok, Izd. UMTs UPI, Ekaterinburg, 2016

[8] I. I. Melamed, S. I. Sergeev, I. Kh. Sigal, “Zadacha kommivoyazhera. Voprosy teorii”, Avtomatika i telemekhanika, 1989, no. 9, 3–33 | Zbl

[9] R. Bellman, “Dynamic programming treatment of the travelling salesman problem”, Journal of the ACM, 9:1 (1962), 61–63 | DOI | MR | Zbl

[10] M. Held, R. M. Karp, “A dynamic programming approach to sequencing problems”, Journal of the Society for Industrial and Applied Mathematics, 10:1 (1962), 196–210 | DOI | MR | Zbl

[11] A. G. Chentsov, Ekstremalnye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii, Regulyarnaya i khaoticheskaya dinamika, M. Izhevsk, 2008

[12] R. Dewil, P. Vansteenwegen, D. Cattrysse, “Sheet metal laser cutting tool path generation: dealing with overlooked problem aspects”, Key Engineering Materials, 639 (2015), 517–524 | DOI

[13] K. A. Dowsland, W. B. Dowsland, “Solution approaches to irregular nesting problems”, European Journal of Operational Research, 84 (1995), 506–521 | DOI | Zbl

[14] Y. Stoyan, A. Pankratov, T. Romanova, “Placement problems for irregular objects: mathematical modeling, optimization and applications”, Optimization Methods and Applications, In Honor of Ivan V. Sergienko's 80th Birthday, Springer, Cham, Switzerland, 2017, 521–559 | DOI | Zbl

[15] R. Alvarez-Valdes, M. A. Carravilla, J. F. Oliveira, “Cutting and packing”, Handbook of Heuristics, Springer, Berlin, 2018, 931–998 | DOI | MR

[16] J. S. Hoeft, U. S. Palekar, “Heuristics for the plate-cutting traveling salesman problem”, IIE Transactions, 29 (1997), 719–731 | DOI

[17] R. Dewil, P. Vansteenwegen, D. Cattrysse, “A review of cutting path algorithms for laser cutters”, International Journal of Advanced Manufacturing Technology, 87:5 (2016), 1865–1884 | DOI

[18] R. Dewil, P. Vansteenwegen, D. Cattrysse, M. Laguna, T. Vossen, “An improvement heuristic framework for the laser cutting tool path problem”, International Journal of Production Research, 53:6 (2015), 1761–1776 | DOI

[19] N. Levichev, G. C. Rodrigues, J. R. Duflou, “Real-time monitoring of fiber laser cutting of thick plates by means of photodiodes”, Procedia CIRP, 94 (2020), 499–504 | DOI

[20] S. Sonawane, P. Patil, R. Bharsakade, P. Gaigole, “Optimizing tool path sequence of plasma cutting machine using tsp approach”, E3S Web of Conferences, 184 (2020), 01037 | DOI

[21] N. D. Ganelina, V. D. Frolovskii, “Dekompozitsionnyi metod optimizatsii proektirovaniya upravlyayuschikh programm teplovoi rezki metalla na oborudovanii s ChPU”, Nauchnyi Vestnik NGTU, 2006, no. 2 (23), 9–19

[22] M. A. Verkhoturov, P. Yu. Tarasenko, “Matematicheskoe obespechenie zadachi optimizatsii puti rezhuschego instrumenta pri ploskom figurnom raskroe na osnove tsepnoi rezki”, Vestnik Ufimskogo gosudarstvennogo aviatsionnogo tekhnicheskogo universiteta, 10:2 (2008), 123–130

[23] T. A. Makarovskikh, A. V. Panyukov, “Software for constructing A-chains with ordered enclosing for a plane connected 4-regular graph”, IFAC-PapersOnLine, 52 (2019), 2650–2655 | DOI | MR

[24] T. A. Makarovskikh, A. V. Panyukov, E. A. Savitskiy, “Mathematical models and routing algorithms for economical cutting tool paths”, International Journal of Production Research, 56:3 (2018), 1171–1188 | DOI

[25] T. Makarovskikh, A. Panyukov, E. Savitsky, “Software development for cutting tool routing problems”, Procedia Manufacturing, 29 (2019), 567–574 | DOI

[26] A. A. Petunin, P. A. Chentsov, “Routing in CNC cutting machines: Engineering constraints”, Acta Polytechnica Hungarica, 17:8 (2020), 165–177 | DOI

[27] A. Petunin, “General model of tool path problem for the CNC sheet cutting machines”, IFAC-PapersOnLine, 52:13 (2019), 2662–2667 | DOI

[28] A. A. Petunin, C. Stylios, “Optimization models of tool path problem for CNC sheet metal cutting machines”, IFAC-PapersOnLine, 49:12 (2016), 23–28 | DOI

[29] D. Mejia, A. Moreno, A. Arbelaiz, J. Posada, O. Ruiz-Salguero, R. Chopitea, “Accelerated thermal simulation for three-dimensional interactive optimization of computer numeric control sheet metal laser cutting”, Journal of Manufacturing Science and Engineering, 140:3 (2018), 031006 | DOI

[30] A. A. Petunin, E. G. Polyshuk, P. A. Chentsov, S. S. Ukolov, V. I. Krotov, “The termal deformation reducing in sheet metal at manufacturing parts by CNC cutting machines”, IOP Conference Series: Materials Science and Engineering, 613 (2019), 012041 | DOI

[31] M. Z. Lagerkvist, M. Nordkvist, M. Rattfeldt, “Laser cutting path planning using CP”, Principles and Practice of Constraint Programming, Springer, Berlin, 2013, 790–804 | DOI

[32] H. Makbul, T. Viboon, J. Chorkaew, D. Chaiya, “Laser cutting path optimization using simulated annealing with an adaptive large neighborhood search”, The International Journal of Advanced Manufacturing Technology, 103:1-4 (2019), 781–792 | DOI

[33] M. Balamurali, N. Jawahar, B. Sivaramakrishnan, M. Thirumoolam, “Realization of effective laser blanking process by heat zone spread resistance coating and optimization methods”, Materials Research Express, 6:4 (2019), 046416 | DOI

[34] Y. Yuan, D. Cattaruzza, M. Ogier, F. Semet, “A branch-and-cut algorithm for the generalized traveling salesman problem with time windows”, European Journal of Operational Research, 286:3 (2020), 849–866 | DOI | MR | Zbl

[35] M. Khachai, E. Neznakhina, “Approximability of the problem about a minimum-weight cycle cover of a graph”, Doklady Mathematics, 91:2 (2015), 240–245 | DOI | MR | Zbl

[36] M. Gendreau, G. Ghiani, E. Guerriero, “Time-dependent routing problems: A review”, Computers and Operations Research, 64 (2015), 189–197 | DOI | MR | Zbl

[37] J. Kinable, A. Cire, W.-J. van Hoeve, “Hybrid optimization methods for time-dependent sequencing problems”, European Journal of Operational Research, 259:3 (2017), 887–897 | DOI | MR | Zbl

[38] A. F. Alkaya, E. Duman, “A new generalization of the traveling salesman problem”, Applied and Computational Mathematics, 9:2 (2010), 162–175 | MR | Zbl

[39] G. Gutin, D. Karapetyan, “A memetic algorithm for the generalized traveling salesman problem”, Natural Computing, 9:1 (2010), 47–60 | DOI | MR | Zbl

[40] K. Helsgaun, “Solving the equality Generalized Traveling Salesman Problem using the Lin-Kernighan-Helsgaun algorithm”, Mathematical Programming Computation, Springer, Berlin-Heidelberg, 2015, 1–19 | MR

[41] S. L. Smith, F. Imeson, “GLNS: An effective large neighborhood search heuristic for the Generalized Traveling Salesman Problem”, Computers and Operations Research, 87 (2017), 1–19 | DOI | MR | Zbl

[42] R. Salman, J. S. Carlson, F. Ekstedt, D. Spensieri, J. Torstensson, R. Soderberg, “An industrially validated CMM inspection process with sequence constraints”, Procedia CIRP, 44 (2016), 138–143 | DOI

[43] R. Salman, F. Ekstedt, P. Damaschke, “Branch-and-bound for the Precedence Constrained Generalized Traveling Salesman Problem”, Operations Research Letters, 48:2 (2020), 163–166 | DOI | MR | Zbl

[44] M. Hajad, V. Tangwarodomnukun, C. Dumkum, C. Jaturanonda, “Solving the laser cutting path problem using population-based simulated annealing with adaptive large neighborhood search”, Key Engineering Materials, 833 (2020), 29–34 | DOI

[45] J. Li, H. Zhu, T. Zhang, L. He, Y. Guan, H. Zhang, “Automatic generation of auxiliary cutting paths based on sheet material semantic information”, The International Journal of Advanced Manufacturing Technology, 106 (2020), 3787–3797 | DOI

[46] Y. Xin, Y. Li, W. Li, G. Wang, “Towards efficient milling of multi-cavity aeronautical structural parts considering aco-based optimal tool feed position and path”, Micromachines, 12:1 (2021), 88 | DOI

[47] D. H. Al-Janan, T. K. Liu, “Path optimization of CNC PCB drilling using hybrid Taguchi genetic algorithm”, Kybernetes, 45 (2016), 107–125 | DOI

[48] N. D. Starostin, K. V. Mironov, K. V. Mironov, “Algorithm modification of the level-by-level approximation to the minimum route”, 2017 IEEE International Symposium on Signal Processing and Information Technology (ISSPIT), 2017, 270–275 | DOI

[49] V. A. Kandasamy, S. Udhayakumar, “Effective location of micro joints and generation of tool path using heuristic and genetic approach for cutting sheet metal parts”, International Journal of Material Forming, 13 (2020), 317–329 | DOI | MR

[50] K. Kuratovskii, A. Mostovskii, Teoriya mnozhestv, Mir, M., 1970

[51] Zh. Dedonne, Osnovy sovremennogo analiza, Mir, M., 1964

[52] T. H. Cormen, C. E. Leizerson, R. L. Rivest, C. Stein, Introduction to algorithms, Third Edition, MIT Press, Cambridge, 2009 | MR | Zbl

[53] A. G. Chentsov, P. A. Chentsov, “Marshrutizatsiya v usloviyakh ogranichenii: zadacha o poseschenii megapolisov”, Avtomatika i telemekhanika, 2016, no. 11, 1957–1974 | Zbl

[54] E. L. Lawler, Efficient implementation of dynamic programming algorithms for sequencing problems, Report BW106, Mathematisch Centrum, Amsterdam, 1979

[55] A. Tavaeva, A. Petunin, S. Ukolov, V. Krotov, “A cost minimizing at laser cutting of sheet parts on CNC machines”, Communications in Computer and Information Science, 10 (2019), 422–437 | DOI | MR