Двухэтапное динамическое программирование в задаче маршрутизации с элементами декомпозиции

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Доступ платный или только для подписчиков

Аннотация

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

Об авторах

А. Г Ченцов

Институт математики и механики им. Н.Н. Красовского УрО РАН;Уральский федеральный университет им. Б.Н. Ельцина

Email: chentsov@imm.uran.ru
Екатеринбург

П. А Ченцов

Институт математики и механики им. Н.Н. Красовского УрО РАН;Уральский федеральный университет им. Б.Н. Ельцина

Автор, ответственный за переписку.
Email: chentsov.p@mail.ru
Екатеринбург

Список литературы

  1. Gutin G., Punnen A. The traveling salesman problem and its variations. Berlin: Springer, 2002.
  2. Cook W.J. In pursuit of the traveling salesman. Mathematics at the limits of computation. Princeton, New Jersey: Princeton University Press, 2012.
  3. Гимади Э.Х., Хачай М.Ю. Экстремальные задачи на множествах перестановок. Екатеринбург: УМЦ УПИ, 2016.
  4. Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера // АиТ. 1989. № 9. С. 3-33; № 10. С. 3-29; № 11. С. 3-26.
  5. Литл Дж., Мурти К., Суини Д., Кэрел К. Алгоритм для решения задачи о коммивояжере // Экономика и математические методы. 1965. Т. 1. № 1. С. 94-107.
  6. Беллман Р. Применение динамического программирования к задаче о коммивояжере / Кибернетический сборник. М.: Мир, 1964. Т. 9. С. 219-228.
  7. Хелд М., Карп Р. М. Применение динамического программирования к задачам упорядочения / Кибернетический сборник. М.: Мир, 1964. Т. 9. С. 202-218.
  8. Ченцов А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории. М.-Ижевск: Регулярная и хаотическая динамика, Ижев. ин-т компьют. исслед., 2008.
  9. Ченцов А.Г., Ченцов А.А., Сесекин А.Н. Задачи маршрутизации перемещений с неаддитивным агрегированием затрат, М.: Ленанд, 2021.
  10. Петунин А.А., Ченцов А.Г., Ченцов П.А. Оптимальная маршрутизация инструмента машин фигурной листовой резки с числовым программным управлением. Математические модели и алгоритмы. Екатеринбург: УрФУ, 2020.
  11. Ченцов А.Г., Ченцов П.А. Динамическое программирование в задаче маршрутизации: декомпозиционный вариант // Вестник российских университетов. Математика. 2022. Т. 27. № 137. С. 95-124.
  12. Ченцов А.Г., Ченцов П.А. Экстремальная двухэтапная задача маршрутизации и процедуры на основе динамического программирования // Тр. Ин-та мат. и механики УрО РАН. 2022. Т. 28. № 2. С. 215-248.
  13. Ченцов А.Г. Задача последовательного обхода мегаполисов с условиями предшествования. АиТ. 2014. № 4. С. 170-190.
  14. Ченцов А.Г., Ченцов П.А. Маршрутизация в условиях ограничений: задача о посещении мегаполисов // АиТ. 2016. № 11. C. 96-117.
  15. Петунин А.А. О некоторых стратегиях формирования маршрута инструмента при разработке управляющих программ для машин термической резки материала // Вестн. Уфим. гос. авиац. техн. ун-та. 2009. Т. 13. № 2. С. 280-286.
  16. Фроловский В.Д. Автоматизация проектирования управляющих программ тепловой резки металла на оборудовании с ЧПУ // Информ. технологии в проектировании и производстве. 2005. № 4. C. 63-66.
  17. Wang G.G., Xie S.Q. Optimal process planning for a combined punch-and-laser cutting machine using ant colony optimization // Int. J. Product. Res., 43:11, Jun. (2005), P. 2195-2216.
  18. Lee M.-K., Kwon K.-B. Cutting path optimization in CNC cutting processes using a two-step genetic algorithm // Int. J. Product. Res. 2006. No. 44. P. 5307-5326.
  19. Куратовский К., Мостовский А. Теория множеств. М.: Мир, 1970.
  20. Дьедонне Ж. Основы современного анализа. М.: Мир, 1964.
  21. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2002.
  22. Варга Дж. Оптимальное управление дифференциальными и функциональными уравнениями. М.: Наука, 1977.
  23. Ченцов А.Г. К вопросу о маршрутизации комплексов работ // Вестн. Удмурт. ун-та. Математика. Механика. Компьютерные науки. 2013. Вып. 1. С. 59-82.
  24. Lawler E.L. Efficient implementation of dynamic programming algorithms for sequencing problems, Report BW106, Amsterdam: Mathematisch Centrum, 1979. P. 1-16.
  25. Ченцов А.Г., Ченцов А.А. К вопросу о нахождении значения маршрутной задачи с ограничениями // Проблемы управления и информатики. 2016. № 1. С. 41-54.
  26. Петунин А.А., Ченцов А.Г., Ченцов П.А. Оптимальная маршрутизация в задачах последовательного обхода мегаполисов при наличии ограничений // Челяб. физ.-мат. журн. 2022. Т. 7. № 2. С. 209-233.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2023