A Parallel Procedure of Constructing Bellman Function in the Generalized Courier Problem with Interior Works

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.

Keywords

route, megalopolis, 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 Mekhaniki UrO RAN, Yekaterinburg, 2008, vol.,14, no. 3, pp. 183-201.
2. Chentsov A.G. About the Optimal Routing with the Conditions of Constraints [Ob optimal'noi marshrutizatsii v usloviyakh ogranichenii]. Doklady Akademii nauk, 2008, vol.,423, no. 3, pp. 303-307.
3. Chentsov A.A., Chentsov A.G., Chentsov P.A. Extreme Movements of Routing Problem with Constraints and Internal Losses [Ekstremal'naya zadacha marshrutizatsii peremeshchenii s ogranicheniyami i vnutrennimi poteryami]. Izv. vysshikh uchebnykh zavedenii. Matematika, Kazan', 2010, no. 6, pp. 64-81.
4. Chentsov A.G. Dynamic Programming Method in Extremal Problems with Constraints Routing [Metod dinamicheskogo programmirovaniya v ekstremal'nikh zadachakh marshrutizatsii s ogranicheniyami]. Izv. RAN. Teoriya i sistemy upravleniya, 2010, no. 3, pp. 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 [Usloviya predshestvovaniya v odnoi zadache ekstremal'noi marshrutizatsii s vnutrennimi rabotami]. Algoritmy i programmnye sredstva parallel'nikh vichislenii, 2010, no. 10, pp. 60-76.
6. Chentsov A.G. Ekstremal'nye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii [Extremal Problems of Routing and Assignment of Tasks: Questions of Theory], Izhevsk: NITS <<Regular and Chaotic Dynamics>>, Izhevsk Institute of Computer Research, 2008, 240 p.
7. Melamed I.I., Sergeev S.I., Sigal I.Kh. Traveling Salesman Problem. Questions of Theory [Zadacha kommivoyazhera. Voprosy teorii]. Avtomatika i telemekhanika, 1989, no. 9, pp. 3-34.
8. Melamed I.I., Sergeev S.I., Sigal I.Kh. Traveling Salesman Problem. Precise Algorithms [Zadacha kommivoyazhera.Tochnye algoritmy]. Avtomatika i telemekhanika, 1989, no. 10, pp. 3-29.
9. Melamed I.I., Sergeev S.I., Sigal I.Kh. Traveling Salesman Problem. Approximate Algorithms [Zadacha kommivoyazhera. Priblizhennye algoritmy]. Avtomatika i telemekhanika, 1989, no. 11, pp. 3-26.
10. Geri M., Jonson D. Vychislitel'nye mashiny i trudnoreshaemye zadachi [Calculating Machines and Difficult Problems], Moscow: Mir, 1982. 416 p.
11. Bellman R. Use Dynamic Programming to the Problem of a Salesman [Primenenie dinamicheskogo programmirovaniya k zadache o kommivoyazhere]. Kiberneticheskii sbornik, Moscow, Mir, 1964, vol.,9, pp. 219-228.
12. Held M. Use Dynamic Programming to the Problems of Ordering [Primenenie dinamicheskogo programmirovaniya k zadacham uporyadocheniya]. Kiberneticheskii sbornik, Moscow, Mir, 1964, vol.,9, pp. 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 [Ispol'zovanie metoda dinamicheskogo programmirovaniya dlya optimizatsii traektorii peremeshcheniya rabotnikov v radiatsionno opasnykh zonakh s tsel'yu minimizatsii oblucheniya]. Izv. vysshikh uchebnykh zavedenii. Yadernaya energetika, 2006, no. 2, pp. 41-48.
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 [Razrabotka optimal'nykh algoritmov vyvoda AES iz ekspluatatsii s ispol'zovaniem metodov matematicheskogo modelirovaniya]. Izv. vysshikh uchebnykh zavedenii. Yadernaya energetika, 2009, no.2, pp. 115-120.
15. Kuratovskii K., Mostovskii A. Teoriya mnozhestv. [Set Theory]. Moscow, Mir, 1970. 416 p.
16. Kormen A., Leizerson Ch., Rivest R. Algoritmy. Postroenie i analiz [The Algorithms. Construction and Analysis]. Moscow, MTSNMO, 1990. 960 p.
17. Warga Dj. Optimal'noe upravlenie differentsial'nymi i functsional'nymi uravneniyami [Optimal Control of Differential and Functional Equations]. Moscow, Nauka, 1977. 624 p.
18. Krasovskii N.N. Teoriya upravleniya dvizheniem [Theory of traffic control]. Moscow, Nauka, 1968. 475 p.
19. Panasyuk A.I., Panasyuk V.I. Asimptoticheskaya magistral'naya optimizatsiya upravlyaemykh sistem [Asymptotic Optimization Trunk of Control Systems]. Minsk, Nauka i tekhnika, 1986. 296 p.