Optimizing the starting point in a precedence constrained routing problem with complicated travel cost functions. (English) Zbl 1448.90015

Chentsov, Alexander G.; Grigoriev, Alexey M.; Chentsov, Alexey A.

Ural Math. J. 4, No. 2, 43-55 (2018).

Summary: We study the optimization of the initial state, route (a permutation of indices), and track in an extremal problem connected with visiting a finite system of megalopolises subject to precedence constraints where the travel cost functions may depend on the set of (pending) tasks. This problem statement is exemplified by the task to dismantle a system of radiating elements in case of emergency, such as the Chernobyl or Fukushima nuclear disasters. We propose a solution based on a parallel algorithm, which was implemented on the Uran supercomputer. It consists of a two-stage procedure: stage one determines the value (extremum) function over the set of all possible initial states and finds its minimum and also the point where it is achieved. This point is viewed as a base of the optimal process, which is constructed at stage two. Thus, optimization of the starting point for the route through megalopolises, connected with conducting certain internal tasks there, is an important element of the solution. To this end, we employ the apparatus of the broadly understood dynamic programming with elements of parallel structure during the construction of Bellman function layers.

MSC:

90B06	Transportation, logistics and supply chain management
90B10	Deterministic network models in operations research
90C39	Dynamic programming

Keywords:

dynamic programming; route; sequencing; precedence constraints; parallel computation

References:

[1]	Melamed I.I., Sergeev S.I., Sigal I., “The traveling salesman problem. Issues in theory”, Autom. Remote Control, 50:9 (1989), 1147-1173 · Zbl 0705.90070
[2]	Melamed I.I., Sergeev S.I., Sigal I., “The traveling salesman problem. Exact methods”, Autom. Remote Control, 50:10 (1989), 1303-1324 · Zbl 0705.90071
[3]	Melamed I.I., Sergeev S.I., Sigal I., “The traveling salesman problem. Approximate algorithms”, Autom. Remote Control, 50:11 (1989), 1459-1479 · Zbl 0704.90095
[4]	Gutin G., Punnen A.P., “The Traveling Salesman Problem and Its Variations”, New York: Springer, 2002 · Zbl 0996.00026
[5]	Cook W.J., In Pursuit of the Traveling Salesman. Mathematics at the Limits of Computation, Princeton University Press, New Jersey, 2012, 248 pp. · Zbl 1236.00007
[6]	Gimadi E.Kh., Khachai M.Yu., Extremal Problems on Sets of Permutations, UMC UPI, Yekaterinburg, 2016, 220 pp. (in Russian.)
[7]	Chentsov A.G., Chentsov A.A., “Route problem with constraints depending on a list of tasks”, Doklady Mathematics, 92:3 (2015), 685-688 · Zbl 1334.90139
[8]	Chentsov A.G., Chentsov A.A., “A discrete-continuous routing problem with precedence conditions”, Proc. Steklov Inst. Math., 300:1 (2018), 56-71 · Zbl 1391.93120
[9]	Chentsov A.G., Grigoryev A.M., “Dynamic Programming Method in a Routing Problem: a Scheme of Independent Computations”, Mekhatronika, Avtomatizatsiya, Upravlenie, 17:12 (2016), 834—846 (in Russian.)
[10]	Chentsov A.G., Grigoryev A.M., “A scheme of independent calculations in a precedence constrained routing problem”, Lecture Notes in Computer Science, 9869, Intern. Conf. on Discrete Optimization and Operations Research (DOOR-2016) (2016), 121-135 · Zbl 1388.90016
[11]	Chentsov A.G., Grigoryev A.M., Chentsov A.A., “Decommissioning of nuclear facilities: minimum accumulated radiation dose routing problem”, CEUR-WS Proc., 1987, 8th Intern. Conf. on Optimization and Applications (OPTIMA-2017) (2017), 123-130
[12]	Chentsov A.G., Khachai M.Y., Khachai D.M., “An exact algorithm with linear complexity for a problem of visiting megalopolises”, Proc. Steklov Inst. Math., 295, Supp. 1 (2016), 38-46 · Zbl 1375.90247
[13]	Korobkin V.V., Sesekin A.N., Tashlykov O.L., Chentsov A.G., Methods of Routing with Application to the Problems of Safety Enhancement and Operational Effectiveness of Nuclear Power Plants, ed. I.A. Kalyaev, Novye Tekhnologii, Moscow, 2012 (in Russian.)
[14]	Kuratowski K., Mostowski A., Set Theory, North-Holland Publishing Company, Amsterdam, 1968, 417 pp. · Zbl 0165.01701
[15]	Dieudonné J., Foundations of Modern Analysis, Academic Press, New York, 1969, 407 pp. · Zbl 0176.00502
[16]	Chentsov A.G., Chentsov P.A., “Routing under constraints: Problem of visit to megalopolises”, Autom. Remote Control, 77:11 (2016), 1957-1974 · Zbl 1356.90153
[17]	Chentsov A.G., “On a parallel procedure for constructing the Bellman function in the generalized problem of courier with internal jobs”, Autom. Remote Control, 73:3 (2012), 532-546 · Zbl 1307.90192
[18]	Chentsov A.G., “A parallel procedure of constructing Bellman function in the generalized courier problem with interior works”, Vestnik YuUrGU. Ser. Mat. Model. Progr., 18 (2012), 53-76 (in Russian.) · Zbl 1413.90034
[19]	Chentsov A.A., Chentsov A.G., Chentsov P.A., “Elements of Dynamic Programming in the Extremal Problems of Routing”, Autom. Remote Control, 75:3 (2014), 537-550 · Zbl 1301.49065
[20]	Chentsov A.G., Chentsov A.A., “A model variant of the problem about radiation sources utilization (iterations based on optimization insertions”, Izv. Inst. Mat. Inform. Udmurt. Gos. Univ., 50 (2017), 83-109 (in Russian.) · Zbl 1418.90278
[21]	Chentsov A.G., Chentsov A.A., Grigoryev A.M., “On one routing problem modeling movement in radiation fields”, Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 27:4 (2017), 540-557 (in Russian.) · Zbl 1401.90251
[22]	Petunin A.A., “About some strategy of formation of a route of the cutting tool by development of the controlling programs for the thermal sheet cutting machines”, The UGATU Bulletin. Series: Control, ADP equipment and informatics, 13:2(35) (2009), 280-286 (in Russian.)
[23]	Frolovskii V.D., “Computer-aided design of the control programs for thermal metal cutting on NPC machines”, Informacionnye tekhnologii v proektirovanii i proizvodstve, 2005, no. 4, 63-66 (in Russian.)
[24]	Wang G.G., Xie S.Q., “Optimal process planning for a combined punch-and-laser cutting machine using ant colony optimization”, Int. J. Product. Res., 43:11 (2005), 2195-2216
[25]	Lee M.K., Kwon K.B., “Cutting path optimization in NC cutting processes using a two-step genetic algorithm”, Int. J. Product. Res., 44:24 (2006), 5307-5326 · Zbl 1128.90584
[26]	Jing Y., Zhige C., “An optimized algorithm of numerical cutting-path control in garment manufacturing”, Adv. Mater. Res., 796 (2013), 454-457
[27]	Ganelina N.D., Frolovskii V.D., “On constructing the shortest circuits on a set ofline segments”, Siberian J. of Numer. Mathematics, 9:3 (2006), 241—252 · Zbl 1212.93170
[28]	Verkhoturov M.A., Tarasenko P.Yu., “Software for the problems of optmization of the cutting tool path for planar figure cutting on the basis of chain cutting”, The UGATU Bulletin. Series: Control, ADP equipment and informatics, 10:2(27) (2008), 123-130 (in Russian.)
[29]	Bellman R., “Dynamic programming treatment of the travelling salesman problem”, J. ACM, 9:1 (1962), 61-63 · Zbl 0106.14102
[30]	Held M., Karp R.M., “A dynamic programming approach to sequencing problems”, J. Soc. Ind. Appl. Math., 1962, no. 10(1), 196-210 · Zbl 0106.14103
[31]	Little J.D.C., Murti K.G., Sweeney D.W., Karel C., “Algorithm for the traveling salesman problem”, Econ. Mat. Metod., 1:1 (1965), 94-107
[32]	Escudero L., “An inexact algorithm for the sequential ordering problem”, Eur. J. Oper. Res., 37:2 (1988), 236-249 · Zbl 0653.90036
[33]	Chentsov A.G., Chentsov A.A., Chentsov P.A., “Extremal routing problem with internal losses”, Proc. Steklov Inst. Math., 264, Suppl. 1. (2009), 87-106 · Zbl 1312.90013