Article

Article title DYNAMIC PROGRAMMING AND HEURISTIC METHODS IN ROUTING PROBLEMS
Authors A. G. Chentsov, P. A. Chentsov
Section SECTION III. THE DESIGN AND APPLICATION OF ROBOTIC AND MECHATRONIC SYSTEMS
Month, Year 09, 2017 @en
Index UDC 519.6
DOI
Abstract The "additive" route problems with constraints and possible dependence of cost functions on tasks list are considered. Such settings are natural under investigation of engineering problems arising in nuclear power and mechanical engineering. In first case, decrease in dose rate for the worker of the nuclear power plant under dismantling radiation elements of equipment is discussed. In second case, procedures are connected with sheet cutting on machines with a numerical control. In article, an issue connected with employment of dynamic programming for solution of problems with constraints and above-mentioned dependence of cost functions from task list is considered. Procedures of testing and local improvements of heuristics are borne in mind. In both versions realized for sub-problems of moderate dimension apparatus of the widely understood dynamic programming is used. But, it is supposed that the above-mentioned sub-problems are complicated by the same conditions as in original “big” problem (constraints, cost functions with dependency on tasks list). For implementation of the “local” dynamic programming, the scheme with using of precedence constraints to reduce of the computational complexity is realized (precedence conditions are available practically in all variants of above-mentioned applied problems); wherein, the construction of total array of Bellman function is not required. For the accounting of emerging under performance of tasks dynamic constraints, special (threshold) cost functions with role of palpable penalties for violation of constraints are used. Results of computing experiment both for testing of above-mentioned heuristics and under solution of problems with palpable dimension are given. The article is based on a lecture one of authors in conference MKPU-10.

Download PDF

