Тема: Разработка алгоритмов оптимальной маршрутизации инструмента для САПР управляющих программ машин листовой резки с ЧПУ

Актуальность темы исследования. Современное производство предъявляет высокие требования к качеству заготовок и технико-экономическому уровню выпускаемой продукции, что приводит к увеличению затрат на проектирование и технологическую подготовку производства. Раскройно-заготовительные операции, являясь началом большинства производственных процессов, оказывают существенное влияние на трудоемкость и экономичность изготовления деталей. Для получения заготовок сложной геометрической формы из листового материала в условиях мелкосерийного и единичного производства широко применяются машины фигурной резки с числовым программным управлением (ЧПУ). Использование оборудования с ЧПУ, предполагает применение средств автоматизации проектирования управляющих программ (CAM-систем). При использовании современных CAD/CAM систем, предназначенных для автоматизированного проектирования раскроя и подготовки управляющих программ (далее — УП) для оборудования с ЧПУ, возникает несколько различных взаимосвязанных задач, поэтому обычно проектирование УП для технологического оборудования листовой резки состоит из нескольких этапов. Первый этап предполагает предварительное геометрическое моделирование заготовок и разработку раскройной карты, здесь возникает известная задача оптимизации фигурного раскроя листового материала, которая относится к классу трудно решаемых проблем раскроя-упаковки (Cutting &Packing). На следующем этапе проектирования УП осуществляется процесс назначения маршрута резки — траектории перемещения режущего инструмента для полученного на первом этапе варианта раскроя, здесь возникают актуальные научно-практические задачи оптимизации маршрута режущего инструмента. Их целью обычно является минимизация стоимости и / или времени процесса резки, связанного с обработкой требуемых контуров деталей из листового материала, за счет определения оптимальной последовательности вырезки контуров и выбора необходимых точек для врезки в материал листа, а также направления движения резака с учетом технологических ограничений процесса резки. Следует отметить, что современные специализированные САПР предоставляют базовый инструментарий для решения задач рационального раскроя материалов и подготовки УП для технологического оборудования листовой резки с ЧПУ. Вместе с тем разработчики систем автоматизированного проектирования УП для оборудования листовой резки с ЧПУ не уделяют должного внимания проблеме оптимизации маршрута резки. Существующее программное обеспечение САПР не гарантирует получение оптимальных траекторий перемещения инструмента при одновременном соблюдении технологических требований резки. Зачастую пользователи САПР используют интерактивный режим проектирования УП. Кроме того, отсутствуют способы оценки точности полученных решений. В связи с этим актуальным направлением исследования являются вопросы разработки и применения эвристических и метаэвристических подходов, а также точных алгоритмов, которые позволяют получить решение задачи оптимальной маршрутизации режущего инструмента в режиме автоматического проектирования за приемлемое время и обеспечивают при этом эффективные оценки результатов проектирования.
Степень разработанности темы исследования. Методы проектирования технологических процессов раскройно-заготовительного производства исследовались в работах как отечественных так и зарубежных ученых.
Разработкой алгоритмов для маршрутизации инструмента машин листовой резки с ЧПУ занимались, в частности, следующие российские исследователи: М.А. Верхотуров, Т.А. Макаровских, Р.Т. Мурзакаев, А.А. Петунин, А.Г. Ченцов, П.А. Ченцов, В.Д. Фроловский, М.Ю. Хачай, А.Ф. Таваева и др., а также зарубежные исследователи: E. Arkin, N. Ascheuer, D. Cattrysse, R. Dewil, L. Gambardella, J. Hoeft, Y. Jing, Y. Kim , M. Lee, S.U. Sherif, W. Yang и др. В подавляющем большинстве работ используется дискретизация граничных контуров деталей, что позволяет применять хорошо разработанные математические модели дискретной оптимизации. Можно отметить только отдельные публикации, где оптимизационные алгоритмы ориентированы на поиск решений в непрерывных множествах.
Задачи маршрутизации инструмента машин листовой резки с ЧПУ относятся, как известно, к NP-трудным задачам. Следует отметить, что до настоящего времени не существует единой математической модели проблемы оптимизации траектории инструмента для технологического оборудования листовой резки с ЧПУ. Имеются отдельные группы ученых, которые занимаются исследованием частных случаев этой проблемы. Кроме того, в рамках CAD/CAM систем, предназначенных для проектирования УП для машин листовой резки с ЧПУ, есть отдельные модули, которые позволяют решать в автоматическом режиме некоторые оптимизационные задачи, например минимизацию холостого хода инструмента, однако при этом не обеспечивают соблюдение технологических требований резки материала на машинах с ЧПУ и не позволяют получать маршруты резки, близкие к оптимальным с точки зрения критериев стоимости и времени резки с учетом рабочего хода инструмента, затрат на врезку и т.д. К тому же, реализованные в коммерческом программном обеспечении алгоритмы как правило не описываются в научной литературе.
В общей проблеме маршрутизации инструмента машин листовой резки с ЧПУ можно выделить несколько классов задач: задача непрерывной резки (CCP), задача резки с конечными точками (ECP), задача прерывистой резки (ICP), задача обхода многоугольников (TPP), задача коммивояжера (TSP) и обобщенная задача коммивояжера (GTSP). Любая задача оптимизации термической резки может рассматриваться как ICP, тем не менее, литература по ICP очень скудна, и большинство программных и научных статей вводят искусственные ограничения, которые упрощают ICP до задач других классов. Поиск хороших алгоритмов оптимизации с эффективными оценками точности для нескольких подклассов задачи ICP мог бы заполнить явный существующий пробел в исследованиях. В частности, отметим, что актуальна разработка алгоритмов для подкласса Segment CCP, базирующегося на понятии «сегмента резки».
Применение эффективных классических метаэвристических алгоритмов дискретной оптимизации (метод ветвей и границ, метод эмуляции отжига, метод муравьиной колонии, эволюционные алгоритмы, метод переменных окрестностей и др.) для дискретных моделей оптимизации траектории инструмента машин с ЧПУ возможно только при адаптации этих алгоритмов к требованиям технологических ограничений листовой резки. Таким образом, необходимость в создании специализированных оптимизационных алгоритмов и программного обеспечения для САПР управляющих программ машин листовой резки с ЧПУ остается доминантой развития методов решения исследуемой оптимизационной проблемы маршрутизации инструмента.
Цель работы заключается в разработке алгоритмов решения задачи оптимальной маршрутизации режущего инструмента и методик применения данных алгоритмов в системах автоматизированного проектирования УП для машин термической резки с ЧПУ. Для достижения поставленной в работе цели необходимо решить следующие задачи:
— Разработать точный алгоритм решения обобщённой задачи коммивояжера с ограничениями предшествования (PCGTSP), позволяющий оценивать качество решений на основе вычисления нижней оценки
— Разработать эвристики поиска оптимального положения точек врезки в контур детали и последовательности обхода контуров в процессе решения задач непрерывной резки (CCP, SCCP)
— Разработать программное обеспечение, реализующее разработанные алгоритмы
— Разработать схемы информационного обмена и методику использования алгоритмов оптимальной маршрутизации режущего инструмента в CAD/CAM-системах при автоматическом проектировании управляющих программ машин листовой резки с ЧПУ.
Научная новизна результатов:
1. Разработан алгоритм ветвей и границ для обобщенной задачи коммивояжера с ограничениями предшествования PCGTSP, позволяющий строить нижние оценки для решений указанной задачи, в том числе, полученных другими алгоритмами и эвристиками. Этот алгоритм способен находить точные решения для задач значительно большей размерности, чем известные алгоритмы (до ~ 150 кластеров в зависимости от уровня вложенности).
2. Разработаны алгоритм поиска точек врезки в контуры, не использующий механизм дискретизации, а также схема выбора последовательности резки контуров на основе метода переменных окрестностей, совместно решающие задачи CCP и SCCP.
3. Сформулированы схемы использования ограничений предшествования для уменьшения вычислительной сложности алгоритмов оптимальной маршрутизации, как в моделях дискретной, так и непрерывной оптимизации.
Теоретическая и практическая значимость работы:
1. Разработанные алгоритмы могут применяться для автоматического проектирования УП машин листовой резки с ЧПУ. Для ряда задач впервые удалось получить эффективные оценки точности решений.
2. Использование непрерывных моделей оптимизации позволяет уменьшить длину холостого хода (в некоторых случаях — до 10%) по сравнению с используемыми в настоящее время дискретными моделями.
3. Разработанные алгоритмы могут применяться для решения более общей задачи маршрутизации резки, например обобщённой сегментной резки 0800?.
4. Разработанные схемы информационного обмена, форматы файлов и методика использования алгоритмов оптимальной маршрутизации инструмента позволяют интегрировать разработанное программное обеспечение в существующие российские САПР «Сириус» и САПР «Т-Р1ех»
Работа выполнена при финансовой поддержке Министерства науки и высшего образования РФ (государственный контракт № 075-03-2020-582/4).
Результаты исследований используются в учебном процессе ФГАОУ ВО «Уральский федеральный университет имени первого Президента России Б. Н. Ельцина».
Методология и методы исследования. Методологическую базу исследования составили фундаментальные и прикладные работы отечественных и зарубежных ученых в области автоматизированного проектирования маршрута резки для машин листовой резки с ЧПУ, геометрического моделирования, разработки алгоритмов оптимальной маршрутизации, методы вычислительной геометрии и компьютерной графики. В качестве инструментов исследования использовались следующие методы: анализ, синтез, классификация, формализация, математические методы обработки данных. Оценка эффективности предложенных методов и алгоритмов осуществлялась с помощью вычислительных экспериментов на различных раскройных картах и тестовых примерах. Проводилось их сравнение с результатами, полученными при работе алгоритмов других авторов.
Положения, выносимые на защиту:
1. Точный алгоритм решения обобщённой задачи коммивояжера с ограничениями предшествования (Р00Т8Р) с обновлением нижней границы.
2. Эвристика поиска точек врезки в плоские контура, не использующая дискретизацию контура.
3. Достаточные условия, при которых полученный маршрут доставляет глобальный минимум длины холостого хода инструмента.
4. Форматы файлов и схемы для обмена геометрической и маршрутной информацией и визуализации для использования алгоритмов оптимальной маршрутизации в CAD/CAM-системах.
Достоверность результатов диссертационной работы подтверждается результатами экспериментальных исследований, приведенными в ряде публикаций и полученными при использовании методик, алгоритмов и программных средств, созданных при непосредственном участии соискателя. Основные положения диссертации были представлены на международных и всероссийских научных конференциях, опубликованы в изданиях ВАК, Scopus, WoS, известны в научном сообществе и положительно оценены специалистами.
Апробация результатов работы. Основные результаты работы докладывались и обсуждались на всероссийских и международных конференциях, в том числе:
— Applications of Mathematics in Engineering and Economics (AMEE’16), Созополь, Болгария, 08.06.2016 - 13.06.2016.
— Manufacturing, Modelling, Management & Control, (8th MiM 2016) Труа, Франция, 28.06.2016 - 30.06.2016.
— ASRTU 2017 International Conference on Intellectual Manufacturing,Харбин, Китайская Народная Республика, 15.06.2017 - 18.06.2017.
— Mathematical Optimization Theory And Operations Research (MOTOR 2019), Екатеринбург, Россия, 08.07.2019 - 12.07.2019.
— Manufacturing Modelling, Management and Control, (9th MiM 2019) Берлин, Германия, 28.08.2019 - 30.08.2019.
— X Всероссийская конференция «Актуальные проблемы прикладной математики и механики» с международным участием, посвященная памяти академика А.Ф.Сидорова и 100-летию Уральского федерального университета, пос. Абрау-Дюрсо, Россия, 01.09.2020 - 06.09.2020.
— ICPR International Workshops and Challenges Virtual Event, Milan, Italy, 10.01.2021 - 15.01.2021.
— XVI Всероссийская научно-практическая конференция «Перспективные системы и задачи управления», Домбай, Россия, 5.04.2021 - 9.04.2021. 
Точка выключения инструмента
Направление резки
Рис. 1 - Элементы маршрута резки
- XII International Conference Optimization and Applications (OPTIMA-2021), Petrovac, Черногория, 27.09.2021 - 1.10.2021.
— XIV-я Всероссийская Мультиконференция по проблемам управления, с. Дивноморское, Геленджик, Россия, 27.09.2021 - 02.10.2021.
Личный вклад автора состоит в проведении теоретических и экспериментальных исследований по теме диссертационной работы, проведении аналитических расчетов на основе полученных результатов. В опубликованных совместных работах постановка и разработка алгоритмов для решения задач осуществлялись совместными усилиями соавторов при непосредственном активном участии соискателя.
По теме диссертационной работы произведено 18 публикаций, в том числе 9 научных работ в рецензируемых научных журналах, определенных ВАК РФ и Аттестационным советом УрФУ, из них 8 публикаций проиндексировано в международных базах данных WoS и Scopus.
Объем и структура работы. Диссертация состоит из введения, 4 глав, заключения и 4 приложений. Полный объем диссертации составляет 135 страниц, включая 24 рисунка и 7 таблиц. Список литературы содержит 121 наименование.

