Section
|
Mathematics
|
Title
|
To question of routing of works complexes
|
Author(-s)
|
Chentsov A.G.a
|
Affiliations
|
Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciencesa
|
Abstract
|
The complicated variant of the problem of sequential megalopolis circuit with constraints in the form of preceding conditions is considered. The additional constraints on the junction character for fragments of exterior permutations and interior works (with respect to megalopolis) are imposed upon. It is supposed that costs of exterior permutations and interior works depend on the task list explicitly. The procedure of the dynamic programming type and (on their base) algorithm on the functional level are constructed.
|
Keywords
|
route, dynamic programming, preceding conditions
|
UDC
|
519.6
|
MSC
|
28A33
|
DOI
|
10.20537/vm130107
|
Received
|
11 February 2013
|
Language
|
Russian
|
Citation
|
Chentsov A.G. To question of routing of works complexes, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2013, issue 1, pp. 59-82.
|
References
|
- Melamed I.I., Sergeev S.I., Sigal I.Kh. The traveling salesman problem. Problems of the theory, Avtomatika i telemekhanika, 1989, no. 9, pp. 3–34.
- Melamed I.I., Sergeev S.I., Sigal I.Kh. The traveling salesman problem. Exact algorithms, Avtomatika i telemekhanika, 1989, no. 10, pp. 3–29.
- Melamed I.I., Sergeev S.I., Sigal I.Kh. The traveling salesman problem. Approximation algorithms, Avtomatika i telemekhanika, 1989, no. 11, pp. 3–26.
- Garey M., Johnson D. Computers and Intractability, 1979, 340 p. Translated under the title Vychislitel’nye mashiny i trudnoreshaemye zadachi, Moscow: Mir, 1982, 416 p.
- Little J., Murty K., Sweeney D., Karel C. An algorithm for the traveling salesman problem, Ekonom. Mat. Met., 1965, vol. 1, no. 1, pp. 90–107.
- Bellmann R. Application of dynamic programming to traveling salesman problem, Kibernet. Sb., Moscow: Mir, 1964, vol. 9, pp. 219–228.
- Kheld M., Karp R.M. Application of dynamic programming to the problem of ordering, Kibernet. Sb., Moscow: Mir, 1964, vol. 9, pp. 202–218.
- Tashlykov O.L. Remont oborudovaniya atomnykh stantsii (Repair of equipment of nuclear power plants), Yekaterinburg: USTU–UPI, 2003, 320 p.
- Tashlykov O.L., Sesekin A.N., Shcheklein S.E., Chentsov A.G. Development of optimal algorithms for decommissioning by using mathematical modeling, Izv. Vyssh. Uchebn. Zaved. Yadern. Energ. 2009, no. 2, pp. 115–120.
- Chentsov A.A., Chentsov A.G., Chentsov P.A. An extremal constrained routing problem with internal losses, Russian Mathematics (Iz. VUZ), 2010, vol. 54, no. 6, pp. 54–68.
- Chentsov A.G. Ekstremal’nye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii (Extremal problems of routing and assignment of tasks: questions of theory), Izhevsk: Institute of Computer Science, 2008, 240 p.
- Sesekin A.N., Chentsov A.A., Chentsov A.G. Generalized problem with the courier cost function that depends on the job list, Izv. Ross. Akad. Nauk Teor. Sist. Upr., 2010, no. 2, pp. 68–77.
- Chentsov A.G. Dynamic programming method in extremal constrained routing problems, Izv. Ross. Akad. Nauk Teor. Sist. Upr., 2010, no. 3, pp. 52–66.
- Chentsov A.A., Chentsov A.G. On a routing problem with the inner workings, Tr. Inst. Mat. Mekh. Ural. Otd. Ross. Akad. Nauk, 2012, vol. 18, no. 1, pp. 298–317.
- Chentsov A.A., Chentsov A.G. About one of the iterative procedure for solving the routing problem with restriction, Tr. Inst. Mat. Mekh. Ural. Otd. Ross. Akad. Nauk, 2012, vol. 18, no. 3, pp. 261–281.
- Chentsov A.G., Chentsov P.A. Dynamic programming in a nonstationary route problem, Izv. Inst. Mat. Inform. Udmurt. Gos. Univ., 2012, no. 1 (39), pp. 151–154.
- Chentsov A.G., Chentsov P.A. Routing movement restrictions and time-dependent cost functions, Nauch. Tekhn. Vedom. SPb Gos. Politekh. Univ. Inform. Telekom. Upr., St. Petersburg, 2012, no. 4, pp. 88–93.
- Chentsov A.G., Chentsov P.A. On a time-dependent routing problem with restrictions, Model. Anal. Inf. Sist., Yaroslavl’, 2012, vol. 19, no. 4, pp. 5–24.
- Chentsov A.A. Chentsov A.G., Chentsov P.A. Dynamic programming in extreme routing problems: general theory and elements of parallel structure, Parallel Computations and Control Problems: Abstracts of Int. Conf., Moscow, 2012, vol. 2, pp. 183–198
- Kuratovskii K., Mostovskii A. Teoriya mnozhestv (Theory of sets), Moscow: Mir, 1970, 416 p.
- Dieudonne J. Osnovy sovremennogo analiza (Foundations of modern analysis), Мoscow: Mir, 1964, 430 p.
- Warga J. Optimal’noe upravlenie differentsial’nymi i funktsional’nymi uravneniyami (Optimal control of differential and functional equations), Moscow: Nauka, 1977, 624 p.
- Kormen A., Leizerson Ch., Rivest R. Algoritmy. Postroenie i analiz (The algorithms. Construction and analysis), Moscow: Moscow Center for Continuous Mathematical Education, 1990, 960 p.
- Chentsov A.G. One parallel procedure for the construction of the Bellman function in the generalized problem of the courier with the inner workings, Vestn. Yuzhno-Ural. Gos. Univ., Ser. Mat. Model. Program., 2012, no. 12, pp. 53–76.
- Chentsov A.G. One parallel procedure for the construction of the Bellman function in the generalized problem of the courier with the inner workings, Avtomatika i telemekhanika, 2012, no. 3, pp. 134–149.
|
Full text
|
|