Elements of dynamic programming in local improvement constructions for heuristic solutions of routing problems with constraints / Petunin A.A., Chentsov A.A., Chentsov A.G., Chentsov P.A. // Automation and Remote Control. - 2017. - V. 78, l. 4. - P. 666-681.

ISSN:
00051179
Type:
Article
Abstract:
We consider methods for solving routing problems with precedence constraints that use iterative modes based on Bellman insertions while recomputing precedence constraints of the original problem; we assume that the dimension of the latter is sufficiently large, which does not let us, due to complexity of computations, immediately apply dynamic programming in the “global” version. © 2017, Pleiades Publishing, Ltd.
Author keywords:
dynamic programming; precedence constraints; route
Index keywords:
Iterative methods; Problem solving; Heuristic solutions; Precedence constraints; Re-computing; route; Routing problems; Dynamic programming
DOI:
10.1134/S0005117917040087
Смотреть в Scopus:
https://www.scopus.com/inward/record.uri?eid=2-s2.0-85017475080&doi=10.1134%2fS0005117917040087&partnerID=40&md5=be9e60731e8eb6ac86c94539cdc7af17
Соавторы в МНС:
Другие поля
Поле Значение
Link https://www.scopus.com/inward/record.uri?eid=2-s2.0-85017475080&doi=10.1134%2fS0005117917040087&partnerID=40&md5=be9e60731e8eb6ac86c94539cdc7af17
Affiliations Ural Federal University, Yekaterinburg, Russian Federation; Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Yekaterinburg, Russian Federation
Author Keywords dynamic programming; precedence constraints; route
References Melamed, I.I., Sergeev, S.I., Sigal, I.K., The Traveling Salesman Problem. Issues in Theory (1989) Autom. Remote Control, 50 (9), pp. 1147-1173; Melamed, I.I., Sergeev, S.I., Sigal, I.K., The Traveling Salesman’s Problem. Exact Methods (1989) Autom. Remote Control, 50 (10), pp. 1303-1324; Melamed, I.I., Sergeev, S.I., Sigal, I.K., The Traveling Salesman Problem. Approximate Algorithms (1989) Autom. Remote Control, 50 (11), pp. 1459-1479; Petunin, A.A., On Some Strategies for Constructing the Tool’s Route in the Development of Controlling Programs for Thermal Cutting Machines (2009) Vestn. UGATU, Ser. Upravlen., Vychisl. Tekh. Informatika, 13 (2), pp. 280-286; Petunin, A.A., Chentsov, A.G., Chentsov, P.A., On Routing the Movement of the Tool in Sheet Cutting Machines with Digital Program Control (2013) Nauch.-Tekhn. Vedomosti SPbGPU, Ser. Informatika. Telekommunikatsii. Upravlen., 2, pp. 103-111; Chentsov, A.G., (2008) Ekstremal’nye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii; Chentsov, A.G., Dynamic Programming in Extremal Problems of Routing with Constraints (2010) Izv. Ross. Akad. Nauk, Teor. Sist. Upravlen., 3, pp. 61-73; Chentsov, A.G., On Routing Complexes of Jobs (2013) Vestn. UdGU, Mat. Mekh. Komp’yut. Igry, 1, pp. 58-82; Chentsov, A.G., Chentsov, A.A., Dynamic Programming in Routing Problem with Constraints and Costs Depending on the List of Tasks (2013) Dokl. Akad. Nauk, 453 (1), pp. 20-23; Litl, D., Murti, K., Suini, D., Kerel, K., Algorithm for the Traveling Salesman Problem (1965) Ekon. Mat. Metod., 1 (1), pp. 94-107; Gutin, G., Punnen, A., (2002) The Traveling Salesman Problem and Its Variations, , Springer, Berlin; Escudero, L., An Inexact Algorithm for the Sequential Ordering Problem (1988) Eur. J. Oper. Res., 37 (2), pp. 236-249; Sigal, I.K., The Decomposition Approach to Solving Traveling Salesman Problem in High Dimensions and Some of Its Applications (1990) Izv. Akad. Nauk SSSR, Tekhn. Kibern., 6, pp. 143-155; Frolovskii, V.D., Automating the Design of Controlling Programs for Heat Metal Cutting on Equipment with Digital Program Control (2005) Inform. Tekhnol. Proektirovan. Proizvod., 4, pp. 63-66; Chentsov, A.G., Problem of Successive Megalopolis Traversal with the Precedence Conditions (2014) Autom. Remote Control, 75 (4), pp. 728-744; Chentsov, A.G., On a Parallel Procedure for Constructing the Bellman Function in the Generalized Problem of Courier with Internal Jobs (2012) Autom. Remote Control, 73 (3), pp. 532-546; Kuratowski, K., Mostowski, A., (1970) Set Theory, , North-Holland, Amsterdam; Kormen, T., Leizerson, C., Rivest, R., (1990) Algoritmy: Postroenie and Analiz, , MTsNMO, Moscow; Chentsov, A.A., Chentsov, A.G., The Problem of Sequential Megalopolis Traversal (2014) Vest. Tambov. Univ., Ser. Estestvenn. Tekh. Nauki, 5 (2), pp. 454-475; Petunin, A.A., Chentsov, A.G., Chentsov, P.A., Local Insertions Based on Dynamic Programming in the Routing Problem with Constraints (2014) Vestn. UdGU, Mat. Mekh. Komp’yut. Igry, 2, pp. 56-75; Chentsov, A.A., Chentsov, A.G., Chentsov, P.A., Method of Iterations in the Routing Problem with Internal Losses (2009) Tr. Inst. Mat. Mekh. UrO RAN, 15 (4), pp. 270-289
Correspondence Address Petunin, A.A.; Ural Federal UniversityRussian Federation; email: aapetunin@gmail.com
Publisher Maik Nauka Publishing / Springer SBM
Language of Original Document English
Abbreviated Source Title Autom. Remote Control
Source Scopus