- Код статьи
- 10.31857/S0005231023050070-1
- DOI
- 10.31857/S0005231023050070
- Тип публикации
- Статья
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том / Номер выпуска 5
- Страницы
- 133-164
- Аннотация
- Рассматривается экстремальная задача маршрутизации перемещений с ограничениями. Одно из таких ограничений связано с выделением в составе исходной задачи предваряющей и финальной подзадач; задания, относящиеся к предваряющей подзадаче, должны быть выполнены прежде, чем начнется выполнение заданий финальной подзадачи. Такое условие может, в частности, возникать в задаче об управлении инструментом при термической резке на машинах с числовым программным управлением (ЧПУ): при наличии среди заготовок так называемых длинномерных деталей вблизи узкой границы материала процесс резки следует начинать с этих заготовок, так как такие детали подвержены тепловым деформациям, что потенциально может привести к браку. В рассматриваемой постановке выделяются две зоны, связанные с обслуживанием деталей. Предполагается, что совокупный маршрутный процесс в исходной задаче включает точку старта, собственно маршрут (перестановку индексов) и конкретную траекторию, согласованную с упомянутыми маршрутом и точкой старта. Предполагается, что в каждой из подзадач выделены свои условия предшествования, а функции стоимости, формирующие аддитивный критерий, могут допускать зависимость от списка заданий. Для применения динамического программирования в качестве метода решения вводится специальная двухэтапная процедура. Установлена структура оптимального решения и, на ее основе, построен алгоритм, реализованный на персональной электронно-вычислительной машине (ПЭВМ). Проведен вычислительный эксперимент.
- Ключевые слова
- динамическое программирование маршрут мегаполис условия предшествования
- Дата публикации
- 15.05.2023
- Год выхода
- 2023
- Всего подписок
- 0
- Всего просмотров
- 10
Библиография
- 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.
