phone +7 (3412) 91 60 92
mail imi@udsu.ru
ru-RU Russian
Home » Issues » Archive of Issues » 2016 - 1 issue » pp. 121-140

Archive of Issues

Russia Yekaterinburg
Year
2016
Volume
26
Issue
1
Pages
121-140
<<
>>
Section Mathematics
Title Routing of displacements with dynamic constraints: “bottleneck problem”
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 A complicated variant of the “bottleneck problem” is considered, namely: the problem of sequential visiting of megalopolises with preceding constraints. It is supposed that costs functions and “current” constraints with respect to displacements selection depend on the tasks list which is not completed at the moment. The variant of widely understood dynamic programming is proposed, it doesn't foresee (with preceding conditions) construction of the whole array of the Bellman function values; the special layers of this function realizing in its totality the partial array of its values are constructed (it helps to decrease the calculation complexity). An algorithm of the problem value (global extremum) calculation is proposed, the computer realization of which implies the existence of only one layer of the Bellman function in a memory of computer; the obtained value may be used for the heuristics testing. The optimal algorithm of “complete” solving of the route problem is constructed, within which all layers of the Bellman function are used at the route and trace constructing.
Keywords route, trace, preceding conditions, dynamic programming
UDC 519.6
MSC 05A05, 97N70, 97N80
DOI 10.20537/vm160110
Received 27 February 2016
Language Russian
Citation 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.
References
  1. Chentsov A.G., Chentsov A.A. Route problem with constraints depending on a list of tasks, Doklady Mathematics, 2015, vol. 92, issue 3, pp. 685-688.
  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).
  3. Chentsov A.A., Chentsov A.G. Route problem in which cost functions and “current” constraints depend from tasks list, Vestn. Tambov. Univ. Ser. Estestv. Tekh. Nauki, 2015, vol. 20, no. 5, pp. 1521-1525 (in Russian).
  4. Petunin A.A. About some strategies of the programming of tool route by developing of control programs for thermal cutting machines, Vestnik UGATU, 2009, vol. 13, no. 2 (35), pp. 280-286 (in Russian).
  5. Frolovskii V.D. Automation of designing control programs for thermal cutting of metal by CNC equipment, Informatsionnye Tekhnologii v Proektirovanii i Proizvodstve, 2005, no. 4, pp. 63-66 (in Russian).
  6. Petunin A.A., Chentsov A.G., Chentsov P.A. To the question about instrument routing in the automated machines of the sheet cutting, St. Petersburg State Polytechnical University Journal. Computer Science. Telecommunication and Control Systems, 2013, issue 2 (169), pp. 103-111 (in Russian).
  7. Chentsov A.G., Salii Ya.V. A model of “nonadditive” routing problem where the costs depend on the set of pending tasks, Vestn. Yuzhno-Ural. Gos. Univ., Ser. Mat. Model. Program., 2015, vol. 8, no. 1, pp. 24-45.
  8. Kuratovskii K., Mostovskii A. Teoriya mnozhestv (Theory of sets), Moscow: Mir, 1970, 416 p.
  9. Dieudonne J. Osnovy sovremennogo analiza (Foundations of modern analysis), Moscow: Mir, 1964, 430 p.
  10. Cormen T., Leiserson Ch., Rivest R. Introduction to algorithms (1st ed.), MIT Press and McGraw-Hill, 1990. Translated under the title Algoritmy. Postroenie i analiz (The algorithms. Construction and analysis), Moscow: Moscow Center for Continuous Mathematical Education, 1999, 960 p.
  11. Chentsov A.G. Ekstremal'nye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii (Extremal problems of routing and assignment of tasks: questions of theory), Moscow-Izhevsk: Institute of Computer Science, 2008, 240 p.
  12. Cheblokov I.B., Chentsov A.G. About one route problem with interior works, Vestn. Udmurt. Univ. Mat. Mekh. Komp'yut. Nauki, 2012, no. 1, pp. 96-119 (in Russian).
  13. Chentsov A.G. To question of routing of works complexes, Vestn. Udmurt. Univ. Mat. Mekh. Komp'yut. Nauki, 2013, no. 1, pp. 59-82 (in Russian).
Full text
/doc/issues-2016/16-01-10.pdf
<< Previous article
Next article >>