OPTIMIZING THE STARTING POINT IN A PRECEDENCE CONSTRAINED ROUTING PROBLEM WITH COMPLICATED TRAVEL COST FUNCTIONS

Alexander G. Chentsov     (Krasovskii Institute of Mathematics and Mechanics,Ural Branch of the Russian Academy of Sciences,16 S. Kovalevskaya Str., Ekaterinburg, 620990, Russian Federation)
Alexey M. Grigoryev     (Krasovskii Institute of Mathematics and Mechanics,Ural Branch of the Russian Academy of Sciences,16 S. Kovalevskaya Str., Ekaterinburg, 620990, Russian Federation)
Alexey A. Chentsov     (Krasovskii Institute of Mathematics and Mechanics,Ural Branch of the Russian Academy of Sciences,16 S. Kovalevskaya Str., Ekaterinburg, 620990, Russian Federation)

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


Dynamic programming, Route, Sequencing, Precedence constraints, Parallel computation

Full Text:

PDF

References


  1. 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.
  2. 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.
  3. 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.
  4. Gutin G., Punnen A.P. The Traveling Salesman Problem and its Variations. New York: Springer, 2002. DOI: 10.1007/b101971
  5. Cook W. J. In Pursuit of the Traveling Salesman. Mathematics at the Limits of Computation. New Jersey: Princeton University Press, 2012. p. 248.
  6. 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)
  7. 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
  8. 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
  9. 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)
  10. 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
  11. 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
  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. , 2016. Vol. 295, supp. 1. P. 38–46. DOI: 10.1134/S0081543816090054
  13. 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)
  14. Kuratowski K., Mostowski A. Set Theory. Amsterdam: North-Holland Publishing Company, 1968. p. 417.
  15. Dieudonné J. Foundations of Modern Analysis. New York: Academic Press, 1969. 407 p.
  16. 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
  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, 2012. Vol. 73, No. 3. P. 532–546. DOI: 10.1134/S0005117912030113
  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., 2012. No. 18. P. 53–76. (in Russian)
  19. 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
  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. , 2017. Vol. 50. P. 83–109. DOI: 10.20537/2226-3594-2017-50-08 (in Russian)
  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, 2017. Vol. 27, No. 4. P. 540–557. DOI: 10.20537/vm170405 DOI: 10.1007/b101971 (in Russian)
  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. 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)
  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. P. 63–66. (in Russian)
  24. 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
  25. 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
  26. 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
  27. 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.
  28. 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)
  29. 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
  30. 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
  31. 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.
  32. Escudero L. An inexact algorithm for the sequential ordering problem. Eur. J. Oper. Res., 1988. Vol. 37, No. 2. P. 236–249.
  33. 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



DOI: http://dx.doi.org/10.15826/umj.2018.2.006

Article Metrics

Metrics Loading ...

Refbacks

  • There are currently no refbacks.