УДК 517.977
MSC: 05A05, 97N70,97N80
DOI: 10.21538/0134-4889-2026-32-3-281-300
Исследуются задачи маршрутизации перемещений, ориентированные на инженерные приложения; последнее приводит к постановкам, включающим ограничения и усложненные функции стоимости. Предполагается, что все множество заданий разбито в сумму кластеров, обслуживание которых упорядочено; при посещении каждого кластера должна быть (всякий раз) решена задача оптимизации очередности выполнения заданий и (в ситуации с многовариантностью перемещений) траекторий, реализуемых согласованно с выбранной очередностью. Для частичных задач возможны ограничения предшествования и функции стоимости с зависимостью от списка заданий, что типично для многих приложений. На практике требуется находить “хорошие” решения совокупной задачи за приемлемое время. В настоящей работе для достижения данной цели используются декомпозиция, согласованная с кластерами заданий, и раздельное динамическое программирование. В результате достигается оптимизация композиционных решений с приемлемым быстродействием. Построен оптимальный алгоритм, реализованный на многоядерной ПЭВМ; проведен обширный вычислительный эксперимент. Возможное применение может быть связано, в частности, с задачей управления инструментом при фигурной листовой резке зонами на машинах с ЧПУ.
Ключевые слова: декомпозиция, динамическое программирование, маршрут, условия предшествования
СПИСОК ЛИТЕРАТУРЫ
1. Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера // Автоматика и телемеханика. 1989. № 9. С. 3–33; № 10. С. 3–29; № 11. С. 3–26.
2. Литл Дж., Мурти К., Суини Д., Кэрел К. Алгоритм для решения задачи о коммивояжере // Экономика и математические методы. 1965. Т. 1, Вып. 1. С. 94–107.
3. Gutin G., Punnen A. The traveling salesman problem and its variations. Vol. 12. NY: Springer, 2007. 830 p. https://doi.org/10.1007/b101971
4. Cook W.J. In pursuit of the traveling salesman. Mathematics at the limits of computation. Princeton, New Jersey: Princeton University Press, 2012. 248 p.
5. Гимади Э.Х., Хачай М.Ю. Экстремальные задачи на множествах перестановок. Екатеринбург: УМЦ УПИ, 2016. 248 c.
6. Беллман Р. Применение динамического программирования к задаче о коммивояжере // Кибер. сб. М.: Мир, 1964. Т. 9. С. 219–228.
7. Хелд М., Карп Р.М. Применение динамического программирования к задачам упорядочения // Кибер. сб. М.: Мир, 1964. Т. 9. С. 202–218.
8. Chisman J.A. The clustered traveling salesman problem // Comput. Oper. Res. 1975. Vol. 2, no. 2. P. 529–558.
9. Петунин А.А., Ченцов А.Г., Ченцов П.А. Оптимальная маршрутизация инструмента машин фигурной листовой резки с числовым программным управлением. Математические модели и алгоритмы. Екатеринбург: Изд-во УрФУ, 2020. 247 c.
10. Петунин А.А. О некоторых стратегиях формирования маршрута инструмента при разработке управляющих программ для машин термической резки материала // Вестн. Уфим. гос. авиац. техн. ун-та. 2009. Т. 13, № 2. С. 280–286.
11. Фроловский В. Автоматизация проектирования управляющих программ тепловой резки металла на оборудовании с ЧПУ // Информ. технологии в проектировании и производстве. 2005, № 4. С. 63–66.
12. Dewil R., Vansteenwegen P., Cattrysse D. Construction heuristics for generating tool paths for laser cutters // Inter. J. Product. Res. 2014. Т. 52, № 20. С. 5965–5984. https://doi.org/10.1080/00207543.2014.895064
13. Ye J., Chen Z.G. An optimized algorithm of numerical cutting-path control in garment manufacturing // Adv. Mat. Res. 2013. Vol. 796. С. 454–457. https://doi.org/10.4028/www.scientific.net/AMR.796.454
14. Lee M.K., Kwon K.B. Cutting path optimization in CNC cutting processes using a two-step genetic algorithm // Int. J. Prod. Res. Research. 2006. Vol. 44, no. 24. С. 5307–5326.
15. Hoeft J., Polekar U.S. Heuristics for the plate-cutting traveling salesman problem // IIE Transactions. 1997. Vol. 29, no. 9. P. 719–731. https://doi.org/10.1023/A:1018582320737
16. Ченцов А.Г., Ченцов П.А. Экстремальная двухэтапная задача маршрутизации и процедуры на основе динамического программирования // Тр. Ин-та математики и механики УрО РАН. 2022. Т. 28, № 2.
С. 215–248. https://doi.org/10.21538/0134-4889-2022-28-2-215-248
17. Ченцов А.Г., Ченцов П.А. Динамическое программирование в задаче маршрутизации: декомпозиционный вариант // Вестн. российских ун-в. Математика. 2022. Т. 27, № 137. С. 95–124. https://doi.org/10.20310/2686-9667-2022-27-137-95-124
18. Ченцов А.Г., Ченцов П.А. Двухэтапное динамическое программирование в задаче маршрутизации с элементами декомпозиции // Автоматика и телемеханика. 2023. № 5. С. 133–164.
19. Ченцов А.Г.,Ченцов П.А. Динамическое программирование и декомпозиция в экстремальных задачах маршрутизации // Тр. Ин-та математики и механики УрО РАН. 2025. Т. 31, № 1. С. 247–272. https://doi.org/10.21538/0134-4889-2025-31-1-fon-03
20. Куратовский К., Мостовский А. Теория множеств. М.: Мир, 1970. 416 с.
21. Дьедонне Ж. Основы современного анализа: пер. с англ. М.: Мир, 1964. 432 с.
22. Варга Дж. Оптимальное управление дифференциальными и функциональными уравнениями. М.: Наука, 1977. 624 с.
23. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 1999. 955 с.
24. Ченцов А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории. М.; Ижевск: Регулярная и хаотическая динамика, Ижевский институт компьютерных исследований, 2008. 239 с.
25. Ченцов А.Г.,Ченцов П.А. Многоэтапное динамическое программирование в задачах маршрутизации с ограничениями // Изв. ИМИ УдГУ. 2025. Т. 66. С. 115–165. https://doi.org/10.35634/2226-3594-2025-66-09
26. Ченцов А.Г.,Ченцов П.А. Маршрутизация в условиях ограничений: задача о посещении мегаполисов // Автоматика и телемеханика. 2016, № 11. С. 96–117.
27. Ченцов А.Г. Задача минимизации “на узкие места” с сиcтемой первоочередных заданий // Изв. ИМИ УдГУ. 2023. Т. 61. С. 156–186. https://doi.org/10.35634/2226-3594-2023-62-08
28. Lawler E.L. Efficient implementation of dynamic programming algorithm for sequencing problems. Report: BW 106/79. Amsterdam: Stichting Mathematisch Centrum, 1979.
Поступила 01.04.2026
После доработки 20.04.2026
Принята к публикации 27.04.2026
Ченцов Александр Георгиевич
д-р физ.-мат. наук, чл.-корр. РАН, профессор,
главный науч. сотрудник
Институт математики и механики им. Н.Н. Красовского УрО РАН;
профессор, Уральский федеральный университет
г. Екатеринбург
e-mail: chentsov@imm.uran.ru
Ченцов Павел Александрович
канд. физ.-мат. наук, старший науч. сотрудник
Институт математики и механики им. Н.Н. Красовского УрО РАН;
старший науч. сотрудник, Уральский федеральный университет
г. Екатеринбург
e-mail: chentsov.p@mail.ru
Ссылка на статью: А.Г. Ченцов, П.А. Ченцов. Динамическое программирование и декомпозиция в многоэтапных задачах маршрутизации // Тр. Ин-та математики и механики УрО РАН. 2026. Т. 32, № 3. С. 281–300
English
A.G. Chentsov, P.A. Chentsov. Dynamic programming and decomposition in multi-stage routing problems
Movement routing tasks focused on engineering applications are being investigated which leads to formulations involving constraints and complicated cost functions. It is assumed that the entire set of tasks is divided into a sum of clusters, the maintenance of which is ordered; when visiting each cluster, the task of optimizing the order of tasks and (in a situation with multiple movements) trajectories that are implemented in accordance with the selected sequence should be solved (each time). For partial tasks, precedence constraints and cost functions that depend on the job list are possible, which is typical for many applications. In practice, it is necessary to find "good"solutions to the overall problem in an acceptable amount of time. In this paper, decomposition that is consistent with job clusters and separate dynamic programming are used to achieve this goal. As a result, the optimization of composite solutions is achieved with acceptable performance. An optimal algorithm has been implemented on a multi-core PC, and an extensive computational experiment has been conducted. Possible applications include the control of tool with using of regions when sheet cutting in CNC machines.
Keywords: decomposition, dynamic programming, route, precedence conditions
Received April 01, 2026
Revised April 20, 2026
Accepted April 27, 2026
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, 620077 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, 620077 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 multi-stage routing problems. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2026, vol. 32, no. 3, pp. 281–300.
[References -> on the "English" button bottom right]
