УДК 517.977, 621.9:519.6(035)
MSC: 90C27
DOI: 10.21538/0134-4889-2025-31-1-fon-03
https://doi.org/10.21538/0134-4889-2025-31-1-fon-03
Статья посвящена светлой памяти Евгения Георгиевича Пыткеева —
выдающегося ученого-тополога, педагога и прекрасного человека.
Рассматриваются задачи маршрутизации перемещений с ограничениями предшествования и функциями стоимости с зависимостью от списка заданий. Исследуются варианты аддитивного агрегирования затрат и минимаксной постановки (задача на узкие места). Предполагается, что вся совокупность заданий, связанных с посещением мегаполисов (непустых конечных множеств), разбита в сумму двух кластеров, в результате чего возникают две частные задачи: предваряющая и финальная. Выполнение заданий финальной задачи может быть начато только после завершения всех заданий предваряющей. Целью исследования является оптимизация композиционных решений в случаях аддитивной и минимаксной постановок. Предлагается единый подход, связанный с раздельным решением предваряющей и финальной задач с использованием широко понимаемого динамического программирования. Построен оптимальный алгоритм для композиционного решения задач ощутимой размерности с приемлемым для практики быстродействием. Возможные применения могут быть связаны с задачей о демонтаже радиационно опасных объектов, задачей управления инструментом при фигурной листовой резке на машинах с ЧПУ, а также с некоторыми транспортными задачами, касающимися логистических проблем в малой авиации.
Ключевые слова: динамическое программирование, композиционные решения, условия предшествования
СПИСОК ЛИТЕРАТУРЫ
1. Gutin G., Punnen A. The traveling salesman problem and its variations. NY: Springer, 2002. 830 p.
2. Cook W.J. In pursuit of the traveling salesman. Mathematics at the limits of computation. Princeton; New Jersey: Princeton University Press, 2012. 248 p.
3. Гимади Э.Х., Хачай М.Ю. Экстремальные задачи на множествах перестановок. Екатеринбург: Изд-во УМЦ УПИ, 2016. 220 p.
4. Сергеев С.И. Алгоритмы решения минимаксной задачи коммивояжера. I. Подход на основе дина- мического программирования // Автоматика и телемеханика. 1995. №7. C. 144–150.
5. Меламед И.И., Сергеев С. И., Сигал И.Х. Задача коммивояжера // Автоматика и телемеханика. 1989. № 9. С. 3–33; № 10. С. 3–29; № 11. С. 3–26.
6. Беллман Р. Применение динамического программирования к задаче о коммивояжере // Кибернетический сборник. М.: Мир, 1964. Т. 9. С. 219–228.
7. Хелд М., Карп Р.М. Применение динамического программирования к задачам упорядочения // Кибернетический сборник. М.: Мир, 1964. Т. 9. С. 202–218.
8. Коробкин В.В., Сесекин А.Н., Ташлыков О.Л., Ченцов А.Г. Методы маршрутизации и их приложения в задачах повышения безопасности и эффективности эксплуатации атомных станций / под общ. ред. член-корр. РАН И.А. Каляева. М.: Новые технологии, 2012. 234 с.
9. Ченцов А.Г., Ченцов А.А. Модельный вариант задачи о последовательной утилизации источников излучения (итерации на основе оптимизирующих вставок) // Изв. Ин-та математики и информатики УдГУ. 2017. Т. 50. C. 83–109. https://doi.org/10.20537/2226-3594-2017-50-08
10. Ченцов А.Г., Ченцов А.А., Сесекин А.Н. Одна задача маршрутизации работ в условиях повышенной радиации // Изв. Ин-та математики и информатики УдГУ. 2021. Т. 58. С. 94–126. https://doi.org/10.35634/2226-3594-2021-58-06
11. Петунин А.А. О некоторых стратегиях формирования маршрута инструмента при разработке управляющих программ для машин термической резки материала // Вестн. Уфим. гос. авиац. техн. ун-та. 2009. Т. 13, № 2. С. 280–286.
12. Петунин А.А., Ченцов А.Г., Ченцов П.А. Оптимальная маршрутизация инструмента машин фигурной листовой резки с числовым программным управлением. Математические модели и алгоритмы. Екатеринбург: Ид-во УрФУ, 2020. 247 c.
13. Ченцов А.Г., Ченцов П.А. Маршрутизация в условиях ограничений: задача о посещении мегаполисов // Автоматика и телемеханика. 2016. Вып. 11. C. 96–117.
14. Петунин А.А., Ченцов А.Г., Ченцов П.А. К вопросу о маршрутизации движения инструмента в машинах листовой резки с числовым программным управлением // Науч.-техн. ведомости СПбГПУ. Сер. Информатика. Телекоммуникации. Управление. 2013. №2 (169). С. 280–286.
15. Ченцов А.Г., Ченцов А.А., Сесекин А.Н. Задачи маршрутизации перемещений с неаддитивным агрегированием затрат. М.: Ленанд, 2021. 230 c.
16. Ченцов А.Г., Ченцов А.А. Обобщенная модель курьера с дополнительными ограничениями // Вестн. ЮУрГУ. Математическое моделирование и программирование. 2016. Т. 9. № 1. С. 46–58. https://doi.org10.14529/mmp160104
17. Ченцов А.Г., Ченцов А.А., Сесекин А.Н. Динамическое программирование в обобщенной задаче "на узкие места"и оптимизация точки старта // Вестн. Удмурт. университета. Математика. Механика, Компьютерные науки. 2018. Т. 28, № 3. С. 348–363. https://doi.org/10.20537/vm180306
18. Ченцов А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории. М.; Ижевск: НЦ “Регулярная и хаотическая динамика”; Ижевский институт компьютерных исследований, 2008. 239 с.
19. Сигал И.Х., Иванова А.П. Введение в прикладное динамическое программирование. М.: Физматлит, 2007. 304 с.
20. Ченцов А.Г.,Ченцов П.А. Экстремальная двухэтапная задача маршрутизации и процедуры на основе динамического программирования // Тр. Ин-та математики и механики УрО РАН. 2022. Т. 28, № 2. С. 215–248. https://doi.org/10.21538/0134-4889-2022-28-2-215-248
21. Ченцов А.Г., Ченцов П.А. Двухэтапное динамическое программирование в задаче маршрутизации с элементами декомпозиции // Автоматика и телемеханика. 2023. № 5. С. 133–164. https://doi.org/10.31857/S0005231023050070
22. Ченцов А.Г. Задача маршрутизации “на узкие места” с системой первоочередных заданий // Изв. ИМИ УдГУ. 2023. Т. 61. С. 156–186. https://doi.org/10.35634/2226-3594-2023-61-09
23. Ченцов А.Г.,Ченцов П.А. Динамическое программирование в задаче маршрутизации: декомпозиционный вариант // Вестн. российских университетов. Математика. 2022. Т. 27, № 137. С. 95–124. https://doi.org/10.20310/2686-9667-2022-27-137-95-124
24. Куратовский К., Мостовский А. Теория множеств. М.: Мир, 1970. 416 c.
25. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2002. 960 c.
26. Варга Дж. Оптимальное управление дифференциальными и функциональными уравнениями. М.: Наука, 1977. 624 с.
27. Ченцов А.Г. К вопросу о маршрутизации комплексов работ // Вестн. Удмурт. университета. Математика. Механика. Компьютерные науки. 2013. № 1. С. 59–82.
28. Ченцов А.Г., Ченцов А.А., Ченцов П.А. Задача маршрутизации "на узкие места" (оптимизация в пределах зон) // Вестн. Удмурт. университета. Математика. Механика. Компьютерные науки. 2024. Т. 34, № 2. С. 267–285. https://doi.org/10.35634/vm240206
Поступила 14.10.2024
После доработки 4.11.2024
Принята к публикации 11.11.2024
Опубликована онлайн: 1.12. 2024
Ченцов Александр Георгиевич
д-р физ.-мат. наук, чл.-корр.РАН, профессор
главный науч. сотрудник
Институт математики и механики им. Н.Н. Красовского УрО РАН;
профессор
Уральский федеральный университет
г. Екатеринбург
e-mail: chentsov@imm.uran.ru
Ченцов Павел Александрович
канд. физ.-мат. наук
старший науч. сотрудник
Институт математики и механики им. Н.Н. Красовского УрО РАН;
старший науч. сотрудник
Уральский федеральный университет
г. Екатеринбург
e-mail: p.chentsov@mail.ru
Ссылка на статью: А.Г. Ченцов, П.А. Ченцов. Динамическое программирование и декомпозиция в экстремальных задачах маршрутизации // Тр. Ин-та математики и механики УрО РАН. 2025. Т. 31, № 1. С. 247-272
A. G. Chentsov, P. A. Chentsov. Dynamic programming and decomposition in extreme routing problems.
Problems of movement routing with precedence constraints and cost functions depending on the list of tasks are considered. Variants of additive cost aggregation and minimax statement (bottleneck problem) are studied. It is assumed that the entire set of tasks related to visiting megalopolises (nonempty finite sets) is divided into the sum of two clusters; as a result, two particular problems arise: preliminary and final. The execution of tasks of the final problem can be started only after the completion of all tasks of the preliminary one. The aim of the study is to optimize compositional solutions in the cases of additive and minimax statements. A unified approach is proposed related to the separate solution of the preliminary and final problems using broadly understood dynamic programming. An optimal algorithm for the compositional solution of problems of significant dimension with practically acceptable performance is constructed. Possible applications may include the problem of dismantling radiation-hazardous objects, tool control during shaped sheet cutting on CNC machines, and some transport problems related to logistical problems in small aviation.
Keywords: dynamic programming, compositional solutions, precedence conditions.
Received October 14, 2024
Revised November 4, 2024
Accepted November 11, 2024
Published online: December 1, 2024
Alexander Georgievich Chentsov, Dr. Phys.-Math. Sci, RAS Corresponding Member, Prof., Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia; Ural Federal University, Yekaterinburg, 620000 Russia, e-mail: chentsov@imm.uran.ru
Pavel Alexandrovich Chentsov, Cand. Sci. (Phys.-Math.) Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia; Ural Federal University, Yekaterinburg, 620000 Russia, e-mail: chentsov.p@mail.ru
Cite this article as: A.G. Chentsov, P.A. Chentsov. Dynamic programming and decomposition in extreme routing problems. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2025, vol. 31, no. 1, pp. 247–272 .
