Алгоритмы маршрутизации для систем технологической подготовки процессов раскроя

Т.А. Макаровских,
доц., к. ф.-м.н., kwark@mail.ru
А.В. Панюков,
зав. каф. ЭММиС, д-р. ф.-м.н., проф., paniukovav@susu.ac.ru
Е.А. Савицкий,
асп., egor88@inbox.ru
ФГБОУ ВПО ЮУрГУ (НИУ), г. Челябинск

Развитие автоматизации производства привело к появлению технологического оборудования с числовым программным управлением, используемого для резки листовых материалов. Новые технологии позволяют осуществлять вырезание по произвольной траектории с достаточной для практики точностью. Снятие требования резки только сквозными прямолинейными резами позволяет существенно снизить отходы материала. Технологии ECP и ICP за счет возможности совмещения границ вырезаемых деталей позволяют сократить расход материала, длину горячей резки, и длину холостых проходов. Проблемы уменьшения отходов материала и максимального совмещения фрагментов контуров вырезаемых деталей решается на этапе составления раскройного плана. Целью данной работы является изложение математических моделей проблемы маршрутизации при вырезании деталей и алгоритмов нахождения маршрутов, удовлетворяющих технологическим ограничениям.

The development of industrial automation has led to emergence of equipment with numerical programming control used for cutting of sheet materials. New technologies allow realizing cutting along an arbitrary path with sufficient for practical purposes accuracy. Withdrawal of the requirement to cut only by straight through-cuts can significantly reduce material waste. Technologies ECP and ICP can reduce material consumption, long hot cut, and the length of idle passes due to the possibility of combining the boundaries of cut parts. Problems of reducing the material waste and maximizing combination of fragments contours of cut out parts is achieved at the stage of cutting plan design. The purpose of this paper is to present the mathematical models of routing problems for cutting process and algorithms for finding the routes that meet some technological constraints.

Введение

В 1949 г. за рубежом появились первые публикации по линейному программированию. В 1951 г. вышло первое издание монографии [1], в которой впервые рассмотрены вопросы применения линейного программирования для оптимального гильотинного раскроя (т.е. построения раскройного плана с определением последовательности сквозных резов на гильотине). Развитие автоматизации производства привело к появлению технологического оборудования с числовым программным управлением (ЧПУ), используемого для резки листовых материалов: машин газовой (кислородной), плазменной, лазерной и электроэрозионной резки материала. Новые технологии позволяют осуществлять вырезание по произвольной траектории с достаточной для практики точностью.

Снятие требования резки только сквозными прямолинейными резами позволяет существенно снизить отходы материала, в связи с этим появилось множество публикаций, посвященных вопросам негильотинного раскроя и его оптимизации в различных производствах и на разных уровнях автоматизации. Подробный обзор задач раскроя, алгоритмов и методов их решения специалистами уфимской научной школы приведен в работе А.С. Филипповой [2]. Задачам геометрического проектирования и управления посвящены также работы Ю.Г. Стояна [3]. Точным методам негильотинного прямоугольного раскроя посвящены и работы В.М. Картака [4], А.А. Петунина [5], коллектива Р. Девила [6]. Интерес к этим задачам привел к тому, что в настоящее время по всему миру существуют сообщества, объединяющие исследователей, заинтересованных в данной задаче, например, ESICUP (Европейская группа по интересам в области раскроя-упаковки) [7].

В отличие от гильотинного раскроя, негильотинный раскройный план не дает программу вырезания деталей. Построение программы управления раскройным автоматом для реализации заданного раскройного плана является самостоятельной задачей. В работе [8] Дж. Хоэфт и У. С. Палекар предлагают следующую классификацию задач маршрутизации инструмента машин листовой резки.

1. Обобщенная задача коммивояжера (GTSP) (Generalized Travelling Salesman Problem ): режущий инструмент последовательно проходит по контуру каждой детали. Точка врезки в контур задана. Данная технология не допускает совмещения фрагментов контуров вырезаемых деталей. Оптимальным маршрутом является решение обобщенной задачи коммивояжера на множестве точек врезки с ограничениями предшествования, учитывающими вложенность одних контуров во внутренность других.

