НОВЫЙ АЛГОРИТМ ПОСТРОЕНИЯ КРАТЧАЙШЕГО ПУТИ ОБХОДА КОНЕЧНОГО МНОЖЕСТВА НЕПЕРЕСЕКАЮЩИХСЯ КОНТУРОВ НА ПЛОСКОСТИ
Ключевые слова:
Задача резки, непрерывная резка, оптимизация, достаточные условия, эвристика, GTSP, метод переменных окрестностейАннотация
Рассматривается проблема маршрутизации режущего инструмента машин листо-
вой резки с ЧПУ для случая, когда точки врезки расположены на границах деталей, ограни-
ченных отрезками прямых и дугами окружностей, при этом используется техника непрерывной резки (CCP), т.е. каждый контур вырезается целиком, но не используется предва-
рительная дискретизация, то есть резка может начинаться с любой точки контура. Об-
щая задача поиска оптимального маршрута в этом случае сводится к минимизации длины
холостого хода. Показано, что она эквивалентна поиску кратчайшей ломаной с вершинами,
расположенными на контурах. Предложен новый эвристический алгоритм построения
такой ломаной для заранее заданного порядка обхода контуров. Показано, что получаю-
щееся решение представляет собой локальный минимум. Описаны некоторые достаточ-
ные условия, того, что решение является также глобальным минимумом, которые легко
проверяются численно, а некоторые даже визуально. Описана методика автоматического
учёта ограничений предшествования для практически важного случая наличия вложенных
контуров, возникающих как за счёт отверстий в деталях, так и за счёт расположения
мелких деталей в отверстиях крупных. При этом происходит также уменьшение размер-
ности задачи, что положительно сказывается на времени оптимизации, особенно дис-
кретной. Предложен эвристический алгоритм выбора порядка обхода контуров на основе
метода переменных окрестностей (VNS). Описаны альтернативные подходы применения
других методов дискретной оптимизации совместно с предложенным алгоритмом по-
строения кратчайшей ломаной для решения полной задачи непрерывной резки и возникаю-
щие при этом сложности как теоретического, так и практического характера. Описано
обобщение задачи непрерывной резки до более широкого класс задач сегментной резки и
обобщённой сегментной резки, что позволяет продвинуться в решении общей задачи пре-
рывистой резки. Описана схема применения предложенного алгоритма для решения задач
сегментной и обобщённой сегментной резки. Приведены некоторые результаты численных
экспериментов в сравнении с точным решением задачи для дискретной модели GTSP.
