
Тип работы:	Предмет:	Язык работы:

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

Работа №	102772
Тип работы	Диссертации (РГБ)
Предмет	информационные системы
Объем работы	135
Год сдачи	2021
Стоимость	4235 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено	170

Не подходит работа?

Узнай цену на написание

Содержание

Введение 5
Глава 1. Задача оптимизации маршрута режущего инструмента для машин листовой резки с ЧПУ. Анализ современного состояния проблемы исследования 13
1.1. Основные понятия 13
1.2. Формализация общей задачи маршрутизации режущего инструмента 17
1.3. Технологические ограничения современных машин листовой
резки с ЧПУ 23
1.3.1. Позиции точек врезки и выключения инструмента .... 23
1.3.2. Условия предшествования 24
1.3.3. Эвристические правила термической резки заготовок из
листовых материалов 25
1.4. Классификация задач маршрутизации инструмента машин листовой резки 29
1.5. Современное состояние проблемы исследования и применение
алгоритмов маршрутизации для автоматизированного проектирования управляющих программ 31
1.6. Выводы по Главе 1 33
Глава 2. Разработка алгоритмов маршрутизации инструмента на основе дискретных оптимизационных моделей 35
2.1. Использование модели обобщенной задачи коммивояжера с
ограничениями предшествования РССТБР для формализации задачи маршрутизации 35
2.2. Общие соображения 38
2.2.1. Получение нижних оценок 39
2.2.2. Отсечение 44
2.2.3. Ветвление 45
2.2.4. Обновление нижней оценки 46
2.2.5. Точное решение 47
2.3. Алгоритм ветвей и границ 48
2.4. Динамическое программирование 49
2.5. Численные эксперименты 53
2.6. Выводы по Главе 2 56
Глава 3. Применение непрерывно-дискретных оптимизационных моделей маршрутизации в эвристических алгоритмах решения задачи непрерывной резки CCP 59
3.1. Постановка задачи CCP 59
3.2. Алгоритмы решения задачи непрерывной резки 60
3.2.1. О приеме удаления «внешних» контуров для сокращения
трудоемкости решения 60
3.2.2. Поиск траектории перемещения инструмента для случая
непрерывной модели описания геометрии контуров 61
3.2.3. Алгоритмы комбинаторной оптимизации построения
маршрута 62
3.3. Численные эксперименты 70
3.4. Обобщение на задачи сегментной резки SCCP / GSCCP 78
3.4.1. Общая схема решения задачи GSCCP 80
3.5. Выводы по Главе 3 81
Глава 4. Методология использования алгоритмов решения задачи оптимальной маршрутизации режущего инструмента в CAD/CAM-системах 83
4.1. Использование открытых форматов файлов данных для
взаимодействия подсистем 83
4.1.1. Выбор открытого формата представления
геометрической информации 84
4.1.2. Разработка спецификаций JSON 87
4.1.3. Разработка конвертеров форматов файлов данных .... 88
4.2. Визуализация геометрической информации 89
4.2.1. Настройка параметров визуализации 91
4.2.2. Организация пользовательского интерфейса 92
4.3. Выводы по Главе 4 94
Заключение 95
Список основных сокращений 97
Список литературы 99
Список иллюстраций 112
Список таблиц 113
Приложение А. Документы о внедрении результатов диссертационного исследования 114
Приложение Б. Основные формулы геометрии дуг на комплексной плоскости 115
Приложение В. Описание формата файлов DBS 120
Приложение Г. JSON-схемы 127
Г.1. Сведения о геометрии деталей и раскроя 127
Г.2. Задание на резку 128
Г.3. Результат резки 131

Введение

