Geodesic
On the Nonstationary Variant of Generalized Courier Problem with Interior Works
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 6 (2013) no. 2, pp. 88-107 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The problem of the sequential circuit of megalopolises with preceding conditions and necessity of the interior works in megalopolises is considered in the article. It is supposed that the costs of permutations depend on the parameter having the sense of a discrete time. The above-mentioned dependence can reflect priorities of clients connected with served megalopolises and partially compensating inputs of executers. The constructed method corresponds to dynamic programming in a broad sense which is applied to solve the route problem with constraints. The extension of the problem, which use equivalent transformation of the system of constraints as a result of which route admissibility by precedence is changed into admissibility by deletion (the task from the list), introduced in the article. Therefore route constraints are reduced to the system of constraints by current interchange that allows us to obtain Bellman equations. To apply the later in the computational procedure of layers construction of Bellman equation we use the approach which implies the construction of the whole array of the values for the function mentioned; this approach is based on the use of essential lists of tasks (by precedence), which the saving of computations is achieved by. The use of the theory developed can be connected with the problems dealing with the reduction of radioactive influence on employees of atomic power plants at work under emergency conditions as well as the problems of transport service for a great number of clients under conditions of priority influencing the choice of service discipline.
Mots-clés : route
Keywords: preceding conditions, dynamic programming. 
@article{VYURU_2013_6_2_a6,
     author = {A. G. Chentsov and P. A. Chentsov},
     title = {On the {Nonstationary} {Variant} of {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 = {88--107},
     year = {2013},
     volume = {6},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURU_2013_6_2_a6/}
}
TY  - JOUR
AU  - A. G. Chentsov
AU  - P. A. Chentsov
TI  - On the Nonstationary Variant of Generalized Courier Problem with Interior Works
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
PY  - 2013
SP  - 88
EP  - 107
VL  - 6
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VYURU_2013_6_2_a6/
LA  - ru
ID  - VYURU_2013_6_2_a6
ER  - 
%0 Journal Article
%A A. G. Chentsov
%A P. A. Chentsov
%T On the Nonstationary Variant of Generalized Courier Problem with Interior Works
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
%D 2013
%P 88-107
%V 6
%N 2
%U http://geodesic.mathdoc.fr/item/VYURU_2013_6_2_a6/
%G ru
%F VYURU_2013_6_2_a6
A. G. Chentsov; P. A. Chentsov. On the Nonstationary Variant of Generalized Courier Problem with Interior Works. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 6 (2013) no. 2, pp. 88-107. http://geodesic.mathdoc.fr/item/VYURU_2013_6_2_a6/

[1] Chentsov A. A., Chentsov A. G., Chentsov P. A., “Extreme Routing Problem with Internal Losses”, Trudy Instituta matematiki i mehaniki UrO RAN, 14, no. 3, 2008, 183–201

[2] Chentsov A. A., Chentsov A. G., Chentsov P. A., “An Extremal Constrained Routing Problem with Internal Losses”, Russian Mathematics (Izvestiya VUZ. Matematika), 54:6 (2010), 54–68 | DOI | MR | Zbl

[3] Chentsov A. G., “Dynamic Programming Method in the Extreme Routing Problems with Constraints”, Journal of Computer and Systems Sciences International, 2010, no. 3, 52–66 | MR | Zbl

[4] Chentsov A. G., Extreme Problems Routing and Assignment of Tasks: Theory, M.–Izhevsk, 2008, 240 pp.

[5] Tonkov L. V., Chentsov A. G., “On the Question of the Optimal Choice Route in Temporary Discount”, Cybernetics and Systems Analysis, 1999, no. 1, 95–106 | MR | Zbl

[6] Kuratovskij K., Mostovskij A., Set Theory, Mir, M., 1970, 416 pp. | MR

[7] Cormen T. H., Leiserson C. E., Rivest R. L., Stein C., Introduction to Algorithms, MIT Press, 2009, 1312 pp. | MR | Zbl

[8] Garey M. R., Johnson D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman CO, N. Y., 1979, 416 pp. | MR | MR | Zbl

[9] Melamed I. I., Sergeev S. I., Sigal I. H., “The Traveling Salesman Problem. Problems in the Theory”, Automation and Remote Control, 1989, no. 9, 3–34 | MR

[10] Melamed I. I., Sergeev S. I., Sigal I. H., “The Traveling Salesman Problem. The Exact Algorithm”, Automation and Remote Control, 1989, no. 10, 3–29 | MR | Zbl

[11] Melamed I. I., Sergeev S. I., Sigal I. H., “The Traveling Salesman Problem. Approximate Algorithms”, Automation and Remote Control, 1989, no. 11, 3–26 | MR | Zbl

[12] Litl Dzh., Murti K., Suini D., Kjerel K., “Algorithms for Solving the Traveling Salesman Problem”, Economics and Mathematical Methods, 1 (1965), 94–107

[13] Bellman R., “The Application of Dynamic Programming Problem to the Traveling Salesman”, Kiberneticheskij sbornik, 9, Mir, M., 1964, 219–228 | MR

[14] Held M., Karp R. M., “The Use of Dynamic Programming to the Problem of Ordering”, Kiberneticheskij sbornik, 9, Mir, M., 1964, 202–218

[15] G. Laporte, Y. Nobert, “Generalized Travelling Salesman Problem Through n-Sets of Nodes: an Integer Programming Approach”, INFOR, 21:1 (1983), 61–75 | MR | Zbl

[16] A. L. Henry-Labordere, “The Record-Balancing Problem: a Dynamic Programming Solution of a Generalized Travelling Salesman Problem”, Rev. Franc. Inform. Rech., 3:2 (1969), 43–49 | Zbl

[17] Lejten A. K., “Some Modifications of the Traveling Salesman Problem”, Tr. VC Tart. un-ta, 28, 1973, 44–58 | MR

[18] Korotaeva L. N., Sesekin A. N., Chentsov A. G., “A Modification of the Dynamic Programming Method in the Problem of Sequential Approach”, Computational Mathematics and Mathematical Physics, 29:8 (1989), 1107–1113 | MR | Zbl

[19] Chentsov A. A., Chentsov A. G., “The Solution of the Route Optimization by Dynamic Programming”, Automation and Remote Control, 1998, no. 9, 117–129 | MR | Zbl

[20] Chentsov A. G., Chentsov P. A., “Routing to the Terms of Precedence (Task Courier): Dynamic Programming Method”, Herald of UGTU-UPI, 2004, no. 15 (45), At the Frontiers of Science and Engineering. Ch. 1, 148–152

[21] Chentsov A. A., Chentsov A. G., “On the Implementation of the Dynamic Programming Method in the Generalized Problem of Courier”, Trudy Instituta matematiki i mehaniki UrO RAN, 13, no. 3, 2007, 136–160

[22] Tashlykov O. L., Sesekin A. N., Scheklein S. E., Chentsov A. G., “Development of Optimum Algorithms for Decommissioning of Nuclear Power Plants with Using of Mathematical Modelling”, Izvestiya VUZ. Nuclear Power Engineering, 2009, no. 2, 115–120

[23] Tashlykov O. L., Sesekin A. N., Scheklein S. E., Balushkin F. A., Chentsov A. G., Homjakov A. P., “The Mathematical Modelling Techniques in Solving the Problem of Reducing Personnel Exposure”, Radiation Safety, 2009, no. 4, 39–49

[24] Sesekin A. N., Tashlykov O. L., Scheklein S. E., Kuklin M. Ju., Chentsov A. G., Kadnikov A. A., “The Use of Dynamic Programming to Optimize the Path of the Radiation Workers in Hazardous Areas in Order to Optimize Exposure”, Izvestiya VUZ. Nuclear Power Engineering, 2006, no. 2, 41–48

[25] Sesekin A. N., Chentsov A. A., Chentsov A. G., Problem of Routing Movements, Lan', St. Petersburg, 2011, 240 pp. | Zbl

[26] Tashlykov O. L., Organization and Technology of Nuclear Energy, UGTU-UPI, Ekaterinburg, 2005, 148 pp.