Geodesic
A Parallel Procedure of Constructing Bellman Function in the Generalized Courier Problem with Interior Works
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, no. 12 (2012), pp. 53-76
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

A construction of the parallel realization of dynamic programming method for solving the problem of sequential visiting for sets (megalopolises) with constraints in the form of preceding conditions; this problem is called generalized courier problem. It is supposed that, on these sets, the works with inputs are fulfilled. The computing procedure used partial constructing of the Bellman function array and realized by layers of the position space is investigated. In the foundation of construction the idea of a discrete dynamic system is situated; for this system, attainability domains realized by recurrence scheme are constructed.
Mots-clés : route, megalopolis
Keywords: dynamic programming. 
@article{VYURU_2012_12_a5,
     author = {A. G. Chentsov},
     title = {A {Parallel} {Procedure} of {Constructing} {Bellman} {Function} in the {Generalized} {Courier} {Problem} with {Interior} {Works}},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a, Matemati\v{c}eskoe modelirovanie i programmirovanie},
     pages = {53--76},
     year = {2012},
     number = {12},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURU_2012_12_a5/}
}
TY  - JOUR
AU  - A. G. Chentsov
TI  - A Parallel Procedure of Constructing Bellman Function in the Generalized Courier Problem with Interior Works
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
PY  - 2012
SP  - 53
EP  - 76
IS  - 12
UR  - http://geodesic.mathdoc.fr/item/VYURU_2012_12_a5/
LA  - ru
ID  - VYURU_2012_12_a5
ER  - 
%0 Journal Article
%A A. G. Chentsov
%T A Parallel Procedure of Constructing Bellman Function in the Generalized Courier Problem with Interior Works
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
%D 2012
%P 53-76
%N 12
%U http://geodesic.mathdoc.fr/item/VYURU_2012_12_a5/
%G ru
%F VYURU_2012_12_a5
A. G. Chentsov. A Parallel Procedure of Constructing Bellman Function in the Generalized Courier Problem with Interior Works. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, no. 12 (2012), pp. 53-76. http://geodesic.mathdoc.fr/item/VYURU_2012_12_a5/

[1] Chentsov A. A., Chentsov A. G., Chentsov P. A., “Extreme Routing Problem with Internal Losses”, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 14:3 (2008), 183–201

[2] Chentsov A. G., “About the Optimal Routing with the Conditions of Constraints”, Doklady Akademii nauk, 423:3 (2008), 303–307 | Zbl

[3] Chentsov A. A., Chentsov A. G., Chentsov P. A., “Extreme Movements of Routing Problem with Constraints and Internal Losses”, Izv. vysshikh uchebnykh zavedenii. Matematika, 2010, no. 6, 64–81 | MR

[4] Chentsov A. G., “Dynamic Programming Method in Extremal Problems with Constraints Routing”, Izv. RAN. Teoriya i sistemy upravleniya, 2010, no. 3, 61–73

[5] Chentsov A. A., Chentsov A. G., Chentsov P. A., “The Conditions of Precedence in a Problem of Extreme Route with the Inner Workings”, Algoritmy i programmnye sredstva parallel'nikh vichislenii, 2010, no. 10, 60–76 | MR

[6] Chentsov A. G., Extremal Problems of Routing and Assignment of Tasks: Questions of Theory, NITS «Regular and Chaotic Dynamics». Izhevsk Institute of Computer Research, Izhevsk, 2008, 240 pp.

[7] Melamed I. I., Sergeev S. I., Sigal I. Kh., “Traveling Salesman Problem. Questions of Theory”, Avtomatika i telemekhanika, 1989, no. 9, 3–34 | MR

[8] Melamed I. I., Sergeev S. I., Sigal I. Kh., “Traveling Salesman Problem. Precise Algorithms”, Avtomatika i telemekhanika, 1989, no. 10, 3–29

[9] Melamed I. I., Sergeev S. I., Sigal I. Kh., “Traveling Salesman Problem. Approximate Algorithms”, Avtomatika i telemekhanika, 1989, no. 11, 3–26

[10] Geri M., Jonson D., Calculating Machines and Difficult Problems, Mir, M., 1982, 416 pp. | MR

[11] Bellman R., “Use Dynamic Programming to the Problem of a Salesman”, Kiberneticheskii sbornik, 9, Mir, M., 1964, 219–228

[12] Held M., “Use Dynamic Programming to the Problems of Ordering”, Kiberneticheskii sbornik, 9, Mir, M., 1964, 202–218

[13] Sesekin A. N., Tashlykov O. L., Shcheklein S. E., Kuklin M. Yu., Chentsov A. G., Kadnikov A. A., “Use of Dynamic Programming Method to Optimize the Trajectory of Movement of Workers in Radioactive Areas to Minimize Exposure”, Izv. vysshikh uchebnykh zavedenii. Yadernaya energetika, 2006, no. 2, 41–48 | MR

[14] Sesekin A. N., Tashlykov O. L., Shcheklein S. E., Chentsov A. G., “Development of Optimal Algorithms for Decommissioning of NPP by the Methods of Mathematical Modeling”, Izv. vysshikh uchebnykh zavedenii. Yadernaya energetika, 2009, no. 2, 115–120 | MR

[15] Kuratovskii K., Mostovskii A., Set Theory, Mir, M., 1970, 416 pp. | MR

[16] Kormen A., Leizerson Ch., Rivest R., The Algorithms. Construction and Analysis, MTSNMO, M., 1990, 960 pp.

[17] Warga Dj., Optimal Control of Differential and Functional Equations, Nauka, M., 1977, 624 pp. | MR

[18] Krasovskii N. N., Theory of traffic control, Nauka, M., 1968, 475 pp. | MR

[19] Panasyuk A. I., Panasyuk V. I., Asymptotic Optimization Trunk of Control Systems, Nauka i tekhnika, Minsk, 1986, 296 pp. | MR