OPTIMIZING THE STARTING POINT IN A PRECEDENCE CONSTRAINED ROUTING PROBLEM WITH COMPLICATED TRAVEL COST FUNCTIONS
Abstract
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 xemplified 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.
Keywords
Full Text:
PDFReferences
Melamed I. I., Sergeev S. I., Sigal I. The traveling salesman problem. Issues in theory. Autom. Remote Control, 1989. Vol. 50, No. 9. P. 1147–1173.
Melamed I. I., Sergeev S. I., Sigal I. The traveling salesman problem. Exact methods. Autom. Remote Control, 1989. Vol. 50, No. 10. P. 1303–1324.
Melamed I. I., Sergeev S. I., Sigal I. The traveling salesman problem. Approximate algorithms. Autom. Remote Control, 1989. Vol. 50, No. 11. P. 1459–1479.
Gutin G., Punnen A.P. The Traveling Salesman Problem and its Variations. New York: Springer, 2002. DOI: 10.1007/b101971
Cook W. J. In Pursuit of the Traveling Salesman. Mathematics at the Limits of Computation. New Jersey: Princeton University Press, 2012. p. 248.
Gimadi E. Kh., Khachai M.Yu. Ekstremalnye zadachi na mnozhestvax perestanovok [Extremal Problems on Sets of Permutations], Yekaterinburg: UMC UPI, 2016. p. 220 (in Russian)
Chentsov A. G., Chentsov A. A. Route problem with constraints depending on a list of tasks. Doklady Mathematics, 2015. Vol. 92, No. 3. P. 685–688. DOI: 10.1134/S1064562415060083
Chentsov A. G., Chentsov A. A. A discrete-continuous routing problem with precedence conditions. Proc. Steklov Inst. Math. , 2018. Vol. 300, No. 1. P. 56–71. DOI: 10.1007/b101971
Chentsov A. G., Grigoryev A. M. Dynamic Programming Method in a Routing Problem: a Scheme of Independent Computations. Mekhatronika, Avtomatizatsiya, Upravlenie, 2016. Vol. 17, No. 12. P. 834–846. DOI: 10.17587/mau.17.834-846 (in Russian)
Chentsov A. G., Grigoryev A. M. A Scheme of Independent Calculations in a Precedence Constrained Routing Problem. Lecture Notes in Computer Science , Vol. 9869: Intern. Conf. on Discrete Optimization and Operations Research (DOOR–2016), 2016. P. 121–135. DOI: 10.1007/978-3-319-44914-2_10
Chentsov A. G., Grigoryev A. M., Chentsov A. A. Decommissioning of nuclear facilities: minimum accumulated radiation dose routing problem. CEUR-WS Proc., Vol.1987 : 8th Intern. Conf. on Optimization and Applications (OPTIMA–2017), 2017. P. 123–130. http://ceur-ws.org/Vol-1987/paper19.pdf
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. , 2016. Vol. 295, supp. 1. P. 38–46. DOI: 10.1134/S0081543816090054
Korobkin V. V., Sesekin A. N., Tashlykov O. L., and Chentsov A. G. Metody marshrutizacii i ih prilozheniya v zadachah povysheniya ehffektivnosti i bezopasnosti ehkspluatacii atomnyh stancij [Methods of Routing with Application to the Problems of Safety Enhancement and Operational Effectiveness of Nuclear Power Plants] Kalyaev, I.A., Ed., Moscow: Novye Tekhnologii, 2012. (in Russian)
Kuratowski K., Mostowski A. Set Theory. Amsterdam: North-Holland Publishing Company, 1968. p. 417.
Dieudonné J. Foundations of Modern Analysis. New York: Academic Press, 1969. 407 p.
Chentsov A. G., Chentsov P. A. Routing under constraints: Problem of visit to megalopolises. Autom. Remote Control, 2016. Vol. 77, No. 11. P. 1957–1974. DOI: 10.1134/S0005117916110060
Chentsov A. G. On a parallel procedure for constructing the Bellman function in the generalized problem of courier with internal jobs. Autom. Remote Control, 2012. Vol. 73, No. 3. P. 532–546. DOI: 10.1134/S0005117912030113
Chentsov A. G. A parallel procedure of constructing Bellman function in the generalized courier problem with interior works. Vestnik YuUrGU. Ser. Mat. Model. Progr., 2012. No. 18. P. 53–76. (in Russian)
Chentsov A. A., Chentsov A. G., and Chentsov P. A. Elements of Dynamic Programming in the Extremal Problems of Routing. Autom. Remote Control, 2014. Vol. 75, No. 3. P. 537–550 DOI: 10.1134/S0005117914030102
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. , 2017. Vol. 50. P. 83–109. DOI: 10.20537/2226-3594-2017-50-08 (in Russian)
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, 2017. Vol. 27, No. 4. P. 540–557. DOI: 10.20537/vm170405 DOI: 10.1007/b101971 (in Russian)
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. Vestn. UGATU., Upravlenie VT i I [The UGATU Bulletin. Series: Control, ADP equipment and informatics], 2009. Vol. 13, No. 2 (35). P. 280–286. (in Russian)
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. P. 63–66. (in Russian)
Wang G.G. and Xie S.Q. Optimal process planning for a combined punch-and-laser cutting machine using ant colony optimization. Int. J. Product. Res. , 2005. Vol. 43, No. 11. P. 2195–2216. DOI: 10.1080/00207540500070376
Lee M.-K. and Kwon K.-B. Cutting path optimization in NC cutting processes using a two-step genetic algorithm. Int. J. Product. Res. , 2006. Vol. 44, No. 24. P. 5307–5326. DOI: 10.1080/00207540600579615
Jing Y. and Zhige C. An Optimized Algorithm of Numerical Cutting-Path Control in Garment Manufacturing. Adv. Mater. Res. , 2013. Vol. 796. P. 454–457. DOI: 10.4028/www.scientific.net/AMR.796.454
Ganelina N.D. and Frolovskii V.D. Study of the methods for constructing the shortest path to round the segments on plane. Sib. Zh. Vychisl. Mat. [Siberian J. of Numer. Mathematics ], 2006. Vol. 9, No. 3. P. 241–252.
Verkhoturov M.A. and Tarasenko P.Yu. Software for the problems of optmization of the cutting tool path for planar _gure cutting on the basis of chain cutting. Vestn. UGATU., Upravlenie VT i I [The UGATU Bulletin. Series: Control, ADP equipment and informatics], 2008. Vol. 10, No. 2 (27). P. 123–130. (in Russian)
Bellman R. Dynamic programming treatment of the travelling salesman problem. J. ACM. 1962. Vol. 9, No. 1. P. 61–63. DOI: 10.1145/321105.321111
Held M. and Karp R.M. A dynamic programming approach to sequencing problems. J. Soc. Ind. Appl. Math., 1962. No. 10 (1). P. 196–210. DOI: 10.1137/0110015
Little J.D.C., Murti K.G., Sweeney D.W., and Karel C. Algorithm for the traveling salesman problem. Econ. Mat. Metod., 1965. Vol. 1, No. 1. P. 94–107.
Escudero L. An inexact algorithm for the sequential ordering problem. Eur. J. Oper. Res., 1988. Vol. 37, No. 2. P. 236–249.
Chentsov A.G., Chentsov A.A., Chentsov P.A. Extremal routing problem with internal losses. Proc. Steklov Inst. Math. 2009. Vol. 264, suppl. 1. P. 87–106. DOI: 10.1134/S0081543809050071
Article Metrics
Refbacks
- There are currently no refbacks.