Keywords Routing problems; precedence conditions; metal cut optimization.
References 1. Little L.D.C., Murty K.G., Sweeney D.W., Karel C. An Algorithm for the Travelling Salesman Problem, Opns. Res., 1963, Vol. 11, No. 6, pp. 972-990.
2. William J. Cook. In pursuit of the traveling salesman. Mathematics at the limits of computation. NJ. Princeton Univer. Press., 2012, 248 p.
3. Gutin G., Punnen A. The Traveling Salesman Problem and Its Variations. Berlin: Springer, 2002, 850 p.
4. Melamed I.I., Sergeev S.I., Sigal I.Kh. Zadacha kommivoyazhera. Voprosy teorii [The traveling salesman problem. Questions of the theory], Avtomatika i telemekhanika [Automation and Remote Control], 1989, No. 9, pp. 3-34.
5. Melamed I.I., Sergeev S.I., Sigal I.Kh. Zadacha kommivoyazhera. Tochnye algoritmy [The traveling salesman problem. Exact algorithms], Avtomatika i telemekhanika [Automation and Remote Control], 1989, No. 10, pp. 3-29.
6. Melamed I.I., Sergeev S.I., Sigal I.Kh. Zadacha kommivoyazhera. Priblizhennye algoritmy [The traveling salesman problem. Approximate algorithms], Avtomatika i telemekhanika [Automation and Remote Control], 1989, No. 11, pp. 3-26.
7. Gimadi E.Kh., Khachay M.Yu. Ekstremal'nye zadachi na mnozhestvakh perestanovok [Extremal problems on sets of permutations]. Ekaterinburg: Izd-vo UMTs UPI, 2016, 220 p.
8. 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 stantsiy [Routing methods and their applications in enhancing the safety and efficiency of nuclear power plants operation]. Moscow: Izd-vo “Novye tekhnologii”, 2012, 234 p.
9. Petunin A.A. O nekotorykh strategiyakh formirovaniya marshruta instrumenta pri razrabotke upravlyayushchikh programm dlya mashin termicheskoy rezki materiala [Some strategies to make the route tool in the development of control programs for thermal cutting machines], Vestnik UGATU. Ser. Upravlenie, vychislitel'naya tekhnika i informatika [Vestnik USATU. Series. Control, computer engineering and computer science], 2009, Vol. 13, No. 2 (35),
pp. 280-286.
10. Frolovskiy V.D. Avtomatizatsiya proektirovaniya upravlyayushchikh programm teplovoy rezki metalla na oborudovanii s ChPU [Automatic design of control programs of thermal cutting on CNC equipment], Informatsionnye tekhnologii v proektirovanii i proizvodstve [Information technologies in designing and manufacturing], 2005, No. 4, pp. 63-66.
11. Verkhoturov M.A., Tarasenko P.Yu. Matematicheskoe obespechenie zadachi optimizatsii puti rezhushchego instrumenta pri ploskom figurnom raskroe na osnove tsepnoy rezki [Software for the optimization of the path of the cutting tool with a flat shape cutting based on chain cutting], Vestnik UGATU. Ser. Upravlenie, vychislitel'naya tekhnika i informatika [Vestnik USATU. Series. Control, computer engineering and computer science], 2008, Vol. 10, No. 2 (27), pp. 123-130.
12. Petunin A.A., Chentsov A.G., Chentsov P.A. K voprosu o marshrutizatsii dvizheniya instrumenta v mashinakh listovoy rezki s chislovym programmnym upravleniem [The question of the route of movement of the tool in the sheet cutting machines with numerical control], Nauch.-tekhn. vedomosti SPbGPU. Informatika. Telekommunikatsii. Upravlenie [St. Petersburg State Polytechnical University Journal. Computer Science. Telecommunication and Control Systems], 2013, No. 2 (169), pp. 103-111.
13. 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, Jun. 2005, Vol. 43 (11), pp. 2195-2216.
14. Lee M.-K., Kwon K.-B. Cutting path optimization in CNC cutting processes using a two-step genetic algorithm, Int. J. Product. Res. Dec., 2006, Vol. 44 (24), pp. 5307-5326.
15. Chentsov A.G., Chentsov P.A. Marshrutizatsiya v usloviyakh ogranicheniy: zadacha o poseshchenii megapolisov [Routing under constraints: the challenge about visiting cities], Avtomatika i telemekhanika [Automation and Remote Control], 2016, No. 11, pp. 96-117.
16. Chentsov A.G., Chentsov A.A. Diskretno-nepreryvnaya zadacha marshrutizatsii s usloviyami predshestvovaniya [Discrete-continuous routing problem with precedence conditions ], Tr. In-ta matematiki i mekhaniki [Proceedings of Institute of mathematics and mechanics], 2017,
Vol. 23, No. 1, pp. 275-292.
17. Chentsov A.G. Bellmanovskie vstavki v zadache marshrutizatsii s ogranicheniyami i s uslozhnennymi funktsiyami stoimosti [Belanovskii insertion in the routing problem with constraints and complicated cost functions], Vestnik UdGU. Matematika. Mekhanika. Komp'yuternye nauki [The Bulletin of Udmurt University. Mathematics Mechanics. Computer science], 2014, Issue 4, pp.122-141.
18. Chentsov A.G. Optimiziruyushchie vstavki v zadachakh marshrutizatsii i ikh realizatsiya na osnove dinamicheskogo programmirovaniya [Optimizing insertion in the routing problems and their implementation on the basis of dynamic programming], Vestnik UdGU. Matematika. Mekhanika. Komp'yuternye nauki [The Bulletin of Udmurt University. Mathematics Mechanics. Computer science], 2016, Vol. 26, No. 4, pp. 565-578.
19. Petunin A.A., Chentsov A.A., Chentsov A.G., Chentsov P.A. Elementy dinamicheskogo programmirovaniya v konstruktsiyakh lokal'nogo uluchsheniya evristicheskikh resheniy zadach marshrutizatsii s ogranicheniyami [Elements of dynamic programming in the construction of the local improvement heuristic solutions of the routing problems with constraints], Avtomatika i telemekhanika [Automation and Remote Control], 2017, Issue 4, pp. 106-125.
20. Chentsov A.A., Chentsov A.G. K voprosu o nakhozhdenii znacheniya marshrutnoy zadachi s ogranicheniyami [The question of finding the value route problem with constraints ], Problemy upravleniya i informatiki [Problems of control and Informatics], 2016, No. 1, pp. 41-54.
21. Chentsov A.A., Chentsov A.G. Zadacha posledovatel'nogo obkhoda megapolisov [The problem of sequential bypass of cities], Vestnik Tambovskogo universiteta. Ser.: Estestvennye i tekhnicheskie nauki [Tambov University Reports. Series Natural and Technical Sciences], 2014, Vol. 19, Issue 2, pp. 454-475.
22. Petunin A.A., Chentsov A.G., Chentsov P.A. Lokal'nye vstavki na osnove dinamicheskogo programmirovaniya v zadache marshrutizatsii s ogranicheniyami [Local insertion on the basis of dynamic programming in the routing problem with the restrictions], Vestnik UdGU. Matematika. Mekhanika. Komp'yuternye nauki [The Bulletin of Udmurt University. Mathematics Mechanics. Computer science], 2014, Issue 2, pp. 56-75.
23. Petunin A.A., Chentsov A.G., Chentsov P.A. K voprosu o marshrutizatsii peremeshcheniy pri listovoy rezke detaley [The question of the routing of movement under the leaf cutting parts], Vestnik YuUrGU. Ser. Matematicheskoe modelirovanie i programmirovanie [Bulletin of the South Ural State University. Series: Mathematical modeling and programming], 2017, Vol. 10, No. 3, pp. 25-39.
24. Chentsov A.G. Ekstremal'nye zadachi marshrutizatsii i raspredeleniya zadaniy: voprosy teorii [Extremal problems of routing and assignment of tasks: questions of theory]. Moscow.-Izhevsk: NITs «Regulyarnaya i khaoticheskaya dinamika», Izhevskiy institut komp'yuternykh issledovaniy, 2008, 240 p.
25. Lawler, Eugene L. Efficient implementation of dynamic programming algorithms for sequencing problems, Mathematical Centre. 1979.BW 106/79.
26. Hoeft J., Palekar U.S. Heuristics for the plate-cutting traveling salesman problem, IIE Transactions, 1997, Vol. 29 (9), pp. 719-731.
27. Bellman R. On a Routing Problem, Quart. Appl. Math., 1958, Vol. 16, pp. 87-90.
28. Held M., Karp R.M. A Dynamic Programming Approach to Sequencing problems, Journal of the Society for Industrial and Applied Mathematics, 1962, No. 10 (1), pp. 196-210.
29. Alkaya A.F., Duman E. Combining and solving sequence dependent travelling salesman and quadratic assignment problems in PCB assembly, Discrete Applied Mathematics, Vol. 192, pp. 2-16.

Comments are closed.