### 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:

PDF#### References

- 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.