Geodesic
Generalized model of courier with additional restrictions
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 9 (2016) no. 1, pp. 46-58 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Mathematical model of process of sequential choice of permutation variants and fulfilment of works complex with complication at the expense of the operations coupling on different time intervals and preceding conditions is constructed. Routization problem with constraints and costs functions depending on tasks list is considered. This formulation is oriented to the solving of engineering problems, which arised in nuclear engineering and mechanical engineering. In the first case, constraints depending on list of tasks which are not fulfilled at the current time and concerning of dismantling of the radiation equipment fragments are assumed. In the second case, constraints connected with guarantee of sheet rigidity under cutting of details on machines with numerical control are possible; in this case, the dependence from lists of fulfilled works arises. The method of solving is based on widely undestanding dynamic programming; method which is expounded on the functional level. In the presence of preceding conditions there is no need for construction of full array of the Bellman function values. For the concrete variant of the problem connected with sheets cutting by the machines with numerical programming control, the proposed (optimal) algorithm is realized on a personal computer; results of calculation experiment are proposed.
Keywords: route; trace; preceding conditions. 
@article{VYURU_2016_9_1_a3,
     author = {A. A. Chentsov and A. G. Chentsov},
     title = {Generalized model of courier with additional restrictions},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a, Matemati\v{c}eskoe modelirovanie i programmirovanie},
     pages = {46--58},
     year = {2016},
     volume = {9},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURU_2016_9_1_a3/}
}
TY  - JOUR
AU  - A. A. Chentsov
AU  - A. G. Chentsov
TI  - Generalized model of courier with additional restrictions
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
PY  - 2016
SP  - 46
EP  - 58
VL  - 9
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VYURU_2016_9_1_a3/
LA  - ru
ID  - VYURU_2016_9_1_a3
ER  - 
%0 Journal Article
%A A. A. Chentsov
%A A. G. Chentsov
%T Generalized model of courier with additional restrictions
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
%D 2016
%P 46-58
%V 9
%N 1
%U http://geodesic.mathdoc.fr/item/VYURU_2016_9_1_a3/
%G ru
%F VYURU_2016_9_1_a3
A. A. Chentsov; A. G. Chentsov. Generalized model of courier with additional restrictions. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 9 (2016) no. 1, pp. 46-58. http://geodesic.mathdoc.fr/item/VYURU_2016_9_1_a3/

[1] Melamed I. I., Sergeev S. I., Sigal I. Kh., “The Traveling Salesman Problem. Issues in the Theory”, Automation and Remote Control, 50:9 (1989), 1147–1173 | MR | Zbl

[2] Melamed I. I., Sergeev S. I., Sigal I. Kh., “The Traveling Salesman Pproblem. Exact Methods”, Automation and Remote Control, 50:10 (1989), 1303–1324 | MR | Zbl

[3] 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

[4] G. Gutin, A. P. Punnen, The Traveling Salesman Problem and Its Variations, Springer, Berlin, 2002 | MR

[5] Bellman R., “The Application of Dynamic Programming to the Problem of Traveling Salesman”, Kiberneticheskiy sbornik, 9 (1964), 219–228 (in Russian) | MR

[6] Kheld M., Karp R. M., “The Application of Dynamic Programming to Problems Ordering”, Kiberneticheskiy sbornik, 9 (1964), 202–218 (in Russian)

[7] 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)

[8] 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. Telecommunications and Control Systems, 2013, no. 2(169), 103–111 (in Russian)

[9] Petunin A. A., Chentsov A. G., Chentsov P. A., “About a Routing Problem of the Tool Motion on Sheet Cutting”, Modelling and Analysis of Information Systems, 2015, no. 2, 278–294 (in Russian) | MR

[10] Frolovskiy V. D., “Design Automation of Control Programs in the Thermal Cutting Equipment ChPU”, Informatsionnye tekhnologii v proektirovanii i proizvodstve, 2005, no. 4, 63–66 (in Russian)

[11] Korobkin V. V., Sesekin A. N., Tashlykov O. L., Chentsov A. G., Methods of Routing and Their Appendix in Problems of Increase of Efficiency and Safety of Operation of Nuclear Power Plants, Novye tekhnologii, M., 2012

[12] Kuratovskiy K., Mostovskiy A., The Theory of Sets, Mir, M., 1970 (in Russian) | MR

[13] Dieudonné J., Foundations of Modern Analysis, Academic Press, New York–London, 1960 | MR | Zbl

[14] Kormen T., Leyzerson Ch., Rivest R., Introduction to Algorithms, MTsNMO, M., 1999 (in Russian)

[15] Chentsov A. G., Extremal Problems of Routing and Distribution of Tasks: Questions of the Theory, RKhD, M.–Izhevsk, 2008 (in Russian)

[16] Chentsov A. G., “Problem of Successive Megalopolis Traversal with the Precedence Conditions”, Automation and Remote Control, 75:4 (2014), 728–744 | DOI | MR | Zbl

[17] Chentsov A. G., “To Question of Routing of Works Complexes”, Bulletin of Udmurt University. Mathematics. Mechanics. Computer Science, 2013, no. 1, 58–82 (in Russian) | MR

[18] 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

[19] Chentsov A. G., “A Parallel Procedure of Constructing Bellman Function in the Generalized Courier Problem with Interior Works”, Bulletin of the South Ural State University. Series: Mathematical Modelling, Programming and Computer Software, 2012, no. 3, 44–52 (in Russian)