УДК 517.6
MSC: 05A05, 97N70, 97N80
DOI: 10.21538/0134-4889-2020-26-3-219-234
Работа выполнена при поддержке РФФИ (проект 19-01-00573) и в рамках исследований, проводимых в Уральском математическом центре.
Полный текст статьи (Full text)
Статья переведена: ISSN 0081-5438
Proceedings of the Steklov Institute of Mathematics, 2021, Vol. 315, Suppl. 1, pp. S67–S80. (Abstract)
Исследуется решение задачи маршрутизации перемещений с ограничениями и усложненными функциями стоимости. Более того, построение последних может быть затруднено, а потому этапы данного построения являются элементами решения задачи. Такая ситуация складывается, в частности, при исследовании инженерной задачи о демонтаже радиационно опасных элементов, где в рамках традиционной для дискретной оптимизации постановки требуется недопустимо большое время для построения матрицы затрат, элементы которой характеризуют дозы радиации, получаемые исполнителями на этапе перемещений и работ по демонтажу. Допускается, что на этапе вычислительной реализации получаемого оптимального алгоритма соответствующие “части” матрицы могут и не заноситься в память компьютера, а вычисляться по мере надобности. Применение развиваемых методов может быть связано с задачей демонтажа энергоблока АЭС, выведенного из эксплуатации.
Ключевые слова: динамическое программирование, маршрут, функция Беллмана
СПИСОК ЛИТЕРАТУРЫ
1. Gutin G., Punnen A. P. The traveling salesman problem and its variations. Berlin: Springer, 2002. 850 p.
2. Cook W. J. In pursuit of the traveling salesman: Mathematics at the limits of computation. Princeton: Princeton University Press, 2012. 228 p.
3. Гимади Э. Х., Хачай М. Ю. Экстремальные задачи на множествах перестановок. Екатеринбург: Изд-во УМЦ УПИ, 2016. 220 c.
4. Меламед И. И., Сергеев С. И., Сигал И. Х. Задача коммивояжера. Вопросы теории // Автоматика и телемеханика. 1989. №9. С. 3–34.
5. Меламед И. И., Сергеев С. И., Сигал И. Х. Задача коммивояжера. Точные алгоритмы // Автоматика и телемеханика. 1989. №10. С. 3–29.
6. Меламед И. И., Сергеев С. И., Сигал И. Х. Задача коммивояжера. Приближенные алгоритмы // Автоматика и телемеханика. 1989. №11. С. 3–26.
7. Беллман Р. Применение динамического программирования к задаче о коммивояжере // Кибернетический сб. М.: Мир. 1964. Т. 9. С. 219–228.
8. Хелд М., Карп Р. М. Применение динамического программирования к задачам упорядочения // Кибернетический сб. М.: Мир. 1964. Т. 9. С. 202–218.
9. Литл Дж., Мурти К., Суини Д., Кэрел К. Алгоритм для решения задачи о коммивояжере // Экономика и мат. методы. 1965. Т. 1 (Вып. 1). С. 94–107.
10. Коробкин В. В., Сесекин А. Н., Ташлыков О. Л., Ченцов А. Г. Методы маршрутизации и их приложения в задачах повышения безопасности и эффективности эксплуатации атомных станций / под общ. ред. чл.-кор. РАН И. А. Каляева. Москва: Новые технологии, 2012. 234 с.
11. Bianco L., Mingozzi A., Ricciardelli S. et. al. The Traveling salesman problem with precedence constraints // Papers of the 19th Annual Meeting / eds. W. Buhler, G. Feichtinger, R.F. Hartl, F.J. Radermacher, P. Stahly, Vortrage der 19. Jahrestagung. Berlin: Springer, 1992. P. 299–306. (Operations Research Proceedings; vol. 1990.) 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, №3. P. 173–189. doi: 10.1016/S0278-6125(03)90018-5
13. Salii Ya. Order-theoretic characteristics and dynamic programming for precedence constrained traveling salesman problem // Turku Center for Computer Science. 2017. Vol. 26. (Proc. of the 4th Russian Finnish Symposium on Discrete Mathematics, Turku, May 16–19 2017). P. 152–164.
14. Chentsov A. G., Chentsov P. A. The routing problems with optimization of the starting point: dynamic programming // Изв. Ин-та математики и информатики Удмурт. гос. ун-та. 2019. Т. 54. С. 102–121.
15. Ченцов А. Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории. Москва; Ижевск: НИЦ “Регулярная и хаотическая динамика”, 2008. 238 с.
16. Ченцов А. Г., Ченцов А. А. Задача маршрутизации, осложненная зависимостью функций стоимости и “текущих” ограничений от списка заданий // Моделирование и анализ информационных систем. 2016. T. 23, №2. C. 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. Vol. 2015. Art-no. 020028. 2018. 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. Vol. 2174 (1). Art-no. 020216. 2019. doi: 10.1063/1.5134367
19. Кропачев Ю. А., Ташлыков О. Л., Щеклеин С. Е. Оптимизация радиационной защиты на этапе вывода энергоблоков АЭС из эксплуатации // Изв. вузов. Ядерная энергетика. 2019. №1. С. 119–130.
20. Ташлыков О. Л., Щеклеин С. Е., Лукьяненко В. Ю., Михайлова А. Ф., Русских И. М., Селезнев Е. Н., Козлов А. В. Оптимизация состава радиационной защиты // Изв. вузов. Ядерная энергетика. 2015. №4. С. 36–42.
21. Коробкин В. В., Ченцов П. А. Оптимизация перемещения и замены тепловыделяющих сборок в активной зоне реактора типа ВВЭР / Мехатроника, автоматизация, управление МАУ-2009 // Материалы Междунар. науч.-техн. конф. Таганрог: ТТИ ЮФУ. 2009. С. 347–349.
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. P. 4329–4343.
23. Dewil R., Vansteenwegen P., Cattrysse D. Construction heuristics for generating tool paths for laser cutters // Internat. J. Product. Research. 2014. Vol. 52, no. 20. P. 5965–5984.
24. Dewil R., Vansteenwegen P., Cattrysse D. An improvement heuristic framework for the laser cutting tool path problem // Internat. J. Product. Research. 2015. Vol. 53, no. 6. P. 1761–1776.
25. Dewil R., Vansteenwegen P., Cattrysse D. A review of cutting path algorithms for cutters // Internat. J. Advanced Manufactoring Technology. 2016. Vol. 87. P. 1865–1884.
26. Petunin A. A. Modelling of tool path for the CNC Sheet Cutting Machines // AIP Conf. Proceedings. 2015. Vol. 1690. P. 060002(1)–060002(7).
27. Petunin A. A., Stylios S. Optimization models of tool path problem for CNC Sheet Metal Cutting Machines // IFAC — PaperOnLine. 2016. Vol. 49, no. 12. P. 23–28.
28. Petunin A. General model of tool path problem for the CNC Sheet Cutting Machines // IFAC — PaperOnLine. 2019. Vol. 52, no. 13. P. 2662–2667.
29. Lee M.-K., Kwon K.-B. Cutting path optimization in CNC cutting processes using a two-step genetic algorithm // Internat. J. Product. Research. 2006. Vol. 44, no. 24. P. 5307–5326.
30. Куратовский К., Мостовский А. Теория множеств. М.: Мир, 1970. 416 с.
31. Дьедонне Ж. Основы современного анализа. М.: Мир, 1964. 430 с.
32. Ченцов А. А., Ченцов А. Г. Модельный вариант задачи о последовательной утилизации источников излучения (итерации на основе оптимизирующих вставок) // Изв. Ин-та математики и информатики Удмурт. гос. ун-та. 2017. Т. 50. С. 83–109. doi: 10.20537/2226-3594-2017-50-08
33. Ченцов А. Г., Ченцов А. А. Задача маршрутизации с ограничениями, зависящими от списка заданий // Докл. РАН. 2015. Т. 465, № 2. С. 154–158.
34. Lawler E. L. Efficient implementation of dynamic programming algorithms for sequencing problems: Tech. Rep.: BW 106/79: Stichting Mathematisch Centrum. 1979. Vol. 106, no. 79. P. 1–16.
Поступила 21.06.2020
После доработки 21.07.2020
Принята к публикации 10.08.2020
Ченцов Александр Георгиевич
д-р физ.-мат. наук, профессор, чл.-кор. РАН
главный науч. сотрудник
Институт математики и механики им. Н.Н.Красовского УрО РАН;
профессор
Уральский федеральный университет им. Б.Н. Ельцина,
г. Екатеринбург
e-mail: chentsov@imm.uran.ru
Ченцов Алексей Александрович
канд. физ.-мат. наук
научн. сотрудник
Институт математики и механики им. Н.Н. Красовского УрО РАН
г. Екатеринбург
e-mail: chentsov.a@binsys.ru
Сесекин Александр Николаевич
д-р физ.-мат. наук, профессор
зав. кафедрой прикладной математики и механики
Уральский федеральный университет;
ведущий научн. сотрудник
Институт математики и механики им. Н.Н. Красовского УрО РАН
г. Екатеринбург
e-mail: a.n.sesekin@urfu.ru
Ссылка на статью: А.Г. Ченцов, А.А. Ченцов, А.Н. Сесекин. О задаче последовательного обхода мегаполисов с условиями предшествования и функциями стоимости с зависимостью от списка заданий // Тр. Ин-та математики и механики УрО РАН. 2020. Т. 26, № 3. С. 219-234
English
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
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
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.
[References -> on the "English" button bottom right]