Купить

В соответствии с целью и задачами исследования получены следующие научные и практические результаты:
1. Разработан алгоритм ветвей и границ для точного решения обобщённой задачи коммивояжёра с ограничениями предшествования. Он может быть реализован в классической схеме, а также в парадигме динамического программирования, при этом он допускает распараллеливание и демонстрирует лучшую производительность.
2. Предложенный алгоритм способен находить точные решения для задач большего размера, чем известные алгоритмы. В проведённых экспериментах было найдено решение для задачи со 151 кластером.
3. Данный алгоритм также решает важную задачу оценки качества решений, в том числе полученных другими алгоритмами.
4. Разработана схемы эффективного учёта ограничений предшествования для задач маршрутизации как в дискретной, так и в непрерывной схеме оптимизации.
5. Разработана основанная на геометрических соображениях эвристика оптимального размещения точек врезки на плоских контурах.
6. Доказано, что данная эвристика доставляет локальный минимум длины холостого хода и сформулированы два набора достаточных условий того, что полученное решение является глобальным минимумом.
7. Разработанные алгоритмы могут использоваться для решения задач сегментной непрерывной резки (SCCP и GSCCP) тем самым открывая подход к решению общей задачи прерывистой резки (ICP)
8. Разработаны форматы данных и алгоритмические схемы для обмена геометрической и маршрутной информацией и визуализации для использования в CAD/CAM-системах, а также алгоритмы преобразования формата файлов, что позволило интегрировать разработанное ПО с САПР «Сириус» и T-Flex CAD.
9. Предложенные схемы информационного обмена позволяют интегрировать в одну подсистему автоматического проектирования маршрутов резки существующие алгоритмы оптимизации, включая алгоритмы, использующие схему непрерывной оптимизации.
10. Разработано программное обеспечение для реализации всех алгоритмов на языках C, Python и JavaScript.
Перспективы дальнейшей разработки темы. Можно выделить следующие направления дальнейшего развития и совершенствования алгоритмического и программного обеспечения САПР УП для оборудования листовой фигурной резки с ЧПУ:
1. Разработка методов получения нижних оценок для частичных подзадач GTSP; например, за счёт более точного учёта расстояний между узлами, а не только между кластерами.
2. Разработка метаэвристических алгоритмов дискретной оптимизации в задачах непрерывной резки (CCP, SCCP) и оценка производительности и качества получаемых алгоритмов.
3. Учет технологических требований термической резки для разработанных в данной диссертационной работе алгоритмов.
4. Интеграция разработанных алгоритмов с отечественными САПР для проектирования УП машин листовой резки

Купить