On the Problem of Sequential Traversal of Megalopolises with Precedence Conditions and Cost Functions Depending on a List of Tasks

A. G. Chentsov ; A. A. Chentsov ; A. N. Sesekin

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 26 (2020) no. 3, pp. 219-234

Résumé

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 a nuclear power plant.

Détail

Keywords: dynamic programming, Bellman function.
Mots-clés : route

Bibliographie

[1] Gutin G., Punnen A. P., The traveling salesman problem and its variations, Springer, Berlin, 2002, 850 pp. | MR

[2] Cook W. J., In pursuit of the traveling salesman: Mathematics at the limits of computation, Princeton University Press, Princeton, 2012, 228 pp. | MR | Zbl

[3] Gimadi E. Kh., Khachai M. Yu., Ekstremalnye zadachi na mnozhestvakh perestanovok, Izd-vo UMTs UPI, Ekaterinburg, 2016, 220 pp.

[4] Melamed I. I., Sergeev S. I., Sigal I. Kh., “Zadacha kommivoyazhera. Voprosy teorii”, Avtomatika i telemekhanika, 1989, no. 9, 3–34

[5] Melamed I. I., Sergeev S. I., Sigal I. Kh., “Zadacha kommivoyazhera. Tochnye algoritmy”, Avtomatika i telemekhanika, 1989, no. 10, 3–29 | Zbl

[6] Melamed I. I., Sergeev S. I., Sigal I. Kh., “Zadacha kommivoyazhera. Priblizhennye algoritmy”, Avtomatika i telemekhanika, 1989, no. 11, 3–26 | Zbl

[7] Bellman R., “Primenenie dinamicheskogo programmirovaniya k zadache o kommivoyazhere”, Kiberneticheskii sb., v. 9, Mir, M., 1964, 219–228

[8] Kheld M., Karp R. M., “Primenenie dinamicheskogo programmirovaniya k zadacham uporyadocheniya”, Kiberneticheskii sb., v. 9, Mir, M., 1964, 202–218

[9] Litl Dzh., Murti K., Suini D., Kerel K., “Algoritm dlya resheniya zadachi o kommivoyazhere”, Ekonomika i mat. metody, 1:1 (1965), 94–107

[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, ed. pod obsch. red. chl.-kor. RAN I. A. Kalyaeva, Novye tekhnologii, Moskva, 2012, 234 pp.

[11] Bianco L., Mingozzi A., Ricciardelli S. et. al, “The Traveling salesman problem with precedence constraints”, Papers of the 19th Annual Meeting, Vortrage der 19. Jahrestagung, Operations Research Proceedings, 1990, eds. W. Buhler, G. Feichtinger, R.F. Hartl, F.J. Radermacher, P. Stahly, Springer, Berlin, 1992, 299–306 | DOI

[12] Castclino K., D'Souza R., Wright P. K., “Toolpath optimization for minimizing airtime during machining”, J. Manufacturing Systems, 22:3 (2003), 173–189 | DOI

[13] Salii Ya., “Order-theoretic characteristics and dynamic programming for precedence constrained traveling salesman problem”, Proc. of the 4th Russian Finnish Symposium on Discrete Mathematics (Turku, May 16-19 2017), Turku Center for Computer Science, 26, 2017, 152–164

[14] Chentsov A. G., Chentsov P. A., “The routing problems with optimization of the starting point: dynamic programming”, Izv. In-ta matematiki i informatiki Udmurt. gos. un-ta, 54 (2019), 102–121 | MR

[15] Chentsov A. G., Ekstremalnye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii, NITs “Regulyarnaya i khaoticheskaya dinamika”, Moskva; Izhevsk, 2008, 238 pp.

[16] Chentsov A. G., Chentsov A. A., “Zadacha marshrutizatsii, oslozhnennaya zavisimostyu funktsii stoimosti i “tekuschikh” ogranichenii ot spiska zadanii”, Modelirovanie i analiz informatsionnykh sistem, 23:2 (2016), 211–227 | MR

[17] Grigoryev A. M., Tashlykov O. L., “Solving a routing optimization of works in radiation fields with using a supercomputer”, AIP Conf. Proc., 2015, 2018, Art-no. 020028 | DOI

[18] Grigoryev A. M., Tashlykov O. L., “Route optimization during works in non-stationary radiation fields with obstacles”, AIP Conf. Proc., 2174 (1), 2019, Art-no. 020216 | DOI

[19] Kropachev Yu. A., Tashlykov O. L., Scheklein S. E., “Optimizatsiya radiatsionnoi zaschity na etape vyvoda energoblokov AES iz ekspluatatsii”, Izv. vuzov. Yadernaya energetika, 2019, no. 1, 119–130

[20] Tashlykov O. L., Scheklein S. E., Lukyanenko V. Yu., Mikhailova A. F., Russkikh I. M., Seleznev E. N., Kozlov A. V., “Optimizatsiya sostava radiatsionnoi zaschity”, Izv. vuzov. Yadernaya energetika, 2015, no. 4, 36–42

[21] Korobkin V. V., Chentsov P. A., “Optimizatsiya peremescheniya i zameny teplovydelyayuschikh sborok v aktivnoi zone reaktora tipa VVER”, Mekhatronika, avtomatizatsiya, upravlenie MAU-2009, Materialy Mezhdunar. nauch.-tekhn. konf., TTI YuFU, Taganrog, 2009, 347–349

[22] Bohez E., Makhanov S. S., Sonthipermpoon K., “Adaptive nonlinear tool path optimization for five-axis machining”, Internat. J. Product. Research, 38:17 (2000), 4329–4343 | DOI | Zbl

[23] Dewil R., Vansteenwegen P., Cattrysse D., “Construction heuristics for generating tool paths for laser cutters”, Internat. J. Product. Research, 52:20 (2014), 5965–5984 | DOI

[24] Dewil R., Vansteenwegen P., Cattrysse D., “An improvement heuristic framework for the laser cutting tool path problem”, Internat. J. Product. Research, 53:6 (2015), 1761–1776 | DOI

[25] Dewil R., Vansteenwegen P., Cattrysse D., “A review of cutting path algorithms for cutters”, Internat. J. Advanced Manufactoring Technology, 87 (2016), 1865–1884 | DOI

[26] Petunin A. A., “Modelling of tool path for the CNC Sheet Cutting Machines”, AIP Conf. Proceedings, 1690, 2015, 060002(1)-060002(7) | DOI

[27] Petunin A. A., Stylios S., “Optimization models of tool path problem for CNC Sheet Metal Cutting Machines”, IFAC - PaperOnLine, 49:12 (2016), 23–28 | DOI

[28] Petunin A., “General model of tool path problem for the CNC Sheet Cutting Machines”, IFAC - PaperOnLine, 52:13 (2019), 2662–2667 | DOI

[29] Lee M.-K., Kwon K.-B., “Cutting path optimization in CNC cutting processes using a two-step genetic algorithm”, Internat. J. Product. Research, 44:24 (2006), 5307–5326 | DOI | Zbl

[30] Kuratovskii K., Mostovskii A., Teoriya mnozhestv, Mir, M., 1970, 416 pp.

[31] Dedonne Zh., Osnovy sovremennogo analiza, Mir, M., 1964, 430 pp.

[32] Chentsov A. A., Chentsov A. G., “Modelnyi variant zadachi o posledovatelnoi utilizatsii istochnikov izlucheniya (iteratsii na osnove optimiziruyuschikh vstavok)”, Izv. In-ta matematiki i informatiki Udmurt. gos. un-ta, 50 (2017), 83–109 | DOI | Zbl

[33] Chentsov A. G., Chentsov A. A., “Zadacha marshrutizatsii s ogranicheniyami, zavisyaschimi ot spiska zadanii”, Dokl. RAN, 465:2 (2015), 154–158 | Zbl

[34] Lawler E. L., “Efficient implementation of dynamic programming algorithms for sequencing problems: Tech. Rep.: BW 106/79”, Stichting Mathematisch Centrum, 106:79 (1979), 1–16