Аннотация:
Исследуется задача оптимальной маршрутизации перемещений
с дополнительными ограничениями типа условий предшествования и функциями стоимости, зависящими от списка заданий. Такого рода зависимости относятся к так называемым динамическим ограничениям, при которых значение целевой функции на каждом шаге перемещения зависит от траектории (истории) пройденного пути и определяет допустимость выбранного перемещения. Рассматриваемая постановка ориентирована прежде всего на инженерные приложения, связанные с оптимизацией маршрута инструмента машин ЧПУ; возможны и другие применения. Объектами посещения являются непустые конечные множества –- мегаполисы. В качестве основной задачи в данной работе рассматривается проблема оптимальной маршрутизации инструмента машин листовой резки с ЧПУ, известная как Cutting Path Problem или Tool Path Problem. Эта проблема возникает на этапе разработки управляющих программ для машины с ЧПУ, которые задают траекторию перемещения инструмента и ряд технологических команд. Среди формальных ограничений особо выделяются условия предшествования, которые вызваны технологическими особенностями листовой резки на машинах с ЧПУ и которые удаётся использовать для снижения вычислительной сложности решаемой задачи и построения допустимых вариантов решения. В качестве основного метода исследования используется широко понимаемое динамическое программирование (ДП), учитывающее условия предшествования и зависимость функций стоимости от списка заданий. Применительно к задаче маршрутизации инструмента машин листовой резки зависимость целевой функции от списка заданий позволяет уменьшить тепловые деформации материала при термической резке. В статье приводится строгая математическая формализация задачи маршрутизации перемещений с ограничениями и описание точного алгоритма решения. В процессе решения оптимизируются очерёдность выполнения заданий, конкретная траектория процесса и точка старта. Алгоритм реализован в виде программы для ПЭВМ; решены модельные примеры.
Ключевые слова:
мегаполисы,
маршрут,
траектория,
динамическое программирование,
условия предшествования,
динамические ограничения,
задача оптимизации пути инструмента,
машина листовой резки с ЧПУ,
допустимое оптимальное решение.
Работа выполнена при финансовой поддержке РФФИ (грант 20-08-00873).
Поступила в редакцию: 13.03.2022 Исправленный вариант: 29.04.2022
Тип публикации:
Статья
УДК:
519.8.А
Образец цитирования:
А. А. Петунин, А. Г. Ченцов, П. А. Ченцов, “Оптимальная маршрутизация в задачах последовательного обхода мегаполисов при наличии ограничений”, Челяб. физ.-матем. журн., 7:2 (2022), 209–233
\RBibitem{PetCheChe22}
\by А.~А.~Петунин, А.~Г.~Ченцов, П.~А.~Ченцов
\paper Оптимальная маршрутизация в задачах последовательного обхода мегаполисов при наличии ограничений
\jour Челяб. физ.-матем. журн.
\yr 2022
\vol 7
\issue 2
\pages 209--233
\mathnet{http://mi.mathnet.ru/chfmj282}
\crossref{https://doi.org/10.47475/2500-0101-2022-17205}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/chfmj282
https://www.mathnet.ru/rus/chfmj/v7/i2/p209
Эта публикация цитируется в следующих 3 статьяx:
Alexander A. Petunin, Natalya S. Kotel, Anastasia F. Tavaeva, “About one optimal solution example to the integrated 2d nesting and routing problem for cnc sheet cutting machines”, Yugra State University Bulletin, 2024, no. 4, 88
А. Г. Ченцов, П. А. Ченцов, “Двухэтапное динамическое программирование в задаче маршрутизации с элементами декомпозиции”, Автомат. и телемех., 2023, № 5, 133–164; A. G. Chentsov, P. A. Chentsov, “Two-stage dynamic programming in the routing problem with decomposition”, Autom. Remote Control, 84:5 (2023), 609–632
А. Г. Ченцов, А. А. Ченцов, “Динамическое программирование и вопросы разрешимости задачи маршрутизации «на узкие места» с ресурсными ограничениями”, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 32:4 (2022), 569–592
Цитирование в формате AMSBIB
Обратная связь: