Geodesic
Dynamic programming in the generalized bottleneck problem and the start point optimization
Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 28 (2018) no. 3, pp. 348-363 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We consider one non-additive routing problem, which is a generalization of the well-known “bottleneck problem”. The parameter is assumed to be a positive number, the degree of which determines the weight of the corresponding stage of the displacement system. By varying the parameter, it is possible to make the initial or, on the contrary, the final stages of displacement dominant. The variant of aggregation of values with the above-mentioned weights corresponds to the ideological formulation of the “bottleneck problem”, but opens the possibility of investigating new versions of routing problems with constraints. It is assumed, however, that the statement of the problem is complicated by the dependence of values on the list of tasks and includes restrictions in the form of precedence conditions. In addition, in the interest of optimization, an arbitrary choice of the initial state from a given a priori set is allowed. For the construction, the apparatus of widely understood dynamic programming is used. The possibility of realizing a global extremum with any degree of accuracy under conditions when the set of possible initial states is not finite is investigated.
Keywords: route optimization, dynamic programming, start point optimization. 
@article{VUU_2018_28_3_a5,
     author = {A. G. Chentsov and A. A. Chentsov and A. N. Sesekin},
     title = {Dynamic programming in the generalized bottleneck problem and the start point optimization},
     journal = {Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹ\^uternye nauki},
     pages = {348--363},
     year = {2018},
     volume = {28},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VUU_2018_28_3_a5/}
}
TY  - JOUR
AU  - A. G. Chentsov
AU  - A. A. Chentsov
AU  - A. N. Sesekin
TI  - Dynamic programming in the generalized bottleneck problem and the start point optimization
JO  - Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
PY  - 2018
SP  - 348
EP  - 363
VL  - 28
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VUU_2018_28_3_a5/
LA  - ru
ID  - VUU_2018_28_3_a5
ER  - 
%0 Journal Article
%A A. G. Chentsov
%A A. A. Chentsov
%A A. N. Sesekin
%T Dynamic programming in the generalized bottleneck problem and the start point optimization
%J Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
%D 2018
%P 348-363
%V 28
%N 3
%U http://geodesic.mathdoc.fr/item/VUU_2018_28_3_a5/
%G ru
%F VUU_2018_28_3_a5
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, mehanika, kompʹûternye nauki, Tome 28 (2018) no. 3, pp. 348-363. http://geodesic.mathdoc.fr/item/VUU_2018_28_3_a5/

[1] Gutin G., Punnen A. (eds.), The traveling salesman problem and its variations, Springer, Boston, 2007 | DOI | MR | Zbl

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

[3] Gimadi E. Kh., Khachai M. Yu., Extremal problems on sets of permutations, UMC UPI, Yekaterinburg, 2016, 220 pp.

[4] Melamed I. I., Sergeev S. I., Sigal I. Kh., “The traveling salesman problem. I: Theoretical issues”, Automation and Remote Control, 50:9 (1989), 1147–1173 | MR | Zbl

[5] Melamed I. I., Sergeev S. I., Sigal I. Kh., “The traveling salesman problem. II: Exact methods”, Automation and Remote Control, 50:10 (1989), 1303–1324 | MR | Zbl

[6] Melamed I. I., Sergeev S. I., Sigal I. Kh., “The traveling salesman problem. Approximate algorithms”, Automation and Remote Control, 50:11 (1989), 1459–1479 | MR | Zbl

[7] Sergeev S. I., “Algorithms for the minimax problem of the traveling salesman. I: An approach based on dynamic programming”, Automation and Remote Control, 56:7-2 (1995), 1027–1032 | MR | Zbl

[8] Kuratowski K., Mostowski A., Set Theory, North-Holland Publishing Company, Amsterdam, 1967, vii+417 pp. | MR

[9] Dieudonné J., Foundations of modern analysis, Academic Press Inc., New York, 1960, xiv+361 pp. | MR | Zbl

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

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

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

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

[14] Chentsov A. G., “On a parallel procedure for constructing the Bellman function in the generalized problem of courier with internal jobs”, Automation and Remote Control, 73:3 (2012), 532–546 | DOI | MR | Zbl

[15] Chentsov A. G., Chentsov A. A., “To the question of finding the value of a constrained route task”, Problemy Upravlenia i Informatiki, 2016, no. 1, 41–54 (in Russian)