Актуальность темы исследования. Современное производство предъявляет высокие требования к качеству заготовок и технико-экономическому уровню выпускаемой продукции, что приводит к увеличению затрат на проектирование и технологическую подготовку производства. Одним из направлений повышения эффективности использования производственных ресурсов является совершенствование безотходных технологий в металлообрабатывающих производствах и возрастание степени их автоматизации.
Раскройно-заготовительные операции, являясь началом большинства производственных процессов, оказывают существенное влияние на трудоемкость и экономичность изготовления деталей. Для получения заготовок сложной геометрической формы из листового материала в условиях мелкосерийного и единичного производства широко применяются машины фигурной резки с числовым программным управлением (ЧПУ). К данному типу оборудования относятся станки газовой, лазерной, плазменной, электроэрозионной и гидроабразивной резки металла. Станки листовой резки имеют множество преимуществ: возможность обработки многих видов материалов различной толщины, высокая скорость резки, возможность обработки контуров различной сложности, адаптация к постоянным изменениям номенклатуры выпускаемой продукции. Использование оборудования с ЧПУ, предполагает применение средств автоматизации проектирования управляющих программ (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, базирующегося на понятии «сегмента резки».
В целом можно отметить, что за рамками исследований отечественных и зарубежных коллег остаются следующие принципиальные моменты: разработка алгоритмов, обеспечивающих получение глобального оптимума оптимизационной задачи маршрутизации инструмента; учет тепловых искажений заготовок при термической резке с целевыми функциями стоимости и времени резки, что приводит к не технологичным решениям и искажению геометрии получаемых заготовок; рассмотрение задач маршрутизации из класса ICP, в частности, и задач с набором возможных точек врезки из континуального множества, включая мульти-контурные множества.
Применение эффективных классических метаэвристических алгоритмов дискретной оптимизации (метод ветвей и границ, метод эмуляции отжига, метод муравьиной колонии, эволюционные алгоритмы, метод переменных окрестностей и др.) для дискретных моделей оптимизации траектории инструмента машин с ЧПУ возможно только при адаптации этих алгоритмов к требованиям технологических ограничений листовой резки. Таким образом, необходимость в создании специализированных оптимизационных алгоритмов и программного обеспечения для САПР управляющих программ машин листовой резки с ЧПУ остается доминантой развития методов решения исследуемой оптимизационной проблемы маршрутизации инструмента.
Цель работы заключается в разработке алгоритмов решения задачи оптимальной маршрутизации режущего инструмента и методик применения данных алгоритмов в системах автоматизированного проектирования УП для машин термической резки с ЧПУ. Для достижения поставленной в работе цели необходимо решить следующие задачи:
— Разработать точный алгоритм решения обобщённой задачи коммивояжера с ограничениями предшествования (PCGTSP), позволяющий оценивать качество решений на основе вычисления нижней оценки
— Разработать эвристики поиска оптимального положения точек врезки в контур детали и последовательности обхода контуров в процессе решения задач непрерывной резки (CCP, SCCP)
— Разработать программное обеспечение, реализующее разработанные алгоритмы
— Разработать схемы информационного обмена и методику использования алгоритмов оптимальной маршрутизации режущего инструмента в CAD/CAM-системах при автоматическом проектировании управляющих программ машин листовой резки с ЧПУ.
Научная новизна результатов.
1. Разработан алгоритм ветвей и границ для обобщенной задачи коммивояжера с ограничениями предшествования PCGTSP, позволяющий строить нижние оценки для решений указанной задачи, в том числе, полученных другими алгоритмами и эвристиками. Этот алгоритм способен находить точные решения для задач значительно большей размерности, чем известные алгоритмы (до ~ 150 кластеров в зависимости от уровня вложенности).
2. Разработаны алгоритм поиска точек врезки в контуры, не использующий механизм дискретизации, а также схема выбора последовательности резки контуров на основе метода переменных окрестностей, совместно решающие задачи CCP и SCCP.
3. Сформулированы схемы использования ограничений предшествования для уменьшения вычислительной сложности алгоритмов оптимальной маршрутизации, как в моделях дискретной, так и непрерывной оптимизации.
Теоретическая и практическая значимость работы
1. Разработанные алгоритмы могут применяться для автоматического проектирования УП машин листовой резки с ЧПУ. Для ряда задач впервые удалось получить эффективные оценки точности решений.
2. Использование непрерывных моделей оптимизации позволяет уменьшить длину холостого хода (в некоторых случаях — до 10%) по сравнению с используемыми в настоящее время дискретными моделями.
3. Разработанные алгоритмы могут применяться для решения более общей задачи маршрутизации резки, например обобщённой сегментной резки СБССР.
4. Разработанные схемы информационного обмена, форматы файлов и методика использования алгоритмов оптимальной маршрутизации инструмента позволяют интегрировать разработанное программное обеспечение в существующие российские САПР «Сириус» и САПР «Т-Р1ех»
5. Работа выполнена при финансовой поддержке Министерства науки и высшего образования РФ (государственный контракт № 075-03-2020-582/4).
6. Результаты исследований используются в учебном процессе ФГАОУ ВО «Уральский федеральный университет имени первого Президента России Б. Н. Ельцина»
Методология и методы исследования. Методологическую базу исследования составили фундаментальные и прикладные работы отечественных и зарубежных ученых в области автоматизированного проектирования маршрута резки для машин листовой резки с ЧПУ, геометрического моделирования, разработки алгоритмов оптимальной маршрутизации, методы вычислительной геометрии и компьютерной графики. В качестве инструментов исследования использовались следующие методы: анализ, синтез, классификация, формализация, математические методы обработки данных. Оценка эффективности предложенных методов и алгоритмов осуществлялась с помощью вычислительных экспериментов на различных раскройных картах и тестовых примерах. Проводилось их сравнение с результатами, полученными при работе алгоритмов других авторов.
Положения, выносимые на защиту:
1. Точный алгоритм решения обобщённой задачи коммивояжера с ограничениями предшествования (РССТБР) с обновлением нижней границы.
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.
— XII International Conference Optimization and Applications (OPTIMA- 2021), Petrovac, Черногория, 27.09.2021 - 1.10.2021.
— XIV-я Всероссийская Мультиконференция по проблемам управления, с. Дивноморское, Геленджик, Россия, 27.09.2021 - 02.10.2021.
Личный вклад автора состоит в проведении теоретических и экспериментальных исследований по теме диссертационной работы, проведении аналитических расчетов на основе полученных результатов. В опубликованных совместных работах постановка и разработка алгоритмов для решения задач осуществлялись совместными усилиями соавторов при непосредственном активном участии соискателя.
По теме диссертационной работы опубликовано 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. Balas E. Linear Time Dynamic-Programming Algorithms for New Classes of Restricted TSPs: A Computational Study / E. Balas, N. Simonetti // INFORMS J. on Computing. — Institute for Operations Research, the Management Sciences (INFORMS), Linthicum, Maryland, USA, 2001. — Т. 13, № 1. — С. 56—75. — URL: http: //dx. doi . org/10.1287/ijoc.13.1.56.9748.
2. Arkin E. M. Approximation algorithms for the geometric covering salesman problem / E. M. Arkin, R. Hassin // Discrete Applied Mathematics. — 1994. — Т. 55, № 3. — С. 197—218.
3. Cascading Style Sheets. — URL: https://www.w3.org/Style/CSS/.
4. Castelino K. Toolpath optimization for minimizing airtime during machining / K. Castelino, R. D’Souza, P. K. Wright // Journal of Manufacturing Systems. — 2003. — Т. 22, № 3. — С. 173—180. — URL: http://www.sciencedirect.com/science/article/pii/S0278612503900185.
5. Chentsov A. G. A Discrete-Continuous Routing Problem with Precedence Constraints / A. G. Chentsov, A. A. Chentsov // Proceedings of the Steklov Institute of Mathematics. — 2018. — Т. 300, № 1. — С. 56—71.
6. Chentsov A. G. An exact algorithm with linear complexity for a problem of visiting megalopolises / A. G. Chentsov, M. Y. Khachai, D. M. Khachai // Proceedings of the Steklov Institute of Mathematics. — 2016. — Т. 295, № 1. — С. 38—46. — URL: https://doi.org/10.1134/S0081543816090054.
7. Chentsov A. Linear time algorithm for Precedence Constrained Asymmetric Generalized Traveling Salesman Problem / A. Chentsov, M. Khachay, D. Khachay // IFAC-PapersOnLine. — 2016. — Т. 49, № 12. — С. 651— 655. — URL: http://www.sciencedirect.com/science/article/pii/S2405896316310485 ; 8th IFAC Conference on Manufacturing Modelling, Management and Control MIM 2016.
8. Chentsov A. G. Model of megalopolises in the tool path optimisation for CNC plate cutting machines / A. G. Chentsov, P. A. Chentsov, A. A. Petunin, A. N. Sesekin // International Journal of Production Research. — 2018. — Т. 56, № 14. — С. 4819—4830.
9. CoffeeScript: a little language that compiles into JavaScript. — URL: https://coffeescript.org/.
10. Dewil R. A Critical Review of Multi-hole Drilling Path Optimization / R. Dewil, i. Kiiciikoglu, C. Luteyn, D. Cattrysse // Archives of Computational Methods in Engineering. — 2019. — T. 26, № 2. — C. 449—459. — URL: https://doi.org/10.1007/s11831-018-9251-x.
11. Dewil R. A review of cutting path algorithms for laser cutters / R. Dewil, P. Vansteenwegen, D. Cattrysse // International Journal of Advanced Manu¬facturing Technology. — 2016. — T. 87, № 5. — C. 1865—1884.
12. Dewil R. Construction heuristics for generating tool paths for laser cutters / R. Dewil, P. Vansteenwegen, D. Cattrysse // International Journal of Production Research. — 2014. — T. 52, № 20. — C. 5965—5984.
13. Dewil R. Sheet Metal Laser Cutting Tool Path Generation: Dealing with Overlooked Problem Aspects. T. 639 / R. Dewil, P. Vansteenwegen, D. Cattrysse. — Trans Tech Publications Ltd, 2015.
14. Dewil R. An improvement heuristic framework for the laser cutting tool path problem / R. Dewil, P. Vansteenwegen, D. Cattrysse, M. Laguna, T. Vossen // International Journal of Production Research. — 2015. — T. 53, № 6. — C. 1761—1776.
15. Dror M. Touring a sequence of polygons / M. Dror, A. Efrat, A. Lubiw, J. S. Mitchell // Proceedings of the thirty-fifth annual ACM symposium on Theory of computing. — ACM. 2003. — C. 473—482.
16. DXF Specifications. — 2012. — URL: http://images.autodesk.com/adsk/files/autocad_2012_pdf_dxf-reference_enu.pdf.
17. Extensible Markup Language (XML). — URL: https://www.w3.org/XML/.
18. Ezzat A. A bare-bones ant colony optimization algorithm that performs competitively on the sequential ordering problem / A. Ezzat, A. M. Abdelbar, D. C. Wunsch // Memetic Computing. — 2014. — T. 6, № 1. — C. 19—29.
19. Feremans C. The geometric generalized minimum spanning tree problem with grid clustering / C. Feremans, A. Grigoriev, R. Sitters // 4OR. — 2006. —
T. 4, № 4. — C. 319—329. — URL: https://doi.org/10.1007/s10288-006-0012-6.
20. Fischetti M. A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem / M. Fischetti, J. J. S. Gonzalez, P. Toth // Operations Research. — 1997. — T. 45, № 3. — C. 378—394.
21. Frolovsky V. D. Constructing the Shortest Closed Tour on a Set of Line Seg¬ments Using Ant Colony approach / V. D. Frolovsky, N. D. Ganelina. —.
22. Gendreau M. Handbook of metaheuristics. T. 2 / M. Gendreau, J.-Y. Potvin [H gp.]. — Springer, 2010.
23. Ghilas V. An adaptive large neighborhood search heuristic for the Pickup and Delivery Problem with Time Windows and Scheduled Lines / V. Ghilas, E. Demir, T. Van Woensel // Computers & Operations Research. — 2016. —
T. 72. — C. 12—30.
24. Gutin G. A Memetic Algorithm for the Generalized Traveling Salesman Problem / G. Gutin, D. Karapetyan // Natural Computing. — 2010. — T. 9, № 1. — C. 47—60.
25. Hansen P. Variable neighbourhood search: methods and applications / P. Hansen, N. Mladenovic, J. A. Moreno Perez // Annals of Operations Research. — 2010. — T 175, № 1. — C. 367—407.
26. Held M. A Dynamic Programming Approach to Sequencing Problems / M. Held, R. M. Karp // Journal of the Society for Industrial and Applied Mathematics. — 1962. — T. 10, № 1. — C. 196—210. — URL: http://www.jstor.org/stable/2098806.
27. Helsgaun K. Solving the equality Generalized Traveling Salesman Problem using the Lin-Kernighan-Helsgaun Algorithm / K. Helsgaun // Mathematical Programming Computation. — 2015. — T. 7, № 3. — C. 269—287.
28. Hoeft J. Heuristics for the plate-cutting traveling salesman problem / J. Hoeft,
U. S. Palekar // IIE Transactions. — 1997. — T. 29, № 9. — C. 719—731.
29. IEEE Standard for Floating-Point Arithmetic. — 2019. — URL: https : //ieeexplore.ieee.org/document/8766229.
30. Imahori S. Generation of cutter paths for hard material in wire EDM / S. Imahori, M. Kushiya, T. Nakashima, K. Sugihara // Journal of Materials Processing Technology. — 2008. — T. 206, № 1. — C. 453—461.
31. Introducing JSON. — URL: https://www.json.org/.
32. JavaScript - MDN Web Docs - Mozilla. — URL: https : / /developer .mozilla.org/ru/docs/Web/JavaScript.
33. JavaScript library that enables panning and zooming of an SVG in an HTML document, with mouse events or custom JavaScript hooks. — URL: https ://github.com/bumbu/svg-pan-zoom.
34. JSON for Humans, superset of JSON that aims to alleviate some of the limitations of JSON by expanding its syntax to include some productions from ECMAScript 5.1. — URL: https://json5.org/.
35. Kandasamy V. A. Effective location of micro joints and generation of tool path using heuristic and genetic approach for cutting sheet metal parts /
V. A. Kandasamy, S. Udhayakumar // International Journal of Material Forming. — 2020. — Т. 13, № 2. — С. 317—329.
36. Karapetyan D. Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem / D. Karapetyan, G. Gutin // European Journal of Operational Research. — 2012. — Т. 219, № 2. — С. 234—251. — URL: https://www.sciencedirect.com/science/article/pii/S0377221712000288.
37. Karapetyan D. Lin-Kernighan heuristic adaptations for the generalized traveling salesman problem / D. Karapetyan, G. Gutin // European Journal of Operational Research. — 2011. — Т. 208, № 3. — С. 221—232.
38. Khachai M. Y. Approximation Schemes for the Generalized Traveling Salesman Problem / M. Y. Khachai, E. D. Neznakhina // Proceedings of the Steklov Institute of Mathematics. — 2017. — Т. 299, № 1. — С. 97— 105. — URL: https://doi.org/10.1134/S0081543817090127.
39. Khachay M. PCGLNS: A Heuristic Solver for the Precedence Constrained Generalized Traveling Salesman Problem / M. Khachay, A. Kudriavtsev, A. Petunin // Optimization and Applications. Т. 12422 / под ред. N. Olenev, Y. Evtushenko, M. Khachay, V. Malkova. — Cham : Springer International Publishing, 2020. — С. 196—208. — (Lecture Notes in Computer Science).
40. Khachay M. Complexity and approximability of the Euclidean Generalized Traveling Salesman Problem in grid clusters / M. Khachay, K. Neznakhina // Annals of Mathematics and Artificial Intelligence. — 2020. — Т. 88, № 1. — С. 53—69.
41. Khachay M. Towards Tractability of the Euclidean Generalized Traveling Salesman Problem in Grid Clusters Defined by a Grid of Bounded Height / M. Khachay, K. Neznakhina // Optimization Problems and Their Applications. Т. 871 / под ред. A. Eremeev, M. Khachay, Y. Kochetov, P. Pardalos. — Cham : Springer International Publishing, 2018. — С. 68— 77. — (Communications in Computer and Information Science). — URL: https://doi.org/10.1007/978-3-319-93800-4%7B%5C_%7D6.
42. Khachay M. Problem-Specific Branch-and-Bound Algorithms for the Precedence Constrained Generalized Traveling Salesman Problem / M. Khachay, S. Ukolov, A. Petunin // Optimization and Applications. Т. 13078 / под ред. N. Olenev [и др.]. — Cham, Switzerland : Springer Nature Switzerland AG, 2021. — С. 136—148. — (Lecture Notes in Computer Science).
43. Kudriavtsev A. PCGLNS: adaptive heuristic solver for the Precedence Constrained GTSP / A. Kudriavtsev, M. Khachay. — 2020. — URL: https://github.com/AndreiKud/PCGLNS/.
44. Laporte G. Computational Evaluation Of A Transformation Procedure For The Symmetric Generalized Traveling Salesman Problem / G. Laporte, F. Semet // INFOR: Information Systems and Operational Research. — 1999. — Т 37, № 2. — С. 114—120.
45. Li J. Automatic generation of auxiliary cutting paths based on sheet material semantic information / J. Li, H. Zhu, T. Zhang, L. He, Y. Guan, H. Zhang // International Journal of Advanced Manufacturing Technology. — 2020. — Т. 106, № 9. — С. 3787—3797.
46. LiveScript - a language which compiles to JavaScript. — URL: https : //livescript.net/.
47. Makarovskikh T. A. Mathematical models and routing algorithms for economical cutting tool paths / T. A. Makarovskikh, A. V. Panyukov, E. A. Savitskiy // International Journal of Production Research. — 2018. — Т. 56, № 3. — С. 1171—1188.
48. Makarovskikh T. Software Development for Cutting Tool Routing Problems / T. Makarovskikh, A. Panyukov, E. Savitsky // Procedia Manufacturing. —
2019. — Т. 29. — С. 567—574.
49. Makarovskikh T. A. Software for Constructing A-chains with Ordered Enclosing for a Plane Connected 4-regular Graph / T. A. Makarovskikh, A. V. Panyukov // IFAC-PapersOnLine. — 2019. — T. 52, № 13. — C. 2650—2655.
50. Morin T. L. Branch-And-Bound Strategies for Dynamic Programming / T. L. Morin, R. E. Marsten // Operations Research. — 1976. — T. 24, № 4. — C. 611—627. — URL: http://www.jstor.org/stable/169764.
51. Nesting Factory: Automatic Nesting - Making Feasible. — URL: http: //algomate.com/.
52. NetworkX: Python package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks. — URL: https ://networkx.org/.
53. Noon C. E. An Efficient Transformation Of The Generalized Traveling Salesman Problem / C. E. Noon, J. C. Bean // INFOR: Information Systems and Operational Research. — 1993. — T. 31, № 1. — C. 39—44.
54. NumPy: library for the Python programming language, adding support for large, multi-dimensional arrays and matrices, along with a large collection of high-level mathematical functions to operate on these arrays. — URL: https://numpy.org/.
55. Official home of the Python Programming Language. — URL: https://www.python.org/.
56. Panteleev A. V. Metaheuristic Algorithms for Searching Global Extremum / A. V. Panteleev // MAI, Moscow. — 2009.
57. Papadimitriou C. Euclidean TSP is NP-complete / C. Papadimitriou // Theoret. Comput. Sci. — 1977. — T. 4, BHH. 3. — C. 237—244.
58. Petunin A. A. Elements of dynamic programming in local improvement constructions for heuristic solutions of routing problems with constraints / A. A. Petunin, A. A. Chentsov, A. G. Chentsov, P. A. Chentsov // Automation and Remote Control. — 2017. — T. 78, № 4. — C. 666—681.
59. Petunin A. A. About routing in the sheet cutting / A. A. Petunin, A. G. Chentsov, P. A. Chentsov // Bulletin of the South Ural State University, Series: Mathematical Modelling, Programming and Computer Software. — 2017. — T. 10, № 3. — C. 25—39.
60. Petunin A. A. Optimum routing algorithms for control programs design in the CAM systems for CNC sheet cutting machines / A. A. Petunin, P. A. Chentsov, E. G. Polishchuk, S. S. Ukolov, V. V. Martynov // Proceedings of the X All-Russian Conference «Actual Problems of Applied Mathematics and Mechanics» with International Participation, Dedicated to the Memory of Academician A.F. Sidorov and 100th Anniversary of UrFU: AFSID-2020. — American Institute of Physics Inc., 2020. — С. 020005-1—020005-7.
61. Petunin A. A. On the new Algorithm for Solving Continuous Cutting Problem / A. A. Petunin, E. G. Polishchuk, S. S. Ukolov // IFAC- PapersOnLine. — 2019. — Т 52, № 13. — С. 2320—2325.
62. Petunin A. A. About some types of constraints in problems of routing / A. A. Petunin, E. G. Polishuk, A. G. Chentsov, P. A. Chentsov, S. S. Ukolov // AIP Conference Proceedings. — 2016. — Т. 1789, № 1. — С. 060002-1—060002-8.
63. Petunin A. A. The termal deformation reducing in sheet metal at manufacturing parts by CNC cutting machines / A. A. Petunin, E. G. Polyshuk, P. A. Chentsov, S. S. Ukolov, V. I. Krotov // IOP Publishing. —
2020. — Т. 613. — С. 012041-1—012041-5.
64. Petunin A. General Model of Tool Path Problem for the CNC Sheet Cutting Machines / A. Petunin // IFAC-PapersOnLine. — 2019. — Т. 52, № 13. — С. 2662—2667.
65. Petunin A. A. Optimization Models of Tool Path Problem for CNC Sheet Metal Cutting Machines / A. A. Petunin, C. Stylios // IFAC- PapersOnLine. — 2016. — Т 49, № 12. — С. 23—28.
66. Pezoa F. Foundations of JSON Schema / F. Pezoa, J. L. Reutter, F. Suarez, M. Ugarte, D. Vrgoc // WWW ’16: Proceedings of the 25th International Conference on World Wide Web. — Republic, Canton of Geneva, CHE : International World Wide Web Conferences Steering Committee, 2016. — С. 263—273.
67. Punnen (auth.) A. P. The Traveling Salesman Problem and Its Variations /
A. P. Punnen (auth.), G. Gutin, A. P. Punnen (eds.) — 1-е изд. — Springer US, 2002. — (Combinatorial Optimization 12).
68. Reihaneh M. An Efficient Hybrid Ant Colony System for the Generalized Traveling Salesman Problem / M. Reihaneh, D. Karapetyan // Algorithmic Operations Research. — 2012. — T. 7, № 1. — C. 22—29. — URL: https ://www.erudit.org/en/journals/aor/2012-v7-n1-aor7_1/aor7_1art03.
69. Rollup: a module bundler for JavaScript. — URL: https://rollupjs.org/guide/en/.
70. Salman R. An Industrially Validated CMM Inspection Process with Sequence Constraints / R. Salman, J. S. Carlson, F. Ekstedt, D. Spensieri, J. Torstensson, R. Soderberg // Procedia CIRP. — 2016. — T. 44. — C. 138— 143. — URL: http://www.sciencedirect.com/science/article/pii/S2212827116004182 ; 6th CIRP Conference on Assembly Technologies and Systems (CATS).
71. Salman R. Branch-and-bound for the Precedence Constrained Generalized Traveling Salesman Problem / R. Salman, F. Ekstedt, P. Damaschke // Operations Research Letters. — 2020. — T. 48, № 2. — C. 163—166.
72. Sarin S. C. New Tighter Polynomial Length Formulations for the Asymmetric Traveling Salesman Problem with and without Precedence Constraints / S. C. Sarin, H. D. Sherali, A. Bhootra // Oper. Res. Lett. — NLD, 2005. — T. 33, № 1. — C. 62—70.
73. Scalable Vector Graphics. — URL: https://www.w3.org/Graphics/SVG/.
74. SciPy: Python-based ecosystem of open-source software for mathematics, science, and engineering. — URL: https://www.scipy.org/.
75. Sherif S. U. Sequential optimization approach for nesting and cutting sequence in laser cutting / S. U. Sherif, N. Jawahar, M. Balamurali // Journal of Manufacturing Systems. — 2014. — T. 33, № 4. — C. 624—638.
76. Smith S. L. GLNS: An effective large neighborhood search heuristic for the Generalized Traveling Salesman Problem / S. L. Smith, F. Imeson // Computers & Operations Research. — 2017. — T. 87. — C. 1—19.
77. Srivastava S. Generalized Traveling Salesman Problem through n sets of nodes / S. Srivastava, S. Kumar, R. Garg, P. Sen // CORS journal. — 1969. — T. 7, BHH. 2, № 2. — C. 97—101.
78. Steiner G.On the complexity of dynamic programming for sequencing problems with precedence constraints / G. Steiner // Annals of Operations Research. — 1990. — T 26, № 1. — C. 103—123.
79. Tavaeva A. A Cost Minimizing at Laser Cutting of Sheet Parts on CNC Machines / A. Tavaeva, A. Petunin, S. Ukolov, V. Krotov // Mathematical Optimization Theory and Operations Research. — Cham, Switzerland : Springer, 2019. — C. 422—437.
80. The Gurobi Optimizer, commercial optimization solver for linear programming (LP), quadratic programming (QP), quadratically constrained programming (QCP), mixed integer linear programming (MILP), mixed¬integer quadratic programming (MIQP), and mixed-integer quadratically constrained programming (MIQCP). — URL: https://www.gurobi.com/.
81. The Gurobi Python Interface. — URL: https : //pypi . org/project/gurobipy/.
82. TOML: Tom’s Obvious, Minimal Language. — URL: https://github.com/toml-lang/toml.
83. Tree: Simple fast compact user-readable binary-safe extensible structural format. — URL: https://github.eom/nin-jin/tree.d/.
84. Vicencio K. Multi-goal path planning based on the generalized Traveling Salesman Problem with neighborhoods / K. Vicencio, B. Davis, I. Gentilini // 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems. — IEEE. — C. 14—18.
85. Vijay Anand K. Heuristic and genetic approach for nesting of two-dimensional rectangular shaped parts with common cutting edge concept for laser cutting and profile blanking processes / K. Vijay Anand, A. Ramesh Babu // Computers & Industrial Engineering. — 2015. — T. 80. — C. 111—124.
86. Wäscher G. An improved typology of cutting and packing problems / G. Wascher, H. Haußner, H. Schumann // European Journal of Operational Research. — 2007. — T 183, № 3. — C. 1109—1130.
87. Webpack: an open-source JavaScript module bundler. — URL: https : //webpack.js.org/.
88. YAML: YAML Ain’t Markup Language™. — URL: https://yaml.org/.
89. Ye J. An Optimized Algorithm of Numerical Cutting-Path Control in Garment Manufacturing. Т. 796 / J. Ye, Z. G. Chen. — Trans Tech Publications Ltd, 2013.
90. Yu W. A route planning strategy for the automatic garment cutter based on genetic algorithm / W. Yu, L. Lu // 2014 IEEE Congress on Evolutionary Computation (CEC). — IEEE. — С. 6—11.
91. Yuan Y. A branch-and-cut algorithm for the generalized traveling salesman problem with time windows / Y. Yuan, D. Cattaruzza, M. Ogier, F. Semet // European Journal of Operational Research. — 2020. — Т. 286, № 3. — С. 849— 866. — URL: https://www.sciencedirect.com/science/article/pii/S0377221720303581.
92. Yun Y. Hybrid genetic algorithm approach for precedence-constrained sequencing problem / Y. Yun, H. Chung, C. Moon // Computers & Industrial Engineering. — 2013. — Т. 65, № 1. — С. 137—147.
93. Бабичев С. Оптимизация раскроя средствами T-FLEX / С. Бабичев // САПР и графика. — 2018. — № 9. — С. 50—53.
94. Бурылов А. В. Автоматическое и интерактивное формирование маршрута режущего инструмента в программном комплексе раскроя ITAS NESTING / А. В. Бурылов, Р. Т. Мурзакаев, В. С. Приступов // При¬волжский научный вестник. — 2016. — 1 (53).
95. Верхотуров М. А. О задаче построения пути режущего инструмента с учетом термических воздействий при раскрое плоского материала / М. А. Верхотуров, Г. Н. Верхотурова, М. И. Айбулатов, Д. Р. Зарипов // Перспективные информационные технологии: сборник трудов междунар. научно-технической конференции. — 2020. — С. 346—351.
96. Верхотуров М. А. Раскрой листовых материалов на фигурные заготовки: оптимизация пути режущего инструмента на основе приминения группировки контуров / М. А. Верхотуров, П. Ю. Тарасенко, А. Р. Тарасснко // Альманах современной науки и образования. — 2008. — № 1. — С. 36—39.
97. Верхотуров М. А. Математическое обеспечение задачи оптимизации пути режущего инструмента при плоском фигурном раскрое на основе цепной резки / М. А. Верхотуров, П. Ю. Тарасенко // Вестник Уфимского государственного авиационного технического университета. — 2008. — Т. 10, № 2.
98. Канторович Л. В. Рациональный раскрой промышленных материалов / Л. В. Канторович, В. А. Залгаллер. — Новосибирск : Наука, 1971. — 290 с.
99. Мурзакаев Р. Т Применение метаэвристических алгоритмов для минимизации длины холостого хода режущего инструмента / Р. Т. Мурзакаев,
B. С. Шилов, А. В. Бурылов // Вестник Пермского национального исследовательского политехнического университета. Электротехника, информационные технологии, системы управления. — 2015. — № 14.
100. Мурзакаев Р. Т Построение маршрута режущего инструмента на основе алгоритма «Всемирного потопа» / Р. Т. Мурзакаев, В. С. Приступов // In the World of Scientific Discoveries/V Mire Nauchnykh Otkrytiy. — 2015. — Т. 69.
101. Мухачева Э. А. Рациональный раскрой промышленных материалов. Применение АСУ / Э. А. Мухачева. — М. : Машиностроение, 1984. — 176 с.
102. Мухачева Э. А. Модели и методы расчета раскроя-упаковки геометрических объектов / Э. А. Мухачева, М. А. Верхотуров, В. В. Мартынов. — Уфа : УГАТУ, 1998. — 217 с.
103. Петунин А. А. Две задачи маршрутизации режущего инструмента для машин фигурной листовой резки с ЧПУ / А. А. Петунин // Intelligent Technologies for Information Processing and Management (ITIPM’2014). —2014.— С. 215—220.
104. Петунин А. А. САПР «Сириус» - оптимизация раскроя и резки листовых материалов в единичном производстве / А. А. Петунин, В. И. Кротов,
C. С. Уколов, В. В. Видяпин // САПР и графика. — 1999. — № 10. — С. 42.
105. Петунин А. А. Новый алгоритм построения кратчайшего пути обхода конечного множества непересекающихся контуров на плоскости / А. А. Петунин, Е. Г. Полищук, С. С. Уколов // Известия ЮФУ. Технические науки. — 2021. — № 1. — С. 149—164.
106. Петунин А. А. Эффективная маршрутизация робота/беспилотного летательного аппарата в задачах с условиями предшествования / А. А. Петунин, М. Ю. Хачай, С. С. Уколов // XIV Всероссийская мультиконференция по проблемам управления (МКПУ-2021). Т. 1. — Издательство Южного федерального университета, 2021. — С. 202—205.
107. Петунин А. А. Алгоритмы оптимальной маршрутизации для систем автоматизированного проектирования управляющих программ машин листовой резки с ЧПУ / А. А. Петунин, П. А. Ченцов, Е. Г. Полищук, С. С. Уколов, В. В. Мартынов // Актуальные проблемы прикладной математики и механики. — Институт математики и механики УрО РАН им. Н.Н. Красовского, 2020. — С. 58—59.
108. Петунин А. А. Методологические и теоретические основы автоматизации проектирования раскроя листовых материалов на машинах с числовым программным управлением : дис. ... д-ра техн. наук : 05.13.12 / Петунин Александр Александрович. — Уфимский государственный авиационно-технический университет, 2010.
109. Петунин А. А. О классификации техник фигурной листовой резки для машин с ЧПУ и одной задаче маршрутизации инструмента / А. А. Пету- нин, В. И. Кротов // Материаловедение. Машиностроение. Энергетика. —2015.— С. 466—475.
110. Петунин А. А. Оптимальная маршрутизация инструмента машин фигурной листовой резки с числовым программным управлением. Математические модели и алгоритмы / А. А. Петунин, А. Г. Ченцов, П. А. Ченцов. — Издательство Уральского университета, 2020. — 247 с.
111. Пушкарева Г. В. Применение гибридного генетического алгоритма для оптимизации маршрутов / Г. В. Пушкарева // Автометрия. — 2006. — Т 42, № 2. — С. 68—79.
112. Таваева А. Ф. Разработка инвариантного модуля генерации управляющих программ для машин лазерной резки. Вопросы интеграции с CAD/CAM системами / А. Ф. Таваева, Е. Н. Шипачева, П. А. Ченцов,
А. А. Петунин, С. С. Уколов, А. П. Халявка // Актуальные проблемы прикладной математики и механики. — Институт математики и механики УрО РАН им. Н.Н. Красовского, 2020. — С. 70—71.
113. Таваева А. Ф. Разработка методик расчета временных и стоимостных параметров процесса резки в системах автоматизированного проектирования управляющих программ для машин листовой лазерной резки с ЧПУ : дис. ... канд. техн. наук : 05.13.12 / Таваева Анастасия Фидагилевна. — Уральский федеральный университет имени первого Президента России Б.Н. Ельцина, 2020.
114. Уколов С. С. Визуализация решения задачи PCGTSP / С. С. Уколов. — URL: https://ukoloff.github.io/j2pcgtsp/.
115. Уколов С. С. Конвертеры открытых форматов для САПР «Сириус» / С. С. Уколов. — URL: https://github.com/ukoloff/dbs.js.
116. Уколов С. С. Описание формата DBS / С. С. Уколов, В. И. Кротов. — URL: https://github.com/ukoloff/dbs.js/wiki/DBS.
117. Уколов С. С. Алгоритм ветвей и границ для обобщённой задачи коммивояжера с ограничениями предшествования / С. С. Уколов, М. Ю. Хачай. — 2021. — URL: https://github.com/ukoloff/PCGTSP-BnB.
118. Уколов С. С.JSON-схемы файлов, используемых в САПР «Сириус» / С. С. Уколов, П. А. Ченцов. — URL: https://ukoloff.github. io/dbs.js/json-schema/.
119. Файзрахманов Р. А. Формирование энергоэкономичного маршрута режущего инструмента станков гидроабразивной и лазерной резки с ЧПУ / Р. А. Файзрахманов, Р. Т. Мурзакаев, А. В. Бурылов, В. С. Шилов // Электротехника. — 2015. — № 11. — С. 32—36.
120. Фроловский В. Д. Автоматизация проектирования управляющих программ тепловой резки металла на оборудовании с ЧПУ / В. Д. Фро- ловский // Информационные технологии в проектировании и производстве. — 2005. — № 4. — С. 63—66.
121. Центр коллективного пользования ИММ УрО РАН «Суперкомпьютерный центр ИММ УрО РАН». — URL: https://parallel.uran.ru/.