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

Voir la notice de l'article provenant de la source Math-Net.Ru

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: ``bottleneck problem''},
     journal = {Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹ\^uternye nauki},
     pages = {121--140},
     publisher = {mathdoc},
     volume = {26},
     number = {1},
     year = {2016},
     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
PB  - mathdoc
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
%I mathdoc
%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/