A constrained routing problem with complicated cost functions is studied. The construction of the cost functions can be difficult, and therefore the stages of this construction are elements of the solution of the problem. This situation arises, in particular, in studying the engineering problem of dismantling radiation hazardous elements, where, in the framework of a problem statement traditional for discrete optimization, it takes an unacceptably long time to construct a cost matrix whose entries characterize the radiation doses received by performers at the stage of displacement and dismantling. It is assumed that, at the stage of the computational implementation of the resulting optimal algorithm, the corresponding “parts” of the matrix may be not fed to the computer’s memory but calculated as needed. Possible applications of the developed methods may be related to the problem of dismantling a decommissioned generator unit of an NPP.
Keywords: dynamic programming, route, Bellman function
Received June 21, 2020
Revised July 21, 2020
Accepted August 10, 2020
Funding Agency: This work was supported by the Russian Foundation for Basic Research (project no. 19-01-00573) and is a part of the research carried out at the Ural Mathematical Center.
Alexander Georgievich Chentsov, Dr. Phys.-Math. Sci., Prof., Corresponding Member RAS. Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia; Ural Federal University Yekaterinburg, 620002 Russia, e-mail: chentsov@imm.uran.ru
Aleksei Aleksandrovich Chentsov, Candidate of Phys.-Math. Sci. Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia, e-mail: chentsov.a@binsys.ru
Alexander Nikolaevich Sesekin, Dr. Phys.-Math. Sci., Prof., Head of the Department of Applied Mathematics and Mechanics — Ural Federal University, Yekaterinburg, 620002 Russia.; Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia, e-mail: a.n.sesekin@urfu.ru
REFERENCES
1. Gutin G., Punnen A.P. The traveling salesman problem and its variations. Berlin: Springer, 2002, 850 p. ISBN: 0-306-48213-4 .
2. Cook W.J. In pursuit of the traveling salesman: mathematics at the limits of computation. Princeton University Press, 2012, 228 p. ISBN: 0691152705 .
3. Gimadi E.Kh., Khachai M.Yu. Ekstremal’nye zadachi na mnozhestvakh perestanovok [Extremal problems on sets of permutations] Yekaterinburg: UMC UPI Publ., 2016, 220 p. ISBN 978-5-8295-0497-7 .
4. Melamed I.I., Sergeev S.I., Sigal I.Kh. The traveling salesman problem. Issues in theory. Autom. Remote Control, 1989, vol. 50, no. 9, pp. 1147–1173.
5. Melamed I.I., Sergeev S.I., Sigal I.Kh. The traveling salesman problem. Exact methods. Autom. Remote Control, 1989, vol. 50, no. 10, pp. 1303—1324.
6. Melamed I.I., Sergeev S.I., Sigal I.Kh. The traveling salesman problem. Approximate algorithms. Autom. Remote Control, 1989, vol. 50, no. 11, pp. 1459–1479.
7. Bellman R. Dynamic programming treatment of the travelling salesman problem. J. ACM, 1962, vol. 9, no. 1, pp. 61–63. doi: 10.1145/321105.321111
8. Held M., Karp R.M. A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics, 1962, vol. 10, no. 1, pp. 196–210. doi: 10.1137/0110015
9. Little L.D.C., Murty K.G., Sweeney D.W., Karel C. An algorithm for the traveling salesman problem. Operations Research, 1963, vol. 11, no. 6, pp. 972–989. doi: 10.1287/opre.11.6.972
10. Korobkin V.V., Sesekin A.N., Tashlykov O.L., Chentsov A.G. Metody marshrutizatsii i ikh prilozheniya v zadachakh povysheniya bezopasnosti i effektivnosti ekspluatatsii atomnykh stantsii [Routing methods and their applications in problems of the enhancement of safety and efficiency of nuclear plant operation]. Moscow: Novye Tekhnologii Publ., 2012, 234 p. ISBN: 97978-5-94694-027-6 .
11. Bianco L., Mingozzi A., Ricciardelli S. et al. The Traveling salesman problem with precedence constraints. In: Buhler W., Feichtinger G., Hartl R.F., Radermacher F.J., Stahly P. (eds), Papers of the 19th Annual Meeting / Vortrage der 19. Jahrestagung, Operations Research Proceedings, vol. 1990, Berlin: Springer, 1992, pp. 299–306. doi: 10.1007/978-3-642-77254-2_33
12. Castclino K., D’Souza R., Wright P.K. Toolpath optimization for minimizing airtime during machining. J. Manufacturing Systems, 2003, vol. 22, no. 3, pp. 173–180. doi: 10.1016/S0278-6125(03)90018-5
13. Salii Ya. Order-theoretic characteristics and dynamic programming for precedence constrained traveling salesman problem. In: Proc. of the 4th Russian Finnish Symposium on Discrete Mathematics (Turku, May 16-19 2017), TUCS Lecture Notes, no. 26, pp. 152–164.
14. Chentsov A.G., Chentsov P.A. The routing problems with optimization of the starting point: dynamic programming. Izv. IMI UdGU, 2019, vol. 54, pp. 102–121. doi: 10.20537/2226-3594-2019-54-08
15. Chentsov A.G. Ekstremal’nye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii [Extremal problems of routing and distribution of tasks: questions of theory]. Moscow; Izhevsk: RHD Pibl., 2008, 238 p. ISBN: 978-5-93972-654-2 .
16. Chentsov A.G., Chentsov A.A. The routing problem complicated by the dependence of cost functions and “current” restrictions on the list of tasks. Modelirovanie i analiz informazionnikh sistem, 2016, vol. 23, no. 2, pp. 211–227 (in Russian). doi: 10.18255/1818-1015-2016-2-211-227
17. Grigoryev A.M., Tashlykov O.L. Solving a routing optimization of works in radiation fields with using a supercomputer. AIP Conf. Proc., 2018, vol. 2015, art.-no. 020028. doi: 10.1063/1.5055101
18. Grigoryev A.M., Tashlykov O.L. Route optimization during works in non-stationary radiation fields with obstacles. AIP Conf. Proc., 2019, vol. 2174 (1), art.-no. 020216. doi: 10.1063/1.5134367
19. Kropachev, Y.A., Tashlykov, O.L., Shcheklein, S.E. Optimization of radiation protection at the NPP unit decommissioning stage. Izvestiya Wysshikh Uchebnykh Zawedeniy. Yadernaya Energetika, 2019, vol. 2019, рр. 119–130. doi: 10.26583/npe.2019.1.11
20. Tashlykov, O.L., Shcheklein, S.E., Luk’yanenko, V.Y., Mikhailova A.F., Seleznyov, E.N., Kozlov, A.V. The optimization of radiation protection composition. Nuclear Energy and Technology, 2016, vol. 2, no. 1, рр. 42–44. doi: 10.1016/j.nucet.2016.03.008
21. Korobkin V.V., Chentsov P.A. Optimization of the movement and replacement of fuel assemblies in the core of a WWER type reactor. In: Abstr. int. sci. tech. conf. “Mechatronics, automation, control” (MAC-2009). Taganrog: TTU SFU, 2009, pp. 347–349. ISBN: 978-5-8327-0339-8 .
22. Bohez E., Makhanov S.S., Sonthipermpoon K. Adaptive nonlinear tool path optimization for five-axis machining. Internat. J. Product. Research, 2000, vol. 38, no. 17, pp. 4329–4343. doi: 10.1080/00207540050205127
23. Dewil R., Vansteenwegen P., Cattrysse D. Construction heuristics for generating tool paths for laser cutters. Internat. J. Produc. Research, 2014, vol. 52, no. 20, pp. 5965–5984. doi: 10.1080/00207543.2014.895064
24. Dewil R., Vansteenwegen P., Cattrysse D. An improvement heuristic framework for the laser cutting tool path problem. Internat. J. Produc. Research, 2015, vol. 53, no. 6, pp. 1761–1776. doi: 10.1080/00207543.2014.959268
25. Dewil R., Vansteenwegen P., Cattrysse D. A review of cutting path algorithms for laser cutters. Int. J. Adv. Manuf. Technol., 2016, vol. 87, no. 5, pp. 1865–1884. doi: 10.1007/s00170-016-8609-1
26. Petunin A.A. Modelling of tool path for the cnc sheet cutting machines. AIP Conf. Proc., 2015, vol. 1690, art.-no. 060002, 7 p. doi: 10.1063/1.4936740
27. Petunin A.A., Stylios S. Optimization models of tool path problem for cnc sheet metal cutting machines. IFAC-PapersOnLine, 2016, vol. 49, no. 12, pp. 23–28. doi: 10.1016/j.ifacol.2016.07.544
28. Petunin A. general model of tool path problem for the cnc sheet cutting machines. IFAC-PapersOnLine, 2019, vol. 52, no. 13, pp. 2662–2667. doi: 10.1016/j.ifacol.2019.11.609
29. Lee M.-K., Kwon K.-B. Cutting path optimization in CNC cutting processes using a two-step genetic algorithm. Internat. J. Produc. Research, 2006, vol. 44, no. 24, pp. 5307–5326. doi: 10.1080/00207540600579615
30. Kuratowski K., Mostowski A. Set theory. Warszawa: PWN — Polish Scientific Publishers, 1968, 417 p. ISBN: 9780444534170 . Translated to Russian under the title Teoriya mnozhestv, Moscow: Mir Publ., 1970, 416 p.
31. Dieudonne J. Foundations of modern analysis. N Y: Acad. Press, 1960, 361 p. Translated to Russian under the title Osnovy sovremennogo analiza, Moscow: Mir Publ., 1964, 430 p.
32. Chentsov A.G., Chentsov A.A. A model variant of the problem about radiation sources utilization (iterations based on optimization insertions). Izv. IMI UdGU, 2017, vol. 50, pp. 83–109 (in Russian). doi: 10.20537/2226-3594-2017-50-08
33. Chentsov A.G., Chentsov A.A. Route problem with constraints depending on a list of tasks. Dokl. Math., 2015, vol. 92, no. 3, pp. 685–688. doi: 10.1134/S1064562415060083
34. Lawler E.L. Efficient implementation of dynamic programming algorithms for sequencing problems. CWI Technical report. Stichting Mathematisch Centrum. Mathematische Besliskunde-BW, 1979, vol. 106, no. 79, pp. 1–16.
Cite this article as: A.G. Chentsov, A.A. Chentsov, A.N. Sesekin. On the problem of sequential traversal of megalopolises with precedence conditions and cost functions depending on a list of tasks, Trudy Instituta Matematiki i Mekhaniki URO RAN, 2020, vol. 26, no. 3, pp. 219–234; Proceedings of the Steklov Institute of Mathematics (Suppl.), 2021, Vol. 315, Suppl. 1, pp. S67–S80.
