Geodesic
Some constructions for solving routing problems using decompositions and transformations of target sets
Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 34 (2024) no. 4, pp. 518-540 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Issues related to solving the additive problem of sequential traversal of sets with precedence restrictions and cost functions that allow dependence on the list of tasks are considered. The basic method is a broadly understood dynamic programming (DP), supplemented in the case of problems of appreciable dimension by decompositions of the family of tasks and transformation of the parameters of the original problem. Possible applications are related, in particular, to the problem of tool control in figured sheet cutting of parts on CNC machines. In this problem, an important circumstance is taking into account the precedence conditions, which have, in particular, the following meaning: in the case of a part with holes, cutting of each of the internal contours (corresponding to the holes) should precede cutting of the external contour. The quality criterion itself in this problem, as a rule, is additive. Another type of constraints concerns avoiding thermal deformations of parts. When using the approach with penalties for violating the conditions associated with effective heat dissipation during cutting, cost functions arise that allow dependence on the list of tasks completed to date. Note that in another applied problem, namely, in the problem of dismantling radiation hazardous objects, cost functions arise with dependence on the list of tasks that have not been completed at the moment (and, consequently, concern the objects that have not been dismantled). As a result, we arrive at a very general problem with precedence constraints and cost functions with dependence on the list of tasks. The decomposition applied in the case of a noticeable dimensionality with subsequent implementation of the DP requires, on the one hand, the development of clustering methods, and, on the other, the construction of an adequate structure for distributing global precedence conditions among clusters. In the theoretical part of the work, the case of two clusters is discussed, which makes it possible to cover with a single scheme a number of practically interesting problems of a range (in terms of dimensionality) type. An algorithm for constructing a composite solution is indicated, including a stage of clustering training based on a greedy algorithm. This “composite” algorithm is implemented on a PC; a computational experiment was carried out.
Keywords: dynamic programming, precedence conditions
Mots-clés : route 
@article{VUU_2024_34_4_a3,
     author = {A. G. Chentsov and P. A. Chentsov},
     title = {Some constructions for solving routing problems using decompositions and transformations of target sets},
     journal = {Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹ\^uternye nauki},
     pages = {518--540},
     year = {2024},
     volume = {34},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VUU_2024_34_4_a3/}
}
TY  - JOUR
AU  - A. G. Chentsov
AU  - P. A. Chentsov
TI  - Some constructions for solving routing problems using decompositions and transformations of target sets
JO  - Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
PY  - 2024
SP  - 518
EP  - 540
VL  - 34
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/VUU_2024_34_4_a3/
LA  - ru
ID  - VUU_2024_34_4_a3
ER  - 
%0 Journal Article
%A A. G. Chentsov
%A P. A. Chentsov
%T Some constructions for solving routing problems using decompositions and transformations of target sets
%J Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
%D 2024
%P 518-540
%V 34
%N 4
%U http://geodesic.mathdoc.fr/item/VUU_2024_34_4_a3/
%G ru
%F VUU_2024_34_4_a3
A. G. Chentsov; P. A. Chentsov. Some constructions for solving routing problems using decompositions and transformations of target sets. Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 34 (2024) no. 4, pp. 518-540. http://geodesic.mathdoc.fr/item/VUU_2024_34_4_a3/

[1] Melamed I.I., Sergeev S.I., Sigal I.Kh., “The traveling salesman problem. I: Theoretical issues”, Automation and Remote Control, 50:9 (1989), 1147–1173 | MR | Zbl | Zbl

[2] Gutin G., Punnen A.P., The traveling salesman problem and its variations, Springer, New York, 2007 | DOI | MR | Zbl

[3] Cook W.J., In pursuit of the traveling salesman. Mathematics at the limits of computation, Princeton University Press, Princeton, 2012 | MR | Zbl

[4] Gimadi E.Kh., Khachai M.Yu., Extreme problems on sets of permutations, UMC UPI, Yekaterinburg, 2016

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

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

[7] Little J.D.C., Murty K.G., Sweeney D.W., Karel C., “An algorithm for the traveling salesman problem”, Operations Research, 11:6 (1963), 972–989 | DOI | Zbl

[8] Lee Moon-Kyu, Kwon Ki-Bum, “Cutting path optimization in CNC cutting processes using a two-step genetic algorithm”, International Journal of Production Research, 44:24 (2006), 5307–5326 | DOI | Zbl

[9] Yu Wenchao, Lu Linji, “A route planning strategy for the automatic garment cutter based on genetic algorithm”, 2014 IEEE Congress on Evolutionary Computation (CEC), IEEE, 2014, 379–386 | DOI

