On the Nonstationary Variant of Generalized Courier Problem with Interior Works

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.

Keywords

route, preceding conditions, dynamic programming.

References

1. Chentsov A.A., Chentsov A.G., Chentsov P.A. Extreme Routing Problem with Internal Losses [Ekstremal'naya zadacha marshrutizatsii s vnutrennimi poteryami]. Trudy Instituta matematiki i mehaniki UrO RAN, 2008, vol. 14, no. 3, pp. 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), 2010, vol. 54, no. 6, pp. 54-68.
3. Chentsov A.G. Dynamic Programming Method in the Extreme Routing Problems with Constraints [Metod dinamicheskogo programmirovaniya v ekstremal'nykh zadachakh marshrutizatsii s ogranicheniyami]. Izvestia Rossiiskoi Akademii Nauk. Teoriya i Systemy Upravleniya [Journal of Computer and Systems Sciences International], 2010, no. 3, pp. 52-66.
4. Chentsov A.G. Ekstremal'nye zadachi marshrutizatsii i raspredeleniya zadaniy: voprosy teorii [Extreme Problems Routing and Assignment of Tasks: Theory]. Moscow, Izhevsk, 2008. 240 p.
5. Tonkov L.V., Chentsov A.G. On the Question of the Optimal Choice Route in Temporary Discount [K voprosu optimal'nogo vybora marshruta v usloviyakh vremennogo diskontirovaniya]. Kibernetika i sistem. analiz [Cybernetics and Systems Analysis], 1999, no. 1, pp. 95-106.
6. Kuratovskij K., Mostovskij A. Teoriya mnozhestv [Set Theory]. Moscow, Mir, 1970. 416 p.
7. Cormen T.H., Leiserson C.E., Rivest R. L., Stein C. Introduction to Algorithms. MIT Press, 2009. 1312 p.
8. Garey M.R., Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. N.Y., W.H. Freeman & CO, 1979. 416 p.
9. Melamed I.I., Sergeev S.I., Sigal I.H. The Traveling Salesman Problem. Problems in the Theory [Zadacha kommivoyazhera. Voprosy teorii]. Avtomatika i telemekhanika [Automation and Remote Control], 1989, no. 9, pp. 3-34.
10. Melamed I.I., Sergeev S.I., Sigal I.H. The Traveling Salesman Problem. The Exact Algorithm [Zadacha kommivoyazhera. Tochnye algoritmy]. Avtomatika i telemekhanika [Automation and Remote Control], 1989, no. 10, pp. 3-29.
11. Melamed I.I., Sergeev S.I., Sigal I.H. The Traveling Salesman Problem. Approximate Algorithms [Zadacha kommivoyazhera. Priblizhennye algoritmy]. Avtomatika i telemekhanika [Automation and Remote Control], 1989, no. 11, pp. 3-26.
12. Litl Dzh., Murti K., Suini D., Kjerel K. Algorithms for Solving the Traveling Salesman Problem [Algoritmy dlya resheniya zadachi o kommivoyazhere]. Ekonomika i matematicheskie metody [Economics and Mathematical Methods], 1965, vol. 1, pp. 94-107.
13. Bellman R. The Application of Dynamic Programming Problem to the Traveling Salesman [Primenenie dinamicheskogo programmirovaniya k zadache o kommivoyazhere]. Kiberneticheskij sbornik, Moscow, Mir, 1964, vol. 9, pp. 219-228.
14. Held M., Karp R.M. The Use of Dynamic Programming to the Problem of Ordering [Primenenie dinamicheskogo programmirovaniya k zadacham uporyadocheniya]. Kiberneticheskij sbornik, Moscow, Mir, 1964, vol. 9, pp. 202-218.
15. Laporte G., Nobert Y. Generalized Travelling Salesman Problem Through n-Sets of Nodes: an Integer Programming Approach. INFOR, 1983, vol. 21, no. 1, pp. 61-75.
16. Henry-Labordere A.L. The Record-Balancing Problem: a Dynamic Programming Solution of a Generalized Travelling Salesman Problem. Rev. Franc. Inform. Rech., 1969, vol. 3, no. 2, pp. 43-49.
17. Lejten A.K. Some Modifications of the Traveling Salesman Problem [Nekotorye modifikatsii zadachi kommivoyazhera]. Tr. VC Tart. un-ta, 1973, issue 28, pp. 44-58.
18. Korotaeva L.N., Sesekin A.N., Chentsov A.G. A Modification of the Dynamic Programming Method in the Problem of Sequential Approach [Ob odnoy modifikatsii metoda dinamicheskogo programmirovaniya v zadache posledovatel'nogo sblizheniya]. Zhurn. vychisl. matematiki i mat. Fiziki [Computational Mathematics and Mathematical Physics], 1989, vol. 29, no. 8, pp. 1107-1113.
19. Chentsov A.A., Chentsov A.G. The Solution of the Route Optimization by Dynamic Programming [O reshenii zadachi marshrutnoy optimizatsii metodom dinamicheskogo programmirovaniya]. Avtomatika i telemekhanika [Automation and Remote Control], 1998, no. 9, pp. 117-129.
20. Chentsov A.G., Chentsov P.A. Routing to the Terms of Precedence (Task Courier): Dynamic Programming Method [Marshrutizatsiya s usloviyami predshestvovaniya (zadacha kur'era): metod dinamicheskogo programmirovaniya]. Vestnik UGTU-UPI. Na peredovyh rubezhah nauki i inzhenernogo tvorchestva [Herald of UGTU-UPI. At the Frontiers of Science and Engineering], 2004, Ch.1, no. 15 (45), pp. 148-152.
21. Chentsov A.A., Chentsov A.G. On the Implementation of the Dynamic Programming Method in the Generalized Problem of Courier [O realizatsii metoda dinamicheskogo programmirovaniya v obobshchennoy zadache kur'era]. Trudy Instituta matematiki i mehaniki UrO RAN, 2007, vol. 13, no. 3, pp. 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 [Razrabotka optimal'nykh algoritmov vyvoda AES iz ekspluatatsii s ispol'zovaniem metodov matematicheskogo modelirovaniya]. Izvestiya VUZ. Nuclear Power Engineering, 2009, no. 2, pp. 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 [Vozmozhnosti matematicheskikh metodov modelirovaniya v reshenii problemy snizheniya obluchaemosti personala]. Voprosy radiatsionnoy bezopasnosti [Radiation Safety], 2009, no. 4, pp. 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 [Ispol'zovanie metoda dinamicheskogo programmirovaniya dlya optimizatsii traektorii peremeshcheniya rabotnikov v radiatsionno opasnykh zonakh s tsel'yu minimizatsii oblucheniya]. Izvestiya VUZ. Nuclear Power Engineering, 2006, no. 2, pp. 41-48.
25. Sesekin A.N., Chentsov A.A., Chentsov A.G. Zadachi marshrutizatsii peremeshcheniy [Problem of Routing Movements]. St. Petersburg, Lan', 2011. 240 p.
26. Tashlykov O.L. Organizatsiya i tekhnologiya atomnoy energetiki [Organization and Technology of Nuclear Energy]. Ekaterinburg, UGTU-UPI, 2005. 148 p.