Geodesic
On the question of the optimization of permutations in the problem with dynamic constraints
Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 29 (2019) no. 3, pp. 363-381
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The “additive” problem of sequentially visiting megalopolises (nonempty finite sets) is considered; some tasks are executed as the megalopolises are visited. Permutations and operations are evaluated by cost functions that admit a dependence on the list of tasks. There are restrictions of different types, which include precedence conditions used in the “positive direction” (to reduce the complexity of calculations). In addition, this conception involves dynamical restrictions that are formed in the process of task execution. This conception is oriented to engineering applications associated with sheet cutting on CNC machines. An approach to constructing optimal solutions based on a nonstandard version of dynamic programming (DP) is investigated. This approach takes into account restrictions of different types, including dynamic constraints which naturally arise in sheet cutting applications (in particular, it takes into account heat tolerances related to diffusion of heat in the vicinities of tie-in points). In this regard, a combination of “direct” interdictions of movements and cutting and a system of penalties is allowed; in the latter case, cost functions with a dependence on the list of tasks arise. The variant of DP that is used allows one to optimize the selection of a starting point, the route, which is identified with a permutation of the indexes, and the trajectory corresponding to the above-mentioned route. An economical variant of DP is used at the stage of construction of the Bellman function. This conception allows avoiding calculation of the whole array of values of this function; instead, only the system of its layers is defined (in the case of using the precedence conditions, which are typical of the problem of sheet cutting, this conception results in a considerable reduction of calculation costs). An optimal DP-based algorithm is constructed and realized on PC, and the results of the computational experiment are presented.
Mots-clés : route
Keywords: path, precedence conditions. 
@article{VUU_2019_29_3_a6,
     author = {A. G. Chentsov and A. A. Chentsov},
     title = {On the question of the optimization of permutations in the problem with dynamic constraints},
     journal = {Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹ\^uternye nauki},
     pages = {363--381},
     year = {2019},
     volume = {29},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VUU_2019_29_3_a6/}
}
TY  - JOUR
AU  - A. G. Chentsov
AU  - A. A. Chentsov
TI  - On the question of the optimization of permutations in the problem with dynamic constraints
JO  - Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
PY  - 2019
SP  - 363
EP  - 381
VL  - 29
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VUU_2019_29_3_a6/
LA  - ru
ID  - VUU_2019_29_3_a6
ER  - 
%0 Journal Article
%A A. G. Chentsov
%A A. A. Chentsov
%T On the question of the optimization of permutations in the problem with dynamic constraints
%J Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
%D 2019
%P 363-381
%V 29
%N 3
%U http://geodesic.mathdoc.fr/item/VUU_2019_29_3_a6/
%G ru
%F VUU_2019_29_3_a6
A. G. Chentsov; A. A. Chentsov. On the question of the optimization of permutations in the problem with dynamic constraints. Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 29 (2019) no. 3, pp. 363-381. http://geodesic.mathdoc.fr/item/VUU_2019_29_3_a6/

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

[2] M. S. Kosheleva, A. A. Chentsov, A. G. Chentsov, “On a routing problem with constraints that include dependence on a task list”, Tr. Inst. Mat. Mekh. Ural. Otd. Ross. Akad. Nauk, 21, no. 4, 2015, 178–195 (in Russian) | MR

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

[4] A. G. Chentsov, A. A. Chentsov, “Dynamic programming in the routing problem with constraints and costs depending on a list of tasks”, Doklady Mathematics, 88:3 (2013), 637–640 | DOI | DOI | MR | MR | Zbl

[5] N. N. Krasovskii, Game problems about meeting motions, Fizmatlit, M., 1970

[6] A. I. Panasyuk, V. I. Panasyuk, The asymptotic magistral optimization of the controllable systems, Nauka i tekhnika, Minsk, 1986 | MR

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

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

[9] G. Gutin, A. P. Punnen, The traveling salesman problem and its variations, Springer US, 2007, xviii+830 pp. | DOI | MR | Zbl

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

[11] E. Kh. Gimadi, M. Yu. Khachay, Extreme problems on sets of permutations, UMC UPI, Yekaterinburg, 2016, 220 pp.

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

[13] F. C. J. Lokin, “Procedures for travelling salesman problems with additional constraints”, European Journal of Operational Research, 3:2 (1979), 135–141 | DOI | Zbl

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

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

[16] T. H. Cormen, C. E. Leizerson, R. L. Rivest, Introduction to algorithms, MIT Press, Cambridge, 1990 | MR | Zbl

[17] A. G. Chentsov, Extreme problems of routing and assignment of tasks: questions of theory, Regular and Chaotic Dynamics, Institute of Computer Science, M.–Izhevsk, 2008

[18] A. G. Chentsov, “To question of routing of works complexes”, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2013, no. 1, 59–82 (in Russian) | DOI | MR | Zbl

[19] A. A. Petunin, “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)

[20] A. A. Petunin, A. G. Chentsov, P. A. Chentsov, “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)

[21] A. A. Petunin, A. G. Chentsov, P. A. Chentsov, “Local dynamic programming incuts in routing problems with restrictions”, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2014, no. 2, 56–75 (in Russian) | DOI | Zbl

[22] A. G. Chentsov, A. A. Chentsov, “Routing of displacements with dynamic constraints: “bottleneck problem””, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 26:1 (2016), 121–140 | DOI | MR | Zbl

[23] A. G. Chentsov, A. A. Chentsov, “A model variant of the problem about radiation sources utilization (iterations based on optimization insertions)”, Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, 50 (2017), 83–109 (in Russian) | DOI | Zbl

[24] A. G. Chentsov, A. A. Chentsov, A. N. Sesekin, “Dynamic programming in the generalized bottleneck problem and the start point optimization”, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 28:3 (2018), 348–363 (in Russian) | DOI | MR | Zbl

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

[26] A. G. Chentsov, “The Bellmann insertions in the route problem with constraints and complicated cost functions”, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2014, no. 4, 122–141 (in Russian) | DOI | Zbl

[27] A. G. Chentsov, “The Bellmann insertions in route problems with constraints and complicated cost functions. II”, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 26:4 (2016), 565–578 (in Russian) | DOI | MR | Zbl

[28] A. G. Chentsov, A. M. Grigoryev, “Optimizing multi-inserts in routing problems with constraints”, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 28:4 (2018), 513–530 (in Russian) | DOI | MR