Отправить статью по E-mail Динамическое программирование в задаче маршрутизации: декомпозиционный вариант
- Авторы: Ченцов А.Г.1,2, Ченцов П.А.1,2
-
Учреждения:
- ФГБУН «Институт математики и механики им. Н. Н. Красовского» Уральского отделения Российской академии наук
- ФГАОУ ВО «Уральский федеральный университет им. первого Президента России Б. Н. Ельцина»
- Выпуск: Том 27, № 137 (2022)
- Страницы: 95-124
- Раздел: Статьи
- URL: https://journals.rcsi.science/2686-9667/article/view/295006
- DOI: https://doi.org/10.20310/2686-9667-2022-27-137-95-124
- ID: 295006
Цитировать
Полный текст
Аннотация
Исследуются вопросы применения аппарата динамического программирования (ДП) в задаче маршрутизации с ограничениями и функциями стоимости, допускающими зависимость от списка заданий. Предполагается заданным бинарное разбиение множества заданий, т. е. выделены две группы заданий; задания первой группы должны быть выполнены раньше, чем начнется выполнение заданий второй группы. В каждой из групп могут присутствовать условия предшествования. Данная постановка может быть связана, в частности, с вариантом листовой резки зонами на машинах с ЧПУ, где две вышеупомянутые группы заданий образуют зоны, намеченные на этапе раскроя. В общем случае для построения оптимального решения применяется двухэтапный вариант ДП. Стыковка этапов осуществляется посредством отождествления терминальной компоненты критерия предваряющей задачи с функций экстремума финальной задачи. Склеивание оптимальных решений предваряющей и финальной задач доставляет, как показано в статье, оптимальное решение совокупной задачи. На основе теоретических конструкций построен алгоритм, реализованный на ПЭВМ; проведен вычислительный эксперимент.
Ключевые слова
Об авторах
Александр Георгиевич Ченцов
ФГБУН «Институт математики и механики им. Н. Н. Красовского» Уральского отделения Российской академии наук; ФГАОУ ВО «Уральский федеральный университет им. первого Президента России Б. Н. Ельцина»
Email: chentsov@imm.uran.ru
доктор физико-математических наук, член-корреспондент РАН, главный научный сотрудник; профессор 620002, Российская Федерация, г. Екатеринбург, ул. Мира, 19
Павел Александрович Ченцов
ФГБУН «Институт математики и механики им. Н. Н. Красовского» Уральского отделения Российской академии наук; ФГАОУ ВО «Уральский федеральный университет им. первого Президента России Б. Н. Ельцина»
Email: chentsov.p@mail.ru
кандидат физико-математических наук, старший научный сотрудник; старший научный сотрудник 620002, Российская Федерация, г. Екатеринбург, ул. Мира, 19
Список литературы
- G. Gutin, A.P. Punnen, The Traveling Salesman Problem and its Variations, Springer, Berlin, 2002, 850 pp.
- W.J. Cook, In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation, Princeton University, United States, 2012, 228 pp.
- Э.Х. Гимади, М.Ю. Хачай, Экстремальные задачи на множествах перестановок, УМЦ УПИ, Екатеринбург, 2016, 216 с.
- M. Kubo, H. Kasugai, “The precedence constrained traveling salesman problem”, Journal of the Operations Research Society of Japan, 34:2 (1991), 152-172.
- Y. Salii, “Revisisting dynamic programming for precedence-constrained Traveling Salesman Problem and its time-dependent generalization”, European Journal of Operational Research, 272:1 (2019), 32-42.
- E. Balas, “New classes of efficiently solvable generalized Taveling Salesman Problems”, Annals of Operations Research, 86 (1999), 529-558.
- J.A. Chisman, “The clustered traveling salesman problem”, Computers and Operation Research, 2:2 (1975), 115-119.
- М.Ю. Хачай, Е.Д. Незнахина, “Приближенные схемы для обобщенной задачи коммивояжера”, Тр. ИММ УрО РАН, 22, 2016, 283-292.
- F.C.J. Lokin, “Procedures for traveling salesman problems with additional constraints”, European of Journal Operation al. Research, 3:2 (1979), 135-141.
- С.С. Лебедев, “О декомпозиции некоторых прикладных задач дискретной оптимизации”, Экономика и математические методы, 44:2 (2008), 121-125.
- В.И. Цурков, Декомпозиция в задачах большой размерности, Наука, М., 1981, 350 с.
- А.А. Первозванский, В.Г. Гайцгори, Декомпозиция, агрегирование и приближенная оптимизация, Наука, М., 1975, 344 с.
- А.Г. Ченцов, Экстремальные задачи маршрутизации и распределения заданий: вопросы теории, Ижевский институт компьютерных исследований, Ижевск, 2008, 238 с.
- Р. Беллман, “Применение динамического программирования к задаче о коммивояжере”, Кибернетический сборник. Т. 9, ред. А. А. Ляпунов, О. Б. Лупанов, Мир, М., 1964, 219-222.
- М. Хелд, Р.М. Карп, “Применение динамического программирования к задачам упорядочения”, Кибернетический сборник. Т. 9, ред. А. А. Ляпунов, О. Б. Лупанов, Мир, М., 1964, 202-218.
- А.А. Ченцов, А.Г. Ченцов, П.А. Ченцов, “Экстремальная задача маршрутизации с внутренними потерями”, Тр. ИММ УрО РАН, 14, 2008, 183-201.
- A.G. Chentsov, P.A. Chentsov, “The routing problems with optimization of the starting point: dynamic programming”, Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, 54 (2019), 102-121.
- А.Г. Ченцов, П.А. Ченцов, “Маршрутизация в условиях ограничений: задача о посещении мегаполисов”, Автоматика и телемеханика, 2016, №11, 96-117.
- А.Г. Ченцов, “К вопросу о маршрутизации комплексов работ”, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 2013, №1, 59-82.
- К. Куратовский, А. Мостовский, Теория множеств, Мир, М., 1970, 416 с.
- Ж. Дьедонне, Основы современного анализа, Мир, М., 1964, 430 с.
- Т. Кормен, Ч. Лейзерсон, Р. Ривест, Алгоритмы: построение и анализ, МЦНМО, М., 2000, 955 с.
- Дж. Варга, Оптимальное управление дифференциальными и функциональными уравнениями, Наука, М., 1977, 624 с.
- А.А. Петунин, А.Г. Ченцов, П.А. Ченцов, Оптимальная маршрутизация инструмента машин фигурной листовой резки с числовым программным управлением. Математические модели и алгоритмы, Издательство Уральского университета, Екатеринбург, 2020, 247 с.
Дополнительные файлы
