phone +7 (3412) 91 60 92
mail imi@udsu.ru
ru-RU Russian
Home » Issues » Archive of Issues » 2016 - 4 issue » pp. 565-578

Archive of Issues

Russia Yekaterinburg
Year
2016
Volume
26
Issue
4
Pages
565-578
<<
>>
Section Mathematics
Title The Bellmann insertions in route problems with constraints and complicated cost functions. II
Author(-s) Chentsov A.G.ab
Affiliations Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciencesa, Ural Federal Universityb
Abstract The route problem with precedence conditions and cost functions depending on the jobs list is considered; these singularities correspond to engineering applications. In particular, the above-mentioned singularities exist in statements of some problems arising in nuclear energetics and in machines with numerical control. Problems involved in sequentially circuiting megalopolises and in carrying out some (interior) work during these circuits are investigated. A procedure for local improvement of heuristic solutions for problems of perceptible dimension is proposed; this procedure exploits insertions on the dynamic programming base. Dynamic programming is realized in the form of a variant that does not provide for construction of a “full” array of values of the Bellman function. The search for localization of an insertion involves restricting to the variant of the Bellman procedure that realizes the extremum of the (local) criterion without constructing a corresponding solution in the form of a route-track pair. A more complete and more cost-intensive (in the sense of memory resources) procedure including determination of the above-mentioned (local optimal) solution is planned after the choice of the insertion localization.
Keywords insertion, dynamic programming, route
UDC 519.6
MSC 28A33
DOI 10.20537/vm160410
Received 15 October 2016
Language Russian
Citation Chentsov A.G. The Bellmann insertions in route problems with constraints and complicated cost functions. II, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2016, vol. 26, issue 4, pp. 565-578.
References
  1. Chentsov A.G. The Bellmann insertions in the route problem with constraints and complicated cost functions, Vestn. Udmurt. Univ. Mat. Mekh. Komp'yut. Nauki, 2014, issue 4, pp. 122-141 (in Russian). DOI: 10.20537/vm140410
  2. Chentsov A.A., Chentsov A.G. The problem of megalopolises consistent detouring, Vestn. Tambov. Univ. Ser. Estestv. Tekh. Nauki, 2014, vol. 19, no. 2, pp. 454-475 (in Russian).
  3. Petunin A.A., Chentsov A.G., Chentsov P.A. Local dynamic programming incuts in routing problems with restrictions, Vestn. Udmurt. Univ. Mat. Mekh. Komp'yut. Nauki, 2014, issue 2, pp. 56-75 (in Russian). DOI: 10.20537/vm140204
  4. Chentsov A.G. Ekstremal'nye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii (Extremal problems of routing and assignment of tasks: questions of theory), Moscow-Izhevsk: Regular and Chaotic Dynamics, Institute of Computer Science, 2008, 240 p.
  5. Bellman R. Application of dynamic programming method for the traveling salesman problem, Kibernet. Sb., Moscow: Mir, 1964, vol. 9, pp. 219-228 (in Russian).
  6. Kheld M., Karp R.M. Application of dynamic programming method for the sorting problems, Kibernet. Sb., Moscow: Mir, 1964, vol. 9, pp. 202-218 (in Russian).
  7. Chentsov A.G., Chentsov A.A. On the question of finding the value of routing problem with constraints, Journal of Automation and Information Sciences, 2016, vol. 48, no. 2, pp. 11-27. DOI: 10.1615/JAutomatInfScien.v48.i2.30
  8. Melamed I.I., Sergeev S.I., Sigal I.Kh. The traveling salesman problem. I: Theoretical issues, Automation and Remote Control, 1989, vol. 50, no. 9, pp. 1147-1173.
  9. Melamed I.I., Sergeev S.I., Sigal I.Kh. The traveling salesman's problem. Exact methods, Automation and Remote Control, 1989, vol. 50, no. 10, pp. 1303-1324.
  10. 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.
  11. Gutin G., Punnen A.P. The traveling salesman problem and its variations, Springer, 2002, 850 p.
  12. Cook W.J. In pursuit of the traveling salesman: Mathematics at the limits of Computation, Princeton University Press, 2012, xvi+228 p.
  13. Ivanko E.E. Ustoichivost' i neustoichivost' v diskretnykh zadachakh (Stability and instability in discrete problems), Yekaterinburg: Ural Branch of the Russian Academy of Sciences, 2013, 208 p.
  14. 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 (in Russian).
  15. Korobkin V.V., Sesekin A.N., Tashlykov O.L., Chentsov A.G. Metody marshrutizatsii i ikh prilozheniya v zadachakh povysheniya bezopasnosti i effektivnosti ekspluatatsii atomnykh stantsii (Routing methods and their applications in problems of improving the safety and efficiency of operation of nuclear power plants), Moscow: Novye tekhnologii, 2012, 234 p.
  16. 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. 2 (35), pp. 280-286 (in Russian).
  17. Frolovskii V.D. Automation of designing control programs for thermal cutting of metal by CNC equipment, Informatsionnye Tekhnologii v Proektirovanii i Proizvodstve, 2005, no. 4, pp. 63-66 (in Russian).
  18. Ganelina N.D., Frolovskii V.D. On constructing the shortest circuits on a set of line segments, Sib. Zh. Vychisl. Mat., 2006, vol. 9, no. 3, pp. 241-252 (in Russian).
  19. 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. Telecommunication and Control Systems, 2013, issue 2 (169), pp. 103-111 (in Russian).
  20. Verkhoturov M.A., Tarasenko P.Yu. The software for the problem of the cutting instrument route optimization based on chain cutting when a flat figure is cut, Vestnik UGATU, 2008, vol. 10, no. 2 (27), pp. 123-130 (in Russian).
  21. Wang G.G., Xie S.Q. Optimal process planning for a combined punch-and-laser cutting machine using ant colony optimization, International Journal of Production Research, 2005, vol. 43, issue 11, pp. 2195-2216. DOI: 10.1080/00207540500070376
  22. Lee M.K., Kwon K.B. Cutting path optimization in CNC cutting processes using a two-step genetic algorithm, International Journal of Production Research, 2006, vol. 44, issue 24, pp. 5307-5326. DOI: 10.1080/00207540600579615
  23. Ye J., Chen Z.G. An optimized algorithm of numerical cutting-path control in garment manufacturing, Advanced Materials Research, 2013, vol. 796, pp. 454-457. DOI: 10.4028/www.scientific.net/AMR.796.454
  24. Cormen T., Leiserson Ch., Rivest R. Introduction to algorithms (1st ed.), MIT Press and McGraw-Hill, 1990. Translated under the title Algoritmy. Postroenie i analiz (The algorithms. Construction and analysis), Moscow: Moscow Center for Continuous Mathematical Education, 1999, 960 p.
  25. Kuratovskii K., Mostovskii A. Teoriya mnozhestv (Theory of sets), Moscow: Mir, 1970, 416 p.
  26. Dieudonne J. Osnovy sovremennogo analiza (Foundations of modern analysis), Moscow: Mir, 1964, 430 p.
  27. Chentsov A.G. Problem of successive megalopolis traversal with the precedence conditions, Automation and Remote Control, 2014, vol. 75, issue 4, pp. 728-744. DOI: 10.1134/S0005117914040122
  28. Chentsov A.A., Chentsov A.G., Chentsov P.A. Elements of dynamic programming in extremal routing problems, Automation and Remote Control, 2014, vol. 75, issue 3, pp. 537-550. DOI: 10.1134/S0005117914030102
  29. Chentsov A.G. To question of routing of works complexes, Vestn. Udmurt. Univ. Mat. Mekh. Komp'yut. Nauki, 2013, issue 1, pp. 59-82 (in Russian). DOI: 10.20537/vm130107
Full text
/doc/issues-2016/16-04-10.pdf
<< Previous article
Next article >>