Online First 2024
Полный текст статьи (Full text)
УДК 517.977, 621.9:519.6(035)
MSC: 90C27
https://doi.org/10.21538/0134-4889-2025-31-1-fon-03
Статья посвящена светлой памяти Евгения Георгиевича Пыткеева —
выдающегося ученого-тополога, педагога и прекрасного человека.
Рассматриваются задачи маршрутизации перемещений с ограничениями предшествования и функциями стоимости с зависимостью от списка заданий. Исследуются варианты аддитивного агрегирования затрат и минимаксной постановки (задача на узкие места). Предполагается, что вся совокупность заданий, связанных с посещением мегаполисов (непустых конечных множеств), разбита в сумму двух кластеров, в результате чего возникают две частные задачи: предваряющая и финальная. Выполнение заданий финальной задачи может быть начато только после завершения всех заданий предваряющей. Целью исследования является оптимизация композиционных решений в случаях аддитивной и минимаксной постановок. Предлагается единый подход, связанный с раздельным решением предваряющей и финальной задач с использованием широко понимаемого динамического программирования. Построен оптимальный алгоритм для композиционного решения задач ощутимой размерности с приемлемым для практики быстродействием. Возможные применения могут быть связаны с задачей о демонтаже радиационно опасных объектов, задачей управления инструментом при фигурной листовой резке на машинах с ЧПУ, а также с некоторыми транспортными задачами, касающимися логистических проблем в малой авиации.
Ключевые слова: динамическое программирование, композиционные решения, условия предшествования.
Поступила 14.10.2024
После доработки 4.11.2024
Принята к публикации 11.11.2024
Опубликована онлайн: 1.12. 2024
Ченцов Александр Георгиевич
д-р физ.-мат. наук, чл.-корр.РАН, профессор
главный науч. сотрудник
Институт математики и механики им. Н.Н.Красовского УрО РАН;
профессор
Уральский федеральный университет
г. Екатеринбург
e-mail: chentsov@imm.uran.ru
Ченцов Павел Александрович
канд. физ.-мат. наук
старший науч. сотрудник
Институт математики и механики им. Н.Н.Красовского УрО РАН;
старший науч. сотрудник
Уральский федеральный университет
г. Екатеринбург
e-mail: p.chentsov@mail.ru
Ссылка на статью: А.Г.Ченцов, П.А.Ченцов. Динамическое программирование и декомпозиция в экстремальных задачах маршрутизации // Тр. Ин-та математики и механики УрО РАН. Опубликовано онлайн: 1.12. 2024. doi: 10.21538/0134-4889-2025-31-1-fon-03
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, Published online: December 1, 2024. doi: 10.21538/0134-4889-2025-31-1-fon-03.
