Geodesic
Routing of displacements with dynamic constraints: “bottleneck problem”
Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 26 (2016) no. 1, pp. 121-140 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Mots-clés : route
Keywords: trace, preceding conditions, dynamic programming. 
@article{VUU_2016_26_1_a9,
     author = {A. G. Chentsov and A. A. Chentsov},
     title = {Routing of displacements with dynamic constraints: {\textquotedblleft}bottleneck problem{\textquotedblright}},
     journal = {Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹ\^uternye nauki},
     pages = {121--140},
     year = {2016},
     volume = {26},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VUU_2016_26_1_a9/}
}
TY  - JOUR
AU  - A. G. Chentsov
AU  - A. A. Chentsov
TI  - Routing of displacements with dynamic constraints: “bottleneck problem”
JO  - Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
PY  - 2016
SP  - 121
EP  - 140
VL  - 26
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VUU_2016_26_1_a9/
LA  - ru
ID  - VUU_2016_26_1_a9
ER  - 
%0 Journal Article
%A A. G. Chentsov
%A A. A. Chentsov
%T Routing of displacements with dynamic constraints: “bottleneck problem”
%J Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
%D 2016
%P 121-140
%V 26
%N 1
%U http://geodesic.mathdoc.fr/item/VUU_2016_26_1_a9/
%G ru
%F VUU_2016_26_1_a9
A. G. Chentsov; A. A. Chentsov. Routing of displacements with dynamic constraints: “bottleneck problem”. Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 26 (2016) no. 1, pp. 121-140. http://geodesic.mathdoc.fr/item/VUU_2016_26_1_a9/

[1] 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 | Zbl

[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, 21, no. 4, 2015, 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, 20:5 (2015), 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, 13:2(35) (2009), 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, 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, no. 2(169), 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., 8:1 (2015), 24–45 | Zbl

[8] Kuratovskii K., Mostovskii A., Theory of sets, Mir, Moscow, 1970, 416 pp. | MR

[9] Dieudonne J., Foundations of modern analysis, Mir, Moscow, 1964, 430 pp.

[10] Cormen T., Leiserson Ch., Rivest R., Introduction to algorithms, 1st ed., MIT Press and McGraw-Hill, 1990 | MR | Zbl

[11] Chentsov A. G., Extremal problems of routing and assignment of tasks: questions of theory, Institute of Computer Science, Moscow–Izhevsk, 2008, 238 pp.

[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, 96–119 (in Russian) | Zbl

[13] Chentsov A. G., “To question of routing of works complexes”, Vestn. Udmurt. Univ. Mat. Mekh. Komp'yut. Nauki, 2013, no. 1, 59–82 (in Russian) | Zbl