Optimizing the starting point in a precedence constrained routing problem with complicated travel cost functions

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

Ural mathematical journal, Tome 4 (2018) no. 2, pp. 43-55

Résumé

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.

Détail

Keywords: Dynamic programming, Sequencing, Precedence constraints, Parallel computation.
Mots-clés : Route

Bibliographie

[1] Melamed I.I., Sergeev S.I., Sigal I., “The traveling salesman problem. Issues in theory”, Autom. Remote Control, 50:9 (1989), 1147–1173 | MR | Zbl

[2] Melamed I.I., Sergeev S.I., Sigal I., “The traveling salesman problem. Exact methods”, Autom. Remote Control, 50:10 (1989), 1303–1324 | MR | Zbl

[3] Melamed I.I., Sergeev S.I., Sigal I., “The traveling salesman problem. Approximate algorithms”, Autom. Remote Control, 50:11 (1989), 1459–1479 | MR | Zbl

[4] Gutin G., Punnen A.P., “The Traveling Salesman Problem and Its Variations”, New York: Springer, 2002 | DOI | MR

[5] Cook W.J., In Pursuit of the Traveling Salesman. Mathematics at the Limits of Computation, Princeton University Press, New Jersey, 2012, 248 pp. | MR | Zbl

[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 | DOI | MR | Zbl

[8] Chentsov A.G., Chentsov A.A., “A discrete-continuous routing problem with precedence conditions”, Proc. Steklov Inst. Math., 300:1 (2018), 56–71 | DOI | MR

[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.) | DOI | MR

[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 | DOI | MR | Zbl

[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 | DOI

[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 | DOI | MR

[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. | MR | Zbl

[15] Dieudonné J., Foundations of Modern Analysis, Academic Press, New York, 1969, 407 pp. | MR | Zbl

[16] Chentsov A.G., Chentsov P.A., “Routing under constraints: Problem of visit to megalopolises”, Autom. Remote Control, 77:11 (2016), 1957–1974 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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.) | MR | Zbl

[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 | DOI | MR | Zbl

[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.) | DOI | MR | Zbl

[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.) | DOI | MR | Zbl

[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.) | DOI

[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 | DOI

[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 | DOI | Zbl

[26] Jing Y., Zhige C., “An optimized algorithm of numerical cutting-path control in garment manufacturing”, Adv. Mater. Res., 796 (2013), 454–457 | DOI

[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

[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.) | DOI

[29] Bellman R., “Dynamic programming treatment of the travelling salesman problem”, J. ACM, 9:1 (1962), 61–63 | DOI | MR | Zbl

[30] Held M., Karp R.M., “A dynamic programming approach to sequencing problems”, J. Soc. Ind. Appl. Math., 1962, no. 10(1), 196–210 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR