А.Г. Ченцов, П.А. Ченцов. Экстремальная двухэтапная задача маршрутизации и процедуры на основе динамического программирования ... С. 215-248

УДК 517.977

MSC: 90C27

DOI: 10.21538/0134-4889-2022-28-2-215-248

Работа выполнена при поддержке РФФИ, грант № 20-08-00873.

Исследуется задача маршрутизации, в которой множество заданий представлено в виде суммы двух дизъюнктных подмножеств. Задания из первого подмножества должны быть выполнены прежде, чем начнется выполнение заданий из второго. Каждое задание связано с посещением мегаполиса (непустого конечного множества) с целью выполнения некоторых работ. Выбор очередности выполнения заданий может быть стеснен условиями предшествования, которые локализуются для двух вышеупомянутых подмножеств полного множества заданий. Функции стоимости, участвующие в формировании аддитивного критерия, допускают зависимость от списка заданий. Для построения решения предлагается двухэтапная процедура на основе динамического программирования. Построен оптимальный алгоритм, реализованный на ПЭВМ; приведено решение модельной задачи, связанной с фигурной листовой резкой на машинах с ЧПУ.

Ключевые слова: динамическое программирование, маршрут, условия предшествования

СПИСОК ЛИТЕРАТУРЫ

1.   Gutin G., Punnen A. 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, New Jersey: Princeton Univ. Press, 2012. 228 p.

3.   Гимади Э. Х., Хачай М. Ю. Экстремальные задачи на множествах перестановок. Екатеринбург: Изд-во УМЦ УПИ, 2016. 220 с.

4.   Петунин А. А. О некоторых стратегиях формирования маршрута инструмента при разработке управляющих программ для машин термической резки материала // Вест. Уфим. гос. авиационного технич. ун-та. 2009. Т. 13, № 2. С. 280–286.

5.   Петунин А. А., Ченцов А. Г., Ченцов П. А. Оптимальная маршрутизация инструмента машин фигурной листовой резки с числовым программным управлением. Математические модели и алгоритмы. Екатеринбург: Изд-во УрФУ, 2020. 248 с.

6.   Литл Дж., Мурти К., Суини Д., Кэрел К. Алгоритм для решения задачи о коммивояжере // Экономика и мат. методы. 1965. Т. 1, вып. 1. С. 94–107.

7.   Беллман Р. Применение динамического программирования к задаче о коммивояжере // Кибернетический сб. М.: Мир. 1964. Т. 9. С. 219–228.

8.   Хелд М., Карп Р. М. Применение динамического программирования к задачам упорядочения // Кибернетический сб. М.: Мир. 1964. Т. 9. С. 202–218.

9.   Меламед И. И., Сергеев С. И., Сигал И. Х. Задача коммивояжера // Автоматика и телемеханика. 1989. Вып. 9. С. 3–33; Вып. 10. С. 3–29; Вып. 11. С. 3–26.

10.   Ченцов А. Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории. М.; Ижевск: НИЦ “Регулярная и хаотическая динамика”, 2008. 238 с.

11.   Ченцов А. Г., Ченцов А. А. Дискретно-непрерывная задача маршрутизации с условиями предшествования // Тр. Ин-та математики и механики УрО РАН. 2017. T. 23, № 1. C. 275–292.

12.   Ченцов А. Г., Ченцов П. А., A. G. Chentsov, P. A. Chentsov, The routing problems with optimization of the starting point: dynamic programming // Изв. Ин-та математики и информатики Удмурт. гос. ун-та. 2019. Т. 54. С. 102–121.

13.   Ченцов А. Г., Ченцов П. А. Маршрутизация в условиях ограничений: задача о посещении мегаполисов // Автоматика и телемеханика. 2016. Вып. 11. C. 96–117.

14.   Куратовский К., Мостовский А. Теория множеств. М.: Мир, 1970. 416 c.

15.   Дьедонне Ж. Основы современного анализа. М.: Мир, 1964. 430 с.

16.   Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.:МЦНМО, 2002. 960 с.

17.   Варга Дж. Оптимальное управление дифференциальными и функциональными уравнениями. М.: Наука, 1977. 624 с.

18.   Ченцов А. Г., Ченцов А. А., Сесекин А. Н. О задаче последовательного обхода мегаполисов с условиями предшествования и функциями стоимости с зависимостью от списка заданий // Тр. Ин-та математики и механики УрО РАН. 2020. Т. 26, № 3. С. 219–234.

19.   Ченцов А. Г. К вопросу о маршрутизации комплексов работ // Вест. Удмурт. ун-та. Математика. Механика. Компьютерные науки. 2013. Вып. 1. С. 59–82.

Поступила 4.04.2022

После доработки 26.04.2022

Принята к публикации 30.04.2022

Ченцов Александр Георгиевич
д-р физ.-мат. наук
чл.-корр. РАН, профессор
главный науч. сотрудник
Институт математики и механики им. Н.Н. Красовского УрО РАН;
профессор
Уральский федеральный университет
г. Екатеринбург
e-mail: chentsov@imm.uran.ru

Ченцов Павел Александрович
канд. физ.-мат. наук
старший науч. сотрудник
Институт математики и механики им. Н.Н. Красовского УрО РАН
г. Екатеринбург
e-mail: chentsov.p@mail.ru

Ссылка на статью: А.Г. Ченцов, П.А. Ченцов. Экстремальная двухэтапная задача маршрутизации и процедуры на основе динамического программирования // Тр. Ин-та математики и механики УрО РАН. 2022. Т. 28, № 2. С. 215-248

English

A.G. Chentsov, P.A. Chentsov. An extremal two-stage routing problem and procedures based on dynamic programming

We study a routing problem in which the set of tasks is represented as the union of two disjoint subsets. The tasks from the first subset must be completed before the execution of the tasks from the second subset. Each task is associated with a visit to a megalopolis (a nonempty finite set) in order to perform some work. The choice of the order in which the tasks are performed is subject to precedence conditions, which are localized for the mentioned two subsets of the total set of tasks. The cost functions used in the formation of the additive criterion may involve a dependence on the list of tasks. To construct a solution, a two-stage procedure based on dynamic programming is proposed. An optimal algorithm is constructed and implemented as a computer program. A model problem about shaped sheet cutting on CNC machines is solved.

Keywords: dynamic programming, route, precedence conditions

Received April 4, 2022

Revised April 26, 2022

Accepted April 30, 2022

Funding Agency: This work was supported by the Russian Foundation for Basic Research (project no. 20-08-00873).

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. An extremal two-stage routing problem and procedures based on dynamic programming, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2022, vol. 28, no. 2, pp. 215–248.

[References -> on the "English" button bottom right]