2. Задача последовательной резки (CCP) (Continuous Cutting Problem): детали вырезаются последовательно. Точка врезки может находиться в любой части контура, переход к другому контуру осуществляется только после окончания вырезания текущего. Данная технология, как и GTSP, не допускает совмещения фрагментов контуров вырезаемых деталей. Оптимальным маршрутом является решение обобщенной задачи коммивояжера на множестве точек врезки с ограничениями предшествования, учитывающими вложенность одних контуров во внутренность других. Технологии GTSP и CCP различаются размерами и значениями элементов матриц стоимостей для задачи коммивояжера. Размер CPP задачи коммивояжера в общем случае не меньше размера GTSP задачи коммивояжера. Фактически технология CCP в сравнении с технологией GTSP позволяет сократить только время на холостые проходы между точками врезки. Алгоритмы для задачи маршрутизации по технологии CCP приведены в работах [5, 9].

3. Задача с фиксированными точками врезки (ECP) (Endpoint Cutting Problem): инструмент осуществляет врезку и переходит к другому фрагменту раскройного плана в заданных точках на границе. Допускается совмещение контуров вырезаемых деталей, что приводит к вырезанию контура отдельных деталей по частям. Для реализации данной технологии необходимо представление раскройного плана в виде плоского графа, в котором каждая компонента связности является полуэйлеровым графом с вершинами нечетной степени инцидентными ее внешней грани. В этом случае построение маршрута для вырезания каждой компоненты связности сводится к построению OE-цепи [5, 10]. Порядок обхода компонент связности определяется решением обобщенной задачи коммивояжера на орграфе возможных переходов между компонентами связности с ограничениями предшествования, учитывающими вложенность одних компонент связности во внутренность контуров других компонент связности. Поскольку, благодаря совмещению фрагментов контуров деталей, количество компонент связности меньше количества деталей, то размер ECP задачи коммивояжера в общем случае не больше размера GTSP задачи коммивояжера.

4. Задача прерывистого раскроя (ICP) (Intermittent Cutting Problem): общий случай задачи раскроя, когда допускается совмещение контуров вырезаемых деталей, и нет ограничений на выбор точек врезки. Для реализации данной технологии необходимо представление раскройного плана в виде плоского графа, в котором, в отличие от технологии ECP, отсутствует требование эйлеровости компонент связности. Построение маршрута для вырезания каждой компоненты связности сводится к построению упорядоченного эйлерового покрытия данной компоненты связности OE-цепями [11, 12]. Порядок обхода компонент связности определяется решением обобщенной задачи коммивояжера на орграфе возможных переходов между компонентами связности с ограничениями предшествования, учитывающими вложенность одних компонент связности во внутренность контуров других компонент связности. Снятие ограничения эйлеровости компонент связности позволяет увеличить их размер за счет совмещения фрагментов контуров деталей, тем самым уменьшить количество компонент связности. Следовательно, размер ICP задачи коммивояжера не больше размера ECP задачи коммивояжера.

Таким образом, технологии ECP и ICP за счет возможности совмещения границ вырезаемых деталей позволяют сократить расход материала, длину горячей резки, и длину холостых проходов. Проблемы уменьшения отходов материала и максимального совмещения фрагментов контуров вырезаемых деталей решается на этапе составления раскройного плана. Целью данной работы является изложение математических моделей проблемы маршрутизации при вырезании деталей и алгоритмов нахождения маршрутов, удовлетворяющих технологическим ограничениям.

1. Основные этапы технологической подготовки процессов раскроя

Применение технологий ECP и ICP в системе технологической подготовки процессов раскроя плоских деталей предполагает следующие этапы.

1. Составление раскройного плана, заключающееся в нахождении такого варианта размещения вырезаемых деталей на прямоугольном листе или ленте, при котором минимизируются отходы и максимизируется длина совмещенных элементов контуров вырезаемых деталей. Решению данной задачи посвящено множество публикаций [1, 2, 4, 9].

2. Абстрагирование раскройного плана до плоского графа. Для определения последовательности резки фрагментов раскройного плана не используется информация о форме детали, поэтому все кривые без самопересечений и соприкосновений на плоскости, представляющие форму деталей, интерпретируются в виде ребер графа, а все точки пересечений и соприкосновений представляются в виде вершин графа. Для анализа выполнения технологических ограничений необходимо введение дополнительных функций на множестве вершин, граней и ребер полученного графа.

3. Решение задачи построения оптимальных маршрутов с ограничениями, наложенными на порядок обхода ребер. Данные ограничения непосредственно вытекают из технологических ограничений, наложенных на порядок вырезания деталей: отрезанная от листа часть не должна требовать дополнительных разрезаний [13], должны отсутствовать пересечения резов [14], необходимо оптимизировать длину холостых переходов [13], минимизировать количество точек врезки [19] и т.д.

4. Составление программы управления процессом раскроя на основе маршрута, найденного с помощью алгоритма решения абстрагированной задачи маршрутизации. Здесь выполняется обратная замена абстрактных ребер плоского графа системой команд раскройному автомату, обеспечивающей движение по кривым на плоскости, соответствующим форме вырезаемой детали.

Этапы построения раскройного плана и интерпретации найденного маршрута в терминах команд раскройному автомату являются общими для всех технологий и достаточно известны. В данной статье рассмотрены особенности реализации второго и третьего этапов для технологий ESP и ICP.

2. Абстрагирование раскройного плана до плоского графа

Моделью раскройного листа будем считать плоскость S, моделью раскройного плана – плоский граф G с внешней гранью на плоскости S. Множество вершин компонент связности графа G негомеоморфных окружности будем считать точки соприкосновения трех и более фрагментов раскройного плана, а соответствующие фрагменты ребрами, инцидентными данной вершине. Компоненту связности гомеоморфную окружности будем считать петлей. Для любой части графа обозначим через теоретико-множественное объединение его внутренних граней (объединение всех связных компонент , не содержащих внешней грани). Если считать, что режущий инструмент прошел по всем фрагментам графа J, то можно интерпретировать как отрезанную от листа часть. Множества вершин, ребер и граней графа J будем обозначать через , и соответственно, а через – число элементов множества M.

Для представления образа раскройного плана в виде плоского графа определим для каждого ребра следующие функции [18]:

- , – вершины, инцидентные ребру e;

- – грань, находящаяся справа при движении по ребру e от вершины к вершине , ;

- – ребро, инцидентное грани и , ;

- – ребро, инцидентное грани и , .

Их построение не составляет проблем. Фактически они определяются и используются еще на этапе проектирования графа G по раскройному плану. Пространственная сложность такого представления равна .

Поскольку функции , , , , построенные на ребрах графа , для каждого ребра определяют инцидентные вершины, инцидентные грани и смежные ребра, то справедливо следующее предложение.

Утверждение 1. Функции , , , построенные на ребрах графа определяют плоский граф с точностью до гомеоморфизма.

Таким образом, используя известные координаты прообразов вершин графа и размещения фрагментов раскройного плана, являющихся прообразами ребер графа , любой маршрут в графе можно интерпретировать как траекторию режущего инструмента.

Для формализации технологических ограничений на порядок резки введем определение ранга для элементов плоского графа , представленного функциями , , , .

Определение 1. Рангом ребра будем называть значение функции , определяемую рекурсивно:

- пусть – множество ребер, ограничивающих внешнюю грань графа , тогда ;

- пусть – множество ребер ранга 1 графа , тогда .

Определение 2. Рангом грани будем называть значение функции :

где – множество ребер инцидентных грани .

Определение 3. Рангом вершины будем называть значение функции : где – множество ребер инцидентных вершине .

Ранг ребра определяет его удаленность от внешней грани и показывает, какое минимальное число граней необходимо пересечь, чтобы добраться от внешней грани до этого ребра. Это позволяет для определения ранга использовать граф , топологически двойственный исходному графу : множеством вершин графа является множество F граней графа G, а ребрам графа соответствует наличие между двумя гранями границы ненулевой длины, т.е. ребра .

Для всех расстояние в графе между f и внешней гранью можно определить, построив в графе дерево кратчайших путей до вершины . Наличие в представлении графа G функций , позволяет найти функции ранга за время не превосходящее величины [10].

Поскольку вырезаемые по раскройному плану фрагменты являются прообразами граней, то требование к последовательности обхода граней, гарантирующие отсутствия необходимости резки отрезанных фрагментов, легко формализовать в терминах графа . Пусть – отношение частичного порядка на , индуцируемое деревом кратчайших путей до вершины :

Утверждение 2. Порядок обхода граней является допустимым в том и только том случае, если он является расширением частичного порядка .

3. Задачи маршрутизации в плоских графах

При построении систем управления манипуляторами с помощью неориентированного графа отображают всевозможные элементы траектории манипулятора. При этом возникают задачи построения маршрутов, удовлетворяющих различным ограничениям, например, маршрутов, в которых следующее ребро определяется заданным циклическим порядком на множестве ребер, инцидентных текущей вершине [16, 17]; маршрутов, в которых часть ребер следует пройти в заданном порядке [16]; маршрутов, удовлетворяющих условию упорядоченного охватывания (OE-маршрутов) [10].

Будем любой маршрут в плоском графе G рассматривать как часть графа, содержащую все вершины и ребра, принадлежащие маршруту. Это позволяет формализовать требование к маршруту режущего инструмента как условие отсутствия пересечения внутренних граней любой начальной части маршрута в заданном плоском графе G с ребрами его оставшейся части [15]. Такие маршруты будем называть маршрутами с упорядоченным охватыванием [12, 17] (или для краткости OE-маршрутами, где OE – от англ. «ordered enclosing»).

Определение 4. Цепь в плоском графе G имеет упорядоченное охватывание (является OE-цепью), если для любой его начальной части , выполнено условие .

В [22] доказано, что плоские эйлеровы графы имеют эйлеровы цепи, принадлежащие классу OE. Данный результат распространяется на полуэйлеровы графы, когда одна из вершин нечетной степени инцидентна внешней грани.

Указанные цепи решают задачу маршрутизации для компонент связности, являющихся эйлеровыми или полуэйлеровыми графами.

Если связный граф G не является эйлеровым и содержит 2k вершин нечетной степени, то в соответствии с теоремой Листинга-Люка возможно покрыть граф k реберно-непересекающимися цепями. Для формализации технологических требований в данном случае введем дополнительные определения.

Определение 5. Упорядоченную последовательность реберно-непересекающихся цепей

с упорядоченным охватыванием, покрывающую граф G и такую, что

будем называть покрытием с упорядоченным охватыванием (OE-покрытием).

Маршруты, которые реализуют OE-покрытие, представляют специальным образом упорядоченное множество OE-цепей и содержат дополнительные холостые переходы (ребра) между концом текущей цепи и началом последующей. Построение OE-покрытия графа G решает поставленную задачу маршрутизации [11]. Наибольший интерес представляют покрытия с минимальным числом цепей и их длиной, поскольку переход от одной цепи к другой соответствует холостому проходу режущего инструмента.

Определение 6. Минимальную по мощности упорядоченную последовательность реберно-непересекающихся цепей с упорядоченным охватыванием в плоском графе G будем называть эйлеровым покрытием с упорядоченным охватыванием (эйлеровым OE-покрытием).

Рассмотрим более подробно алгоритмы OE-маршрутизации.

3.1 Построение OE-маршрута в связном графе

Наиболее просто построить OE-маршрут для плоского эйлерова графа. Данную задачу решает алгоритм OE-Trail [10]. Доказательство результативности алгоритма имеется в работах [10] и [15], там же показано, что вычислительная сложность алгоритма не превосходит величины . Если связный граф G не является эйлеровым, то он содержит , вершин нечетной степени. В этом случае OE-маршрут будет содержать k реберно-непересекающихся цепей. Задачу построения такого маршрута решает алгоритм OE-Router [11]. Доказательство результативности алгоритма имеется в работах [11, 18, 19], там же показано, что вычислительная сложность алгоритма не превосходит величины . Недостатком алгоритма OE-Router является неоптимальность холостых перемещений между концом текущей и началом следующей цепей. Ясно, что минимальную оценку длины холостых перемещений дает длина ребер, образующих паросочетание M минимального веса на множестве вершин нечетной степени. Если плоский граф G, представляющий образ раскройного плана, является связным и не содержит мостов (т.е. ребер инцидентных единственной грани), то оказывается возможным построение OE-маршрута, в котором холстым перемещениям будут соответствовать ребра паросочетания M и только они. Задачу построения такого маршрута решает алгоритм M-OE-Router, доказательство его результативности для плоских графов без мостов имеется в работе [20], там же показано, что вычислительная сложность алгоритма не превосходит величины . Заметим, что связные плоские графы, являющихся образами раскройных планов, не содержат мостов. Следовательно, для них алгоритм M-OE-Router строит маршрут с минимальной длиной холостых переходов.

3.2. Построение OE-маршрута в несвязном графе

Зачастую раскройный план содержит детали с отверстиями, а также расположенными в этих отверстиях другими деталями, и т.д. и т.п. Плоский граф, являющийся гомеоморфным образом такого раскройного плана, будет несвязным. Решение задач маршрутизации для каждой компоненты связности с использованием методики из раздела 3.1 позволяет найти для нее циклический OE-маршрут. Ограничения на порядок обхода компонент связности определяются в соответствии с утверждением 2.

Определение 7. Грань будем называть разделяющей, если граф является несвязным.

Пусть граф получен из графа G добавлением в разделяющих гранях мостов между компонентами связности. Очевидно, что полученный граф будет плоским связным графом и для него может быть построен OE-маршрут. Искомый OE-маршрут может быть получен из маршрута если вершины, инцидентные введенным мостам, считать окончанием текущей цепи и началом следующей (т.е. введенные мосты считать холостыми перемещениями).

Рассмотрим способ построения мостов, связывающих граф G и имеющих минимальную суммарную длину.

Алгоритм Bridging

Входные данные: плоский несвязный граф G.

Выходные данные: плоский связный граф и множество B добавленных мостов.

Шаг 0. ; .

Шаг 1. Найти множество всех разделяющих граней.

Шаг 2. Для каждой разделяющей грани выполнить шаги с 3 по 6, после чего останов.

Шаг 3. Найти множество всех компонент связности графа G, инцидентных грани f.

Шаг 4. Построить полный абстрактный граф , вершинами которого являются компоненты связности , а длины ребер равны расстоянию между соответствующими компонентами.

Шаг 5. Найти остовное дерево минимального веса в .

Шаг 6. Добавить ребра найденного остовного дерева в граф : , .

Конец алгоритма Bridging.

Плоский граф , построенный алгоритмом Bridging, содержит мосты, поэтому к нему можно применить алгоритм OE-Router. Усложнением шагов 5 и 6 в алгоритме Bridging, можно сократить длину холостых перемещений за счет использования алгоритма M-OE-Router. Действительно, если в абстрактном графе вместо остовного дерева минимального веса использовать гамильтонов цикл минимального веса, то результирующий граф не будет содержать мостов и применение к нему алгоритма M-OE-Router даст OE-маршрут с минимальной длиной холостых перемещений.

Заключение

Изложенные в работе математические модел и алгоритмы задачи маршрутизации в плоских графах решают задачу определения допустимой последовательности резки по раскройному плану при использовании технологий ECP и ICP допускающих возможность совмещения границ вырезаемых деталей. Их применение позволяет сократить расход материала, длину горячей резки, и длину холостых проходов.

Литература

1. Канторович Л.В., Залгаллер В.А. Рациональный раскрой промышленных материалов. - СПб.: Невский Диалект, 2012. – 304 с., ил., табл.

2. Филиппова А.С. Обзор методов решения задач раскроя-упаковки уфимской научной школы Э.А. Мухачевой // Статистика. Моделирование. Оптимизация/ сборник трудов Всероссийской конференции (Челябинск, 28 ноября – 3 декабря 2011 г.). – Челябинск: Издательский центр ЮУрГУ, 2011. С.~73--85.

3. Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометрического проектирования. Киев. – Наукова думка. 1986. – 268 с.

4. Картак В.М. Задача упаковки прямоугольников: точный алгоритм на базе матричного представления // Вестник УГАТУ, сер. «Управление, вычислительная техника и информатика». 2007. Т. 9. No. 4(22), C. 104–110.

5. Петунин А.А., Ченцов А.Г., Ченцов П.А. К вопросу о маршрутизации движения инструмента в машинах листовой резки с числовым программным управлением / Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. Сер. «Информатика. Телекоммуникации. Управление». 2013. No. 169. C. 103–111.

6. Dewil, R., Vansteenwegen, P., Cattrysse, D., Laguna, M., Vossen, T. An improvement heuristic framework for the laser cutting tool path problem // International Journal of Production Research, 2015. Volume 53, Issue 6, Pages 1761–1776.

7. EURO Special Interest Group on Cutting and Packing // http://www.fe.up.pt/esicup

8. Hoeft J., Palekar U.S. Heuristics for the plate-cutting travelling salesman problem // IIE Transactions, 1997, no.29(9), P. 719–731.

9. Верхотуров М.А., Тарасенко П.Ю. Математическое обеспечение задачи оптимизации пути режущего инструмента при плоском фигурном раскрое на основе цепной резки// Вестник УГАТУ, «Управление, вычислительная техника и информатика». 2008. Т. 10, No. 2(27). – С. 123–130.

10. Panyukov, A.V. The Algorithm for Tracing of Flat Euler Cycles with Ordered Enclosing / A.V. Panyukov, T.A. Panioukova // Proceedings of Chelyabinsk Scientific Center, 2000. – No. 4(9). – P. 18–22. http://elibrary.ru/item.asp?id=1614035

11. Panyukova, T. Eulerian Cover with Ordered Enclosing for Flat Graphs / T. Panyukova // Electronic Notes in Discrete Mathematics. – 2007. – Vol. 28. – P. 17–24.

12. Panyukova T. Chain sequences with ordered enclosing. – Journal of Computer and System Sciences International, 2007, Vol. 46, No. 1; 10. – pp. 83–92.

13. Панюкова Т.А. Оптимизация использования ресурсов при технологической подготовке процесса раскроя // Т.А. Панюкова / Прикладная информатика. – No. 3(39), 2012. – С.20–32.

14. Фляйшнер, Г. Эйлеровы графы и смежные вопросы / Г. Фляйшнер. – М.: Мир, 2002. – 335 с., ил.

15. Panioukova, T.A. Algorithms for Construction of Ordered Enclosing Traces in Planar Eulerian Graphs / T.A. Panioukova, A.V. Panyukov // The International Workshop on Computer Science and Information Technologies' 2003, Proceedings of Workshop, Ufa, September 16–18, 2003/ Ufa State Technical University. – Ufa, 2003. – Vol. 1. – Р. 134–138.

16. Fleichner, H. Eulerian Graphs / H. Fleischner, L.W. Beineke, R.J. Wilson // Selected Topics in Graph Theory 2, Academic Press, London-NewYork, 1983. – P. 17–53.

17. Fleischner H. Eulerian Graphs and Related Topics / H. Fleischner. – Part 1, Vol.2 – Ann. Discrete Mathematics, 1991. – No. 50.

18. Панюкова Т.А. Последовательности цепей с упорядоченным охватыванием // Известия Академии наук. Теория и системы управления. 2007. No. 1. С. 88–97.

19. Панюкова Т.А. Цепи с упорядоченным охватыванием в плоских графах// Дискретный анализ и исследование операций. Новосибирск: Часть 2. 2006. Т.13, No. 2, С. 31–43.

20. Панюкова, Т.А. Оптимальные эйлеровы покрытия для плоских графов / Т.А.~Панюкова // Дискретный анализ и исследование операций. 2011. – Т.~18, No. 2. – C. 64–74.