Routing problems: constraints and optimality / Chentsov A.G., Chentsov P.A., Petunin A.A., Sesekin A.N. // IFAC-PapersOnLine. - 2016. - V. 49, l. 12. - P. 640-644.

ISSN:
24058963
Type:
Article
Abstract:
We consider the issues of routing under constraints and formulate a mathematical problem of visiting megalopolises. The order of visits is subject to precedence constraints. In addition, the cost functions depend on the set of pending tasks. The quality criterion is a variety of the additive criterion. The problem is established within the dynamic programming framework, however, a heuristic is proposed and implemented to solve practical problems of large dimensionality. © 2016
Author keywords:
Index keywords:
Cost functions; Dynamic programming; Mathematical problems; Optimality; Practical problems; Precedence constraints; Programming framework; Quality criteria; Routing problems; Problem solving
DOI:
10.1016/j.ifacol.2016.07.756
Смотреть в Scopus:
https://www.scopus.com/inward/record.uri?eid=2-s2.0-84992343508&doi=10.1016%2fj.ifacol.2016.07.756&partnerID=40&md5=55e4ea9bf06f3dcaaa28b5150a67d79e
Соавторы в МНС:
Другие поля
Поле Значение
Link https://www.scopus.com/inward/record.uri?eid=2-s2.0-84992343508&doi=10.1016%2fj.ifacol.2016.07.756&partnerID=40&md5=55e4ea9bf06f3dcaaa28b5150a67d79e
Affiliations Ural Federal University, Russia. Institute of Mathematics and Mechanics UB RAS, Russian Federation; Ural Federal University, Russian Federation
References Ali Fuat Alkaya, Ekrem Duman Combining and solving sequence dependent traveling salesman and quadratic assignment problems in PCB assembly Discrete Applied Mathematics, 10 September 2015, Vol. 192, p. 2-16; Bellman, R., On a Routing Problem Quart. Appl. Math, 16, 1958, P.87-90; Chentsov, A.G., Ekstremal'nye zadachi marshrutizat-sii i raspredeleniya zadaniy: voprosy teorii. M.Izhevsk: NITs "Regulyarnaya i khaoticheskaya di-namika (2008) Izhevskiy institut komp'yuternykh issle-dovaniy, p. 240; Chentsov, A.A., Chentsov, A.G., Extremal Bottleneck Routing Problem with Constraints in the Form of Precedence Conditions (2008) Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 263 (2), pp. 23-36; Chentsov, A.G., Problem of successive megalopolis traversal with the precedence conditions (2014) Automation and Remote Control, April, 75 (4), pp. 728-744; Chentsov, A.A., Chentsov, A.G., Chentsov P.A. Elements of dynamic programming in extremal routing problems. Automation and Remote Control, Volume 75, Issue 3, March 2014, p. 537-550; Chentsov, A.A., Chentsov A.G. Zadacha posledovatel'nogo obhoda megapolisov. Vestn. Tambov. un-ta. Ser. Es-testv. i tehn. nauki, 2014, T. 19, vyp. 2, S.454-475; Chentsov, A.G., Salii Ya.V. A Model of ”Nonadditive” Routing Problem Where the Costs Depend on the Set of Pending Tasks. Bulletin SUSU MMCS, Mathematical Modelling Programming & Computer Software, 2015, vol.8, No. 1. p. 24-44; Dewil, R., Vansteenwegen, P., Cattrysse, D., Cutting Path Optimization using Tabu Search. Key Engineering Materials, 473, 2011. p. 739-748; Dewil, R., Vansteenwegen, P., Cattrysse, D., Construction heuristics for generating tool paths for laser cutters. International Journal of Production Research, Mar. 2014, p. 1-20; Frolovskij, V.D., (2005) Avtomatizacija proektirovanija upravl-jajushhih programm teplovoj rezki metalla na oboru-dovanii s ChPU Informacionnye tehnologii v proek-tirovanii i proizvodstve. N4. M, pp. 63-66; Gutin, G., Punnen, A., The Traveling Salesman Problem and Its Variations. Berlin: Springer, 2002, 850 p; Held, M., Karp R.M. A Dynamic Programming Approach to Sequencing Problems Journal of the Society for Industrial and Applied Mathematics, 1962, N10 (1), P. 196-210; Hoeft, J., Palekar U.S. Heuristics for the plate-cutting traveling salesman problem. IIE Transactions, 29, 1997, p. 719-731; V. Jorge Leon, Brett A.Peters Replanning and Analysis of Partial Setup Strategies in Printed Circuit Board Assembly Systems The International Journal of Flexible Manufacturing Systems, 1996, N8, p. 389-412; Melamed, I.I., Sergeev, S.I., Sigal, I.K., The traveling salesman problem (1989) Issues in theory Automation and Remote Control, 50 (9), pp. 1147-1173; Melamed, I.I., Sergeev, S.I., Sigal, I.K., The traveling salesman's problem (1989) Exact methods. Automation and Remote Control, 50 (10), pp. 1303-1324; Melamed, I.I., Sergeev, S.I., Sigal, I.K., The traveling salesman problem (1989) Approximate algorithms. Automation and Remote Control, 50 (11), pp. 1459-1479; Petunin, A.A., (2009) O nekotoryh strategijah formirovanija marshruta instrumenta pri razrabotke upravljajushhih programm dlja mashin termicheskoj rezki metalla. Vest-nik UGATU, pp. 280-286; Petunin, A.A., Chentsov, A.G., Chentsov, P.A., Local dynamic programming incuts in routing problems with restrictions (2014) Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, N2, pp. 56-75; Petunin, A.A., Modelling of Tool Path for the CNC Sheet Cutting Machines (2015) AIP Conference Proceedings. 41st International Conference Applications of Mathematics in Engineering and Economics (AMEE’15), , V.1690, p. 060002(1)-060002(7); Xie, S.Q., Optimal process planning for compound laser cutting and punch using Genetic Algorithms (2009) International Journal of Mechatronics and Manufacturing Systems, 2 (1-2), pp. 20-38; Yang, W.B., An Effective Algorithm for Tool-Path Airtime Optimization during Leather Cutting (2010) Advanced Materials Research, 102-104, pp. 373-377
Publisher Elsevier B.V.
Language of Original Document English
Abbreviated Source Title IFAC-PapersOnLine
Source Scopus