[10] Dewil R., Vansteenwegen P., Cattrysse D., “Construction heuristics for generating tool paths for laser cutters”, International Journal of Production Research, 52:20 (2014), 5965–5984 | DOI

[11] Petunin A.A., “About some strategies of the programming of tool route by developing of control programs for thermal cutting machines”, Vestnik Ufimskogo Gosudarstvennogo Aviatsionnogo Tekhnicheskogo Universiteta. Seriya: Upravlenie, Vychislitel’naya Tekhnika i Informatika, 13:2(35) (2009), 280–286 (in Russian)

[12] Petunin A.A., Chentsov A.G., Chentsov P.A., “On routing tool motion on the sheet cutting NPC machines”, St. Petersburg State Polytechnical University Journal. Computer Science. Telecommunication and Control Systems, 2013, no. 2(169), 103–111 (in Russian)

[13] Petunin A.A., “General model of Tool Path Problem for the CNC sheet cutting machines”, IFAC-PapersOnline, 52:13 (2019), 2662–2667 | DOI

[14] Petunin A.A., Chentsov A.G., Chentsov P.A., Optimal tool routing on CNC sheet cutting machines. Mathematical models and algorithms, Ural Federal University, Yekateriburg, 2020

[15] Korobkin V.V., Sesekin A.N., Tashlykov O.L., Chentsov A.G., Routing methods and their applications in problems of improving the safety and efficiency of operation of nuclear power plants, Novye Tekhnologii, Moscow, 2012

[16] Chentsov A.G., “A bottleneck routing problem with a system of priority tasks”, Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, 61 (2023), 156–186 (in Russian) | DOI | Zbl

[17] Chentsov A.G., Chentsov A.A., “Dynamic programming and questions of solvability of route bottleneck problem with resource constraints”, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp’yuternye Nauki, 32:4 (2022), 569–592 (in Russian) | DOI | MR | Zbl

[18] Chentsov A.G., Chentsov A.A., Chentsov P.A., “The routing bottlenecks problem (optimization within zones)”, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp’yuternye Nauki, 34:2 (2024), 267–285 (in Russian) | DOI | MR | Zbl

[19] Chentsov A.G., Chentsov A.A., Sesekin A.N., Routing problems with non-additive cost aggregation, URSS, Moscow, 2020

[20] Chentsov A.G., Chentsov P.A., “An extremal two-stage routing problem and procedures based on dynamic programming”, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 28:2 (2022), 215–248 (in Russian) | DOI | MR

[21] Chentsov A.G., Chentsov P.A., “Two-stage dynamic programming in the routing problem with decomposition”, Automation and Remote Control, 84:5 (2023), 609–632 | DOI | DOI | MR | Zbl

[22] Chentsov A.G., Chentsov P.A., “Dynamic programming in the routing problem: decomposition variant”, Russian Universities Reports. Mathematics, 27:137 (2022), 95–124 (in Russian) | DOI | Zbl

[23] Chentsov A.G., Chentsov A.A., Chentsov P.A., “Extremal routing problem with internal losses”, Proceedings of the Steklov Institute of Mathematics, 264:suppl. 1 (2009), S87–S106 | DOI | MR | Zbl

[24] Chentsov A.G., “Constrained optimal routing”, Doklady Mathematics, 78:3 (2008), 859–863 | DOI | MR | Zbl

[25] Chentsov A.G., Chentsov A.A., “Route problem with constraints depending on a list of tasks”, Doklady Mathematics, 92:3 (2015), 685–688 | DOI | DOI | MR | Zbl

[26] Chentsov A.G., “Problem of successive megalopolis traversal with the precedence conditions”, Automation and Remote Control, 75:4 (2014), 728–744 | DOI | MR | Zbl

[27] Chentsov A.G., Extreme tasks of routing and distribution of tasks: theory questions, Regular and Chaotic Dynamics, Institute of Computer Science, Moscow–Izhevsk, 2008

[28] Kuratowski K., Mostowski A., Set theory, North-Holland, Amsterdam, 1967 | MR

[29] Dieudonné J., Foundations of modern analysis, Academic Press, New York, 1960 | MR | Zbl

[30] Cormen T.H., Leiserson C.E., Rivest R.L., Introduction to algorithms, McGraw-Hill, New York, 1990 | MR | Zbl

[31] Chentsov A.G., Sets, events, probability (basic structures), Ural State Technical University — UPI, Yekaterinburg, 2006

[32] 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