phone +7 (3412) 91 60 92
mail imi@udsu.ru
ru-RU Russian
Home » Issues » Archive of Issues » 2014 - 2 issue » pp. 56-75

Archive of Issues

Russia Yekaterinburg
Year
2014
Issue
2
Pages
56-75
<<
>>
Section Mathematics
Title Local dynamic programming incuts in routing problems with restrictions
Author(-s) Petunin A.A.a, Chentsov A.G.ab, Chentsov P.A.ab
Affiliations Ural Federal Universitya, Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciencesb
Abstract The article is concerned with the procedure of insertion of optimizable fragments of route solutions into the global solutions of the “big’’ problem defined by heuristic algorithms. Setting of the route problem takes into account some singularities of the engineering problem about the sequential cutting of details each having one exterior and probably several interior contours. The latter ones must be subjected to cutting previously in comparison with the exterior contour, which leads to a great number of given preceding conditions. These conditions are actively used to decrease the computational complexity. Nevertheless, the problem dimensionality remains sufficiently large that does not permit to use “global’’ dynamic programming and forces heuristic algorithms to be used (the problem under investigation is a hard-solvable problem in the traditional sense). Therefore, it is interesting to develop the methods for correction of solutions based on the above-mentioned algorithms. In the present investigation, such correction is realized by the replacement of fragments (of the above-mentioned solutions) having a moderate dimensionality by optimal “blocks’’ constructed by dynamic programming with local preceding conditions which are compatible with the constraints of the initial “big’’ problem. The proposed replacement does not deteriorate, but, in typical cases, improves the quality of the initial heuristic solution. This is verified by the computing experiment on multi-core computer. The proposed algorithm is realized in the iterated regime: the solution (in the form of “route-trace’’) obtained after the first insertion on the basis of dynamic programming is taken as an initial solution for which the insertion is constructed again. In addition, the beginning of the new insertion is chosen randomly in the bounds defined by the possibilities of formation of a sliding “window’’ of the appreciable dimensionality which is in fact sufficient for the employment of the economical version of dynamic programming. Further, the procedure is repeated. The operation of the iterated algorithm is illustrated by solution of model problems including the versions with sufficiently dense “packing’’ of parts on a sheet, which is typical for the engineering production.
Keywords routing problem, preceding conditions
UDC 519.6
MSC 93CXX, 93С15
DOI 10.20537/vm140204
Received 1 March 2014
Language Russian
Citation Petunin A.A., Chentsov A.G., Chentsov P.A. Local dynamic programming incuts in routing problems with restrictions, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2014, issue 2, pp. 56-75.
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 (in Russian).
  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 (in Russian).
  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 (in Russian).
  4. 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).
  5. Petunin A.A., Chentsov A.G., Chentsov P.A. To the question about instrument routing in the automated machines of sheet cutting, Nauch. Tekhn. Vedom. SPb Gos. Politekh. Univ. Inform. Telekom. Upr., St. Petersburg, 2013, issue 2 (169), pp. 103-111 (in Russian).
  6. 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: Institute of Computer Science, 2008, 240 p.
  7. Kuratowski K., Mostowski A. Teoriya mnozhestv (Theory of sets), Moscow: Mir, 1970, 416 p.
  8. Dieudonne J. Osnovy sovremennogo analiza (Foundations of modern analysis), Мoscow: Mir, 1964, 430 p.
  9. Warga J. Optimal'noe upravlenie differentsial'nymi i funktsional'nymi uravneniyami (Optimal control of differential and functional equations), Moscow: Nauka, 1977, 624 p.
  10. 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, 1990, 960 p.
  11. Chentsov A.G. To question of routing of works complexes, Vestn. Udmurt. Univ. Mat. Mekh. Komp'yut. Nauki, 2013, no. 1, pp. 59-82 (in Russian).
  12. Chentsov A.A., Chentsov A.G., Chentsov P.A. Iteration method in the routing problem with internal losses, Tr. Inst. Mat. Mekh. Ural. Otd. Ross. Akad. Nauk, 2009, vol. 15, no. 4, pp. 270-289 (in Russian).
  13. Ivanko E.E. Ustoichivost' i neustoichivost' v diskretnykh zadachakh (Stability and instability in discrete problems), Ekaterinburg: Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, 2013, 208 p.
  14. 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).
Full text
/doc/issues-2014/14-02-04.pdf
<< Previous article
Next article >>