Optimal routing in problems of sequential traversal of megapolises in the presence of constraints

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

Čelâbinskij fiziko-matematičeskij žurnal, Tome 7 (2022) no. 2, pp. 209-233.

Résumé

The problem of optimal routing of movements is considered with additional constraints such as precedence conditions and cost functions depending on the job list. Dependencies of this kind refer to the so-called dynamic restrictions, in which the value of the objective function at each step of the movement depends on the trajectory (history) of the path traveled and determines the admissibility of the selected movement. The considered statement is focused, first of all, on engineering applications related to the optimization of the route of the tool of CNC machines; other applications are possible. The objects of visit are non-empty finite sets — megacities. As the main problem in this paper, we consider the problem of optimal tool routing for CNC sheet cutting machines, known as the Cutting Path Problem or Tool Path Problem. This problem arises at the stage of development of control programs for the CNC machine, which set the tool path and a number of technological commands. Among the formal restrictions, the precedence conditions are especially distinguished, which are caused by the technological features of sheet cutting on CNC machines and which can be used to reduce the computational complexity of the problem being solved and construct feasible solutions. The main research method is the widely understood dynamic programming (DP), which takes into account the precedence conditions and the dependence of cost functions on the list of tasks. As applied to the problem of routing the tool of sheet cutting machines, the dependence of the objective function on the list of tasks makes it possible to reduce thermal deformations of the material during thermal cutting. The article provides a rigorous mathematical formalization of the problem of constrained movement routing and a description of the exact solution algorithm. In the process of solving, the order of tasks execution, the specific process trajectory and the starting point are optimized. The algorithm is implemented as a PC program; model examples are solved.

Détail

Keywords: megalopolises, route, trajectory, dynamic programming, precedence constraints, dynamic constraints, tool path optimization problem, CNC sheet cutting machine, feasible optimal solution.

Bibliographie

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

[2] Petunin A.A., Chentsov A.G., Chentszov P.A., Optimal routing of the tool of shaped sheet cutting machines with numerical control. Mathematical models and algorithms, Ural Federal University, Ekaterinburg, 2020 (In Russ.)

[3] Korobkin V.V., Sesekin A.N., Tashlykov O.L., Chenczov P.A., Routing methods and their applications in the tasks of increasing the efficiency and safety of operation of nuclear power plants, Novye tekhnologii Publ., Moscow, 2012 (In Russ.)

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

[5] Bellman R., “Application of dynamic programming to the traveling salesman problem”, Cybernetic collection, 9 (1964), 219–228 (In Russ.)

[6] Held M., Karp R., “Application of dynamic programming to ordering problems”, Cybernetic collection, 9 (1964), 202–218 (In Russ.)

[7] Melamed I.I., Sergeev S.I., Sigal I.Kh., “The Travelling Salesman Problem. Issues in theory”, Automation and Remote Control, 50:9 (1989), 1147–1173 | MR | Zbl

[8] The Traveling Salesman Problem and Its Variations, eds. G. Gutin, A. P. Punnen, Springer Science Business Media, New York, 2006 | MR

[9] Cook W. J., In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation, Princeton University Press, Princeton, 2011 | MR

[10] Gimadi E.X., Khachay M.Y., Extreme problems on permutation sets, Ural Polytechnical Institute,, Ekaterinburg, 2016 (In Russ.)

[11] Chentsov A.G., Extreme problems of routing and assignment distribution: issues of theory, Izhevsk Institute of Computer Research, Moscow, Izhevsk, 2008 (In Russ.)

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

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

[14] Cherri L. H., Mundim L. R., Andretta M., Toledo F., Oliveira J., Carravilla M., “Robust mixed-integer linear programming models for the irregular strip packing problem”, European Journal of Operational Research, 253:3 (2016), 570–583 | DOI | MR | Zbl

[15] Stoyan Y., Pankratov A., Romanova T., “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, 2017, 521–559 | DOI | Zbl

[16] Alvarez-Valdés R., Carravilla M. A., Oliveira J. F., “Cutting and Packing”, Handbook of Heuristics, eds. R. Martí, P. Pardalos, M. Resende, Springer, Cham, 2018, 931–977 | DOI | MR

[17] Ganelina N.D., Frolovskiy V.D., “Decomposition method for optimizing the design of control programs for thermal metal cutting on CNC equipment”, Scientific Bulletin of NSTU, 2006, no. 2 (23), 9–19 (In Russ.)

[18] Verkhoturov M.A., Tarasenko P.Yu., “Mathematical support of the problem of optimization of the cutting tool path in flat curly cutting based on chain cutting”, Bulletin of Ufa State Aviation Technical University], 10:2 (2008), 123–130 (In Russ.)

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

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

[21] Makarovskikh T., Panyukov A., Savitsky E., “Software development for Cutting Tool Routing Problems”, Procedia Manufacturing, 29 (2019), 567–574 | DOI

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

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

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

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

[26] Eapen N. A., Heckendorn R. B., “Cutting path optimization for an automatic cutter in polynomial time using a 3/2 approximation algorithm”, The International Journal of Advanced Manufacturing Technology, 113 (2021), 3667–3679 | DOI

[27] Mejia D., Moreno A., Arbelaiz A., Posada J., Ruiz-Salguero O., Chopitea R., “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

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

[29] Verkhoturov M., Verkhoturova G., Zaripov D., Kondratyeva N., Valeev S., “Digital twin of the process of thermal cutting of flat material into figured parts”, International Workshop on Information, Computation, and Control Systems for Distributed Environments (Irkutsk, 2021), 2021, 209–219

[30] Lagerkvist M. Z., Nordkvist M., Rattfeldt M., “Laser cutting path planning using CP”, Principles and Practice of Constraint Programming, Lecture Notes in Computer Science, 8124, ed. C. Schulte, Springer-Verlag, Berlin, Heidelberg, 2013, 790–804 | DOI

[31] Balamurali M., Jawahar N., Balaji S., Manichandran T., “Realization of effective laser blanking process by heat zone spread resistance coating and optimization methods”, Materials Research Express, 6 (2019), 046416 | DOI

[32] Makbul H., Viboon T., Chorkaew J., Chaiya D., “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

[33] Yuan Y., Cattaruzza D., Ogier M., Semet F., “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

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

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

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

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

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

[39] Helsgaun K., “Solving the equality generalized traveling salesman problem using the Lin — Kernighan — Helsgaun Algorithm”, Mathematical Programming Computation, 7 (2015), 269–287 | DOI | MR | Zbl

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

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

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

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

[44] Starostin N. D., Mironov K., “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

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

[46] Kandasamy V. A., Udhayakumar S., “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:2 (2020), 317–329 | DOI | MR

[47] Kuratovskiy K., Mostovskiy A., Theory of sets, Mir Publ., Moscow, 1970 (In Russ.)

[48] Dieudonné J., Foundations of Modern Analysis, Academic Press, New York, London, 1960 | MR | Zbl

[49] Kormen T., Leyzerson C., Rivest R., Shtayn K., Algorithms. Construction and analysis, Publishing House ‘`Vil’yams" , Moscow, 2009 (In Russ.)

[50] Chentsov A.G., Chentsov P.A., “Routing under constraints: Problem of visit to megalopolises”, Automation and Remote Control, 77:11 (2016), 1957–1974 | DOI | MR | Zbl

[51] Lawler E., “Efficient Implementation of Dynamic Programming Algorithms for Sequencing Problems”, Report BW106, Mathematisch Centrum, Amsterdam, 1979, 1–16

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