Volume 9, no. 1Pages 46 - 58

Generalized Model of Courier with Additional Restrictions

A.A. Chentsov, A.G. Chentsov
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.
Full text
route; trace; preceding conditions.
1. Melamed I.I., Sergeev S.I., Sigal I.Kh. The Traveling Salesman Problem. Issues in the Theory. Automation and Remote Control, 1989, vol. 50, no. 9, pp. 1147-1173.
2. Melamed I.I., Sergeev S.I., Sigal I.Kh. The Traveling Salesman Pproblem. Exact Methods. Automation and Remote Control, 1989, vol. 50, no. 10, part 1, pp. 1303-1324.
3. Melamed I.I., Sergeev S.I., Sigal I.Kh. The Traveling Salesman Problem. Approximate Algorithms. Automation and Remote Control, 1989, vol. 50, no. 11, pp. 1459-1479.
4. Gutin G., Punnen A.P. The Traveling Salesman Problem and Its Variations. Berlin, Springer, 2002.
5. Bellman R. [The Application of Dynamic Programming to the Problem of Traveling Salesman]. Kiberneticheskiy sbornik, 1964, no. 9, pp. 219-228. (in Russian)
6. Kheld M., Karp R.M. [The Application of Dynamic Programming to Problems Ordering]. Kiberneticheskiy sbornik, 1964, vol. 9, pp. 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, 2009, vol. 13, no. 35, pp. 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), pp. 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, pp. 278-294. (in Russian)
10. Frolovskiy V.D. [Design Automation of Control Programs in the Thermal Cutting Equipment ChPU]. Informatsionnye tekhnologii v proektirovanii i proizvodstve, 2005, no. 4, pp. 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. Moscow, Novye tekhnologii, 2012.
12. Kuratovskiy K., Mostovskiy A. Teoriya mnozhestv [The Theory of Sets]. Moscow, Mir, 1970. (in Russian)
13. Dieudonn'e J. Foundations of Modern Analysis. New York, London, Academic Press, 1960.
14. Kormen T., Leyzerson Ch., Rivest R. Algoritmy: postroenie i analiz [Introduction to Algorithms]. Moscow, MTsNMO, 1999. (in Russian)
15. Chentsov A.G. Ekstremal'nye zadachi marshrutizatsii i raspredeleniya zadaniy: voprosy teorii [Extremal Problems of Routing and Distribution of Tasks: Questions of the Theory]. Moscow, Izhevsk, RKhD, 2008. (in Russian)
16. Chentsov A.G. Problem of Successive Megalopolis Traversal with the Precedence Conditions. Automation and Remote Control, 2014, vol. 75, no. 4, pp. 728-744. DOI: 10.1134/S0005117914040122
17. Chentsov A.G. To Question of Routing of Works Complexes. Bulletin of Udmurt University. Mathematics. Mechanics. Computer Science, 2013, no. 1, pp. 58-82. (in Russian)
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, 2012, vol. 73, no. 3, pp. 532-546. DOI: 10.1134/S0005117912030113
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, pp. 44-52. (in Russian)