|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Математика
Оптимальная маршрутизация в задачах последовательного обхода мегаполисов при наличии ограничений
А. А. Петунинab, А. Г. Ченцовb, П. А. Ченцовb a Уральский федеральный университет им. первого Президента России Б. Н. Ельцина, г. Екатеринбург
b Институт математики и механики им. Н. Н. Красовского Уральского отделения РАН, г. Екатеринбург
Аннотация:
Исследуется задача оптимальной маршрутизации перемещений
с дополнительными ограничениями типа условий предшествования и функциями стоимости, зависящими от списка заданий. Такого рода зависимости относятся к так называемым динамическим ограничениям, при которых значение целевой функции на каждом шаге перемещения зависит от траектории (истории) пройденного пути и определяет допустимость выбранного перемещения. Рассматриваемая постановка ориентирована прежде всего на инженерные приложения, связанные с оптимизацией маршрута инструмента машин ЧПУ; возможны и другие применения. Объектами посещения являются непустые конечные множества –- мегаполисы. В качестве основной задачи в данной работе рассматривается проблема оптимальной маршрутизации инструмента машин листовой резки с ЧПУ, известная как Cutting Path Problem или Tool Path Problem. Эта проблема возникает на этапе разработки управляющих программ для машины с ЧПУ, которые задают траекторию перемещения инструмента и ряд технологических команд. Среди формальных ограничений особо выделяются условия предшествования, которые вызваны технологическими особенностями листовой резки на машинах с ЧПУ и которые удаётся использовать для снижения вычислительной сложности решаемой задачи и построения допустимых вариантов решения. В качестве основного метода исследования используется широко понимаемое динамическое программирование (ДП), учитывающее условия предшествования и зависимость функций стоимости от списка заданий. Применительно к задаче маршрутизации инструмента машин листовой резки зависимость целевой функции от списка заданий позволяет уменьшить тепловые деформации материала при термической резке. В статье приводится строгая математическая формализация задачи маршрутизации перемещений с ограничениями и описание точного алгоритма решения. В процессе решения оптимизируются очерёдность выполнения заданий, конкретная траектория процесса и точка старта. Алгоритм реализован в виде программы для ПЭВМ; решены модельные примеры.
Ключевые слова:
мегаполисы,
маршрут,
траектория,
динамическое программирование,
условия предшествования,
динамические ограничения,
задача оптимизации пути инструмента,
машина листовой резки с ЧПУ,
допустимое оптимальное решение.
Поступила в редакцию: 13.03.2022 Исправленный вариант: 29.04.2022
Образец цитирования:
А. А. Петунин, А. Г. Ченцов, П. А. Ченцов, “Оптимальная маршрутизация в задачах последовательного обхода мегаполисов при наличии ограничений”, Челяб. физ.-матем. журн., 7:2 (2022), 209–233
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/chfmj282 https://www.mathnet.ru/rus/chfmj/v7/i2/p209
|
Статистика просмотров: |
Страница аннотации: | 106 | PDF полного текста: | 94 | Список литературы: | 24 |
|