TY - JOUR

T1 - ОПТИМАЛЬНАЯ МАРШРУТИЗАЦИЯ В ЗАДАЧАХ ПОСЛЕДОВАТЕЛЬНОГО ОБХОДА МЕГАПОЛИСОВ ПРИ НАЛИЧИИ ОГРАНИЧЕНИЙ

AU - Петунин, Александр Александрович

AU - Ченцов, Александр Георгиевич

AU - Ченцов, Павел Александрович

PY - 2022

Y1 - 2022

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

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

KW - CNC sheet cutting machine

KW - dynamic constraints

KW - dynamic programming

KW - feasible optimal solution

KW - megalopolises

KW - precedence constraints

KW - route

KW - tool path optimization problem

KW - trajectory

UR - https://elibrary.ru/item.asp?id=48572393

UR - http://www.scopus.com/inward/record.url?scp=85133093863&partnerID=8YFLogxK

U2 - 10.47475/2500-0101-2022-17205

DO - 10.47475/2500-0101-2022-17205

M3 - Статья

VL - 7

SP - 209

EP - 233

JO - Челябинский физико-математический журнал

JF - Челябинский физико-математический журнал

SN - 2500-0101

IS - 2

ER -