phone +7 (3412) 91 60 92
mail imi@udsu.ru
ru-RU Russian
Home » Issues » Archive of Issues » 2019 - 3 issue » pp. 363-381

Archive of Issues

Russia Yekaterinburg
Year
2019
Volume
29
Issue
3
Pages
363-381
<<
>>
Section Mathematics
Title On the question of the optimization of permutations in the problem with dynamic constraints
Author(-s) Chentsov A.G.ab, Chentsov A.A.a
Affiliations Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciencesa, Ural Federal Universityb
Abstract 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.
Keywords route, path, precedence conditions
UDC 519.6
MSC 05A05, 97N70, 97N80
DOI 10.20537/vm190307
Received 28 June 2019
Language Russian
Citation Chentsov A.G., Chentsov A.A. On the question of the optimization of permutations in the problem with dynamic constraints, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2019, vol. 29, issue 3, pp. 363-381.
References
  1. Chentsov A.G., Chentsov A.A. Route problem with constraints depending on a list of tasks, Doklady Mathematics, 2015, vol. 92, no. 3, pp. 685-688. https://doi.org/10.1134/S1064562415060083
  2. Kosheleva M.S., Chentsov A.A., Chentsov A.G. On a routing problem with constraints that include dependence on a task list, Tr. Inst. Mat. Mekh. Ural. Otd. Ross. Akad. Nauk, 2015, vol. 21, no. 4, pp. 178-195 (in Russian). http://mi.mathnet.ru/eng/timm1240
  3. Chentsov A.G., Chentsov P.A. Routing under constraints: Problem of visit to megalopolises, Automation and Remote Control, 2016, vol. 77, no. 11, pp. 1957-1974. https://doi.org/10.1134/S0005117916110060
  4. Chentsov A.G., Chentsov A.A. Dynamic programming in the routing problem with constraints and costs depending on a list of tasks, Doklady Mathematics, 2013, vol. 88, no. 3, pp. 637-640. https://doi.org/10.1134/S1064562413060021
  5. Krasovskii N.N. Igrovye zadachi o vstreche dvizhenii (Game problems about meeting motions), Moscow: Fizmatlit, 1970.
  6. Panasyuk A.I., Panasyuk V.I. Asimptoticheskaya magistral'naya optimizatsiya upravlyaemykh sistem (The asymptotic magistral optimization of the controllable systems), Minsk: Nauka i tekhnika, 1986.
  7. Bellman R. Dynamic programming treatment of the travelling salesman problem, Journal of the ACM, 1962, vol. 9, issue 1, pp. 61-63. https://doi.org/10.1145/321105.321111
  8. Held M., Karp R.M. A dynamic programming approach to sequencing problems, Journal of the Society for Industrial and Applied Mathematics, 1962, vol. 10, no. 1, pp. 196-210. https://doi.org/10.1137/0110015
  9. Gutin G., Punnen A.P. (Eds.) The traveling salesman problem and its variations, Springer US, 2007, XVIII+830 p. https://doi.org/10.1007/b101971
  10. Cook W.J. In pursuit of traveling salesman. Mathematics at the limits of computation, New Jersey: Princeton University Press, 2012.
  11. Gimadi E.Kh., Khachay M.Yu. Ekstremal'nye zadachi na mnozhestvakh perestanovok (Extreme problems on sets of permutations), Yekaterinburg: UMC UPI, 2016, 220 p.
  12. Little G.D.C., Murty K.G., Sweeney D.W., Karel C. An algorithm for the traveling salesman problem, Operations Research, 1963, vol. 11, issue 6, pp. 972-989. https://doi.org/10.1287/opre.11.6.972
  13. Lokin F.C.J. Procedures for travelling salesman problems with additional constraints, European Journal of Operational Research, 1979, vol. 3, no. 2, pp. 135-141. https://doi.org/10.1016/0377-2217(79)90099-7
  14. Kuratowski K., Mostowski A. Set theory, Amsterdam: North-Holland, 1967. Translated under the title Teoriya mnozhestv, Moscow: Mir, 1970.
  15. Dieudonné J. Foundations of modern analysis, New York: Academic Press Inc., 1960. Translated under the title Osnovy sovremennogo analiza, Moscow: Mir, 1964.
  16. Cormen T.H., Leizerson C.E., Rivest R.L. Introduction to algorithms, Cambridge: MIT Press, 1990. Translated under the title Algoritmy: postroenie i analiz, Moscow: Moscow Center for Continuous Mathematical Education, 2000.
  17. Chentsov A.G. Ekstremal'nye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii (Extreme problems of routing and assignment of tasks: questions of theory), Moscow-Izhevsk: Regular and Chaotic Dynamics, Institute of Computer Science, 2008.
  18. Chentsov A.G. To question of routing of works complexes, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2013, issue 1, pp. 59-82 (in Russian). https://doi.org/10.20537/vm130107
  19. 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, 2009, vol. 13, no. 2 (35), pp. 280-286 (in Russian).
  20. 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, issue 2 (169), pp. 103-111 (in Russian).
  21. Petunin A.A., Chentsov A.G., Chentsov P.A. Local dynamic programming incuts in routing problems with restrictions, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2014, issue 2, pp. 56-75 (in Russian). https://doi.org/10.20537/vm140204
  22. Chentsov A.G., Chentsov A.A. Routing of displacements with dynamic constraints: “bottleneck problem”, Vestnik Udmurtskogo Universiteta.\ Matematika.\ Mekhanika.\ Komp'yuternye Nauki, 2016, vol. 26, issue 1, pp. 121-140. https://doi.org/10.20537/vm160110
  23. Chentsov A.G., Chentsov A.A. A model variant of the problem about radiation sources utilization (iterations based on optimization insertions), Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, 2017, vol. 50, pp. 83-109 (in Russian). https://doi.org/10.20537/2226-3594-2017-50-08
  24. Chentsov A.G., Chentsov A.A., Sesekin A.N. Dynamic programming in the generalized bottleneck problem and the start point optimization, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2018, vol. 28, issue 3, pp. 348-363 (in Russian). https://doi.org/10.20537/vm180306
  25. Korobkin V.V., Sesekin A.N., Tashlykov O.L., Chentsov A.G. Metody marshrutizatsii i ikh prilozheniya v zadachakh povysheniya bezopasnosti i effektivnosti ekspluatatsii atomnykh stantsii (Routing methods and their applications in problems of improving the safety and efficiency of operation of nuclear power plants), Moscow: Novye Tekhnologii, 2012.
  26. Chentsov A.G. The Bellmann insertions in the route problem with constraints and complicated cost functions, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2014, issue 4, pp. 122-141 (in Russian). https://doi.org/10.20537/vm140410
  27. Chentsov A.G. The Bellmann insertions in route problems with constraints and complicated cost functions. II, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2016, vol. 26, issue 4, pp. 565-578 (in Russian). https://doi.org/10.20537/vm160410
  28. Chentsov A.G., Grigoryev A.M. Optimizing multi-inserts in routing problems with constraints, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2018, vol. 28, issue 4, pp. 513-530 (in Russian). https://doi.org/10.20537/vm180406
Full text
/doc/issues-2019/19-03-07.pdf
<< Previous article
Next article >>