phone +7 (3412) 91 60 92

Archive of Issues


Russia Yekaterinburg
Year
2013
Issue
1
Pages
59-82
<<
>>
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
  1. 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.
  2. Melamed I.I., Sergeev S.I., Sigal I.Kh. The traveling salesman problem. Exact algorithms, Avtomatika i telemekhanika, 1989, no. 10, pp. 3–29.
  3. Melamed I.I., Sergeev S.I., Sigal I.Kh. The traveling salesman problem. Approximation algorithms, Avtomatika i telemekhanika, 1989, no. 11, pp. 3–26.
  4. 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.
  5. 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.
  6. Bellmann R. Application of dynamic programming to traveling salesman problem, Kibernet. Sb., Moscow: Mir, 1964, vol. 9, pp. 219–228.
  7. Kheld M., Karp R.M. Application of dynamic programming to the problem of ordering, Kibernet. Sb., Moscow: Mir, 1964, vol. 9, pp. 202–218.
  8. Tashlykov O.L. Remont oborudovaniya atomnykh stantsii (Repair of equipment of nuclear power plants), Yekaterinburg: USTU–UPI, 2003, 320 p.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. Chentsov A.G. Dynamic programming method in extremal constrained routing problems, Izv. Ross. Akad. Nauk Teor. Sist. Upr., 2010, no. 3, pp. 52–66.
  14. 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.
  15. 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.
  16. 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.
  17. 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.
  18. 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.
  19. 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
  20. Kuratovskii K., Mostovskii A. Teoriya mnozhestv (Theory of sets), Moscow: Mir, 1970, 416 p.
  21. Dieudonne J. Osnovy sovremennogo analiza (Foundations of modern analysis), Мoscow: Mir, 1964, 430 p.
  22. Warga J. Optimal’noe upravlenie differentsial’nymi i funktsional’nymi uravneniyami (Optimal control of differential and functional equations), Moscow: Nauka, 1977, 624 p.
  23. 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.
  24. 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.
  25. 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
<< Previous article
Next article >>