Оптимальная маршрутизация инструмента машин фигурной листовой резки с числовым программным управлением. Математические модели и алгоритмы

Министерство науки и высшего образования  
Российской Федерации 

Уральский федеральный университет 
имени первого Президента России Б. Н. Ельцина 

А. А. Петунин, А. Г. Ченцов, П. А. Ченцов 

Оптимальная маршрутизация инструмента  
машин фигурной листовой резки  
с числовым программным управлением.  
Математические модели и алгоритмы

М о н о г р афия

 

Екатеринбург 
Издательство Уральского университета 
2020 

УДК 621.9:519.6(035)
ББК 34.638в6+32.965в6
          П29

Ре ц е н з е н ты :
А. В. Коновалов, проф., д-р техн. наук, заведующий лабораторией  
Института машиноведения УрО РАН; 
М. Ю. Хачай, проф., д-р физ.-мат. наук, заведующий отделом математического программирования Института математики и механики  
им. Н. Н. Красовского УрО РАН

На уч н ы й  ред а к т о р  — проф., д-р физ.-мат. наук А. Н. Сесекин 

П29
Петунин, А. А.
Оптимальная маршрутизация инструмента машин фигурной листовой резки с числовым программным управлением.  
Математические модели и алгоритмы : монография /  
А. А. Петунин, А. Г. Ченцов, П. А. Ченцов ; Мин-во науки и высшего образования РФ. — Екатеринбург : Изд-во Урал. ун-та, 
2020. — 247, [1] с.

ISBN 978-5-7996-3016-4

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

* Результаты исследований получены при выполнении проекта создания и развития научной 
лаборатории «Лаборатория оптимального раскроя промышленных материалов и оптимальных 
маршрутных технологий» в рамках Программы повышения конкурентоспособности Уральского 
федерального университета 5–100–2020 и при поддержке Российского Фонда Фундаментальных 
Исследований (гранты № 17-08-01385, № 20-08-00873).
УДК 621.9:519.6(035)
ББК 34.638в6+32.965в6

ISBN 978-5-7996-3016-4
© Уральский федеральный 
     университет, 2020

Оглавление

ВВЕДЕНИЕ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7

I
ИНЖЕНЕРНЫЕ ЗАДАЧИ МАРШРУТИЗАЦИИ
ИНСТРУМЕНТА МАШИН ЛИСТОВОЙ РЕЗКИ.
ОБЩИЕ ПОСТАНОВКИ И ПОДХОДЫ
К ИХ РЕШЕНИЮ
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.
МОДЕЛИРОВАНИЕ МАРШРУТА ИНСТРУМЕНТА
ДЛЯ МАШИН ФИГУРНОЙ ЛИСТОВОЙ РЕЗКИ
С ЧИСЛОВЫМ ПРОГРАММНЫМ УПРАВЛЕНИЕМ.
ОСНОВНЫЕ ПОНЯТИЯ И ЗАДАЧИ
. . . . . . . . . . . . . .
21
§ 1.1. Технологии и техники листовой резки на машинах с ЧПУ
. .
21
§ 1.2. Маршрут резки и оптимизационные задачи маршрутизации
инструмента машин листовой резки с ЧПУ . . . . . . . . . . . .
29
§ 1.3. Технологические ограничения параметров маршрута
инструмента машин листовой резки с ЧПУ . . . . . . . . . . . .
38
§ 1.3.1. Ограничения координат точек врезки и точек
выключения инструмента, обусловленные деформацией
материала при врезке
. . . . . . . . . . . . . . . . . . . .
38
§ 1.3.2. Условие предшествования
. . . . . . . . . . . . . . . . .
40
§ 1.3.3. Эвристические правила термической резки заготовок
из листовых материалов . . . . . . . . . . . . . . . . . . .
42
§ 1.4. Классификация оптимизационных задач маршрутизации
инструмента машин фигурной листовой резки с ЧПУ . . . . . .
50

3

2.
ПРАКТИЧЕСКИЕ АСПЕКТЫ ОПТИМИЗАЦИИ
ТРАЕКТОРИИ ИНСТРУМЕНТА ДЛЯ МАШИН
ЛАЗЕРНОЙ РЕЗКИ С ЧПУ
. . . . . . . . . . . . . . . . . . . .
59
§ 2.1. Точное вычисление целевых функций в задаче оптимизации
маршрута резки на примере машины лазерной резки
ByStar 3015
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
§ 2.1.1. Вычисление фактического времени лазерной резки
машины с ЧПУ в зависимости от параметров
управляющей программы и технологических факторов
процесса резки
. . . . . . . . . . . . . . . . . . . . . . . .
59
§ 2.1.2. Вычисление стоимости резки заготовок на машине
с ЧПУ в режиме моделирования процесса резки . . . . .
65
§ 2.2. Стратегии формирования маршрута режущего инструмента
для типовых заготовок на машиностроительном производстве .
70
§ 2.2.1. Стратегии проектирования маршрута режущего
инструмента для круглых заготовок . . . . . . . . . . . .
72
§ 2.2.2. Стратегии проектирования маршрута режущего
инструмента для многоугольных заготовок . . . . . . . .
79
§ 2.3. Разработка методов учета динамических ограничений
в оптимизационных алгоритмах маршрутизации инструмента
машин для термической резки листовых заготовок
. . . . . . .
87

II
МАТЕМАТИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ
РЕШЕНИЯ ЗАДАЧ МАРШРУТИЗАЦИИ,
СВЯЗАННЫХ С ЛИСТОВОЙ РЕЗКОЙ НА МАШИНАХ
С ЧПУ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

3.
ЗАДАЧА ПОСЛЕДОВАТЕЛЬНОГО ОБХОДА
МЕГАПОЛИСОВ С УСЛОВИЯМИ
ПРЕДШЕСТВОВАНИЯ
. . . . . . . . . . . . . . . . . . . . . . . 105
§ 3.1. Используемые соглашения и обозначения
. . . . . . . . . . . . 105
§ 3.2. Математическая постановка задачи. Обсуждение
на содержательном уровне
. . . . . . . . . . . . . . . . . . . . . 109
§ 3.3. Математическая постановка задачи. Объект исследования
и некоторые характерные ограничения
. . . . . . . . . . . . . . 111
§ 3.4. Расширение основной маршрутной задачи
. . . . . . . . . . . . 123

4

§ 3.5. Экономичная версия метода динамического программирования 129
§ 3.6. Построение эвристик на базе ДП
. . . . . . . . . . . . . . . . . 137

4.
ЗАДАЧИ МАРШРУТИЗАЦИИ С ОГРАНИЧЕНИЯМИ
И УСЛОЖНЕННЫМИ ФУНКЦИЯМИ СТОИМОСТИ
. . 141
§ 4.1. Трудности при решении задач маршрутизации
. . . . . . . . . 141
§ 4.2. Постановка задач маршрутизации . . . . . . . . . . . . . . . . . 143
§ 4.3. Динамическое программирование при усложненных функциях
стоимости
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
§ 4.4. Локальное улучшение допустимых решений
. . . . . . . . . . . 151
§ 4.5. Алгоритм на функциональном уровне (вставка в начало)
. . . 173
§ 4.6. Алгоритм на функциональном уровне (вставка в середину) . . 185
§ 4.7. Финальная оптимизирующая вставка . . . . . . . . . . . . . . . 191
§ 4.8. Итерационные методы с использованием оптимизирующих
вставок (общие соображения) . . . . . . . . . . . . . . . . . . . . 203

5.
АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ МАРШРУТИЗАЦИИ
С ОГРАНИЧЕНИЯМИ
. . . . . . . . . . . . . . . . . . . . . . . . 207
§ 5.1. Общие подходы к решению задач маршрутизации
. . . . . . . 207
§ 5.2. Задача маршрутизации перемещений
(частная постановка задачи)
. . . . . . . . . . . . . . . . . . . . 209
§ 5.3. Итерационный режим с комбинированием оптимизирующих
вставок разной «длины» . . . . . . . . . . . . . . . . . . . . . . . 213
§ 5.4. Итерационный режим с элементами оптимизации локальных
условий предшествования
. . . . . . . . . . . . . . . . . . . . . . 215
§ 5.5. Итерационный режим со случайным расположением вставок
фиксированной «длины» . . . . . . . . . . . . . . . . . . . . . . . 220
§ 5.6. Вариант «жадного» эвристического алгоритма
. . . . . . . . . 221

ЗАКЛЮЧЕНИЕ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233

Библиографический список . . . . . . . . . . . . . . . . . . . . . . . . 235

5

ВВЕДЕНИЕ

В различных технических приложениях возникают задачи моделирования маршрута и маршрутной оптимизации. Большая часть таких задач обычно рассматривается современными исследователями через призму различных
комбинаторных моделей дискретной оптимизации. Вместе с тем, при моделировании маршрута в реальных технических задачах числовые значения
некоторых параметров маршрута могут выбираться из множества допустимых величин, имеющего континуальную мощность, что усложняет математические модели оптимальной маршрутизации в сравнении с классическими
маршрутными постановками типа задачи коммивояжера (ЗК). Кроме того,
на множество допустимых решений могут накладываться дополнительные
ограничения, вызванные техническими особенностями задачи, например, технологическими требованиями к маршруту, порождаемыми спецификой конкретной предметной области. В результате возникают новые математические
постановки, не охватываемые существующими методами решения. К числу
такого рода сложных задач относится проблема оптимальной маршрутизации инструмента машин фигурной листовой резки с числовым программным
управлением (ЧПУ). Эта проблема возникает на этапе разработки управляющих программ для машины с ЧПУ, которые задают траекторию перемещения
инструмента и ряд технологических команд, определяющих параметры резки листового материала для получения из него заготовок известных форм
и размеров. Необходимые данные для моделирования маршрута инструмента машины с ЧПУ определяет информация о раскройных картах, которые
разрабатываются на этапе проектирования раскроя и порождают известные
задачи оптимизации раскроя листового материала. С точки зрения геометрической оптимизации задачи раскроя относятся к классу задач раскроя –
упаковки (Cutting & Packing), для которых, также как и для маршрутных
оптимизационных проблем, не известны алгоритмы решения полиномиальной сложности. В данной работе задачи раскроя не рассматриваются. Основ
7

ное направление исследования в настоящей монографии связано с моделированием маршрута инструмента машин фигурной листовой резки с ЧПУ и
проблемой его оптимизации по временным и стоимостным параметрам.
В исходной задаче требуется осуществить последовательное посещение
всех контуров с целью осуществления резки по эквидистантам, представляющим собой замкнутые кривые (обсуждаются также и более сложные типы
резки); точки, определяющие начало и окончание реза, могут при этом назначаться произвольно. В интересах построения конкретных решений приходится, однако, использовать дискретизацию эквидистант и некоторые дополнительные преобразования последних в непустые конечные множества —
мегаполисы, что и делается в настоящей монографии (см. в этой связи [1; 2]).
Если рассматривать сформулированное научное направление в его полной общности, то приходится признать, что адекватной математической теории здесь не разработано. Имеются отдельные направления, среди которых
особо отметим проблему полиномиальной разрешимости для отдельных классов оптимизационных задач, которые могут использоваться в качестве подзадач рассматриваемой проблемы. Известные результаты, которые получены в
последние годы в предметных областях, связанных с разработкой алгоритмов
дискретной оптимизации и исследованием проблемы полиномиальной разрешимости, при всей своей значимости не охватывают проблемы «диапазонных» (в смысле размерности) задач и особенно задач, осложненных ограничениями. В монографии авторы исследуют вопросы разработки теоретических и методологических основ решения проблемы оптимальной маршрутизации инструмента для машин фигурной листовой резки с ЧПУ, включая
разработку адекватных математических моделей и алгоритмов решения для
исследуемой прикладной задачи. Результаты работы могут быть использованы и для решения других прикладных задач, описываемых предложенными
в монографии математическими моделями.
Монография структурно состоит из двух частей и пяти глав.
В первой главе рассмотрены основные понятия фигурной листовой резки на машинах с ЧПУ, формулируется содержательная постановка исследуемой проблемы, приводятся общие постановки и классификация возникающих
оптимизационных маршрутных задач. Здесь же приведена «первичная» математическая формализация рассматриваемой проблемы и описана дискретная модель некоторых сформулированных ранее оптимизационных задач, основанная на использовании модели мегаполисов.

8

Во второй главе рассматриваются отдельные практические аспекты оптимизации траектории инструмента для машин листовой резки с ЧПУ: описываются способы уменьшения термических деформаций материала при оптимальной маршрутизации инструмента, исследуется проблема точного вычисления целевых функций на примере машины лазерной резки ByStar 3015
и эффективность применения специальных техник резки в сравнении со стандартной техникой «резки по контуру».
Третья глава содержит описание математических моделей и методов,
используемых при решении задачи последовательного обхода мегаполисов с
условиями предшествования.
В четвертой главе исследованы задачи маршрутизации с ограничениями и усложненными функциями стоимости. Рассматриваются вопросы, связанные с локальным улучшением эвристических решений.
В пятой главе приводятся описание разработанных авторами алгоритмов для решения задач маршрутизации, а также результаты вычислительных
экспериментов, содержащих данные решения некоторых практических задач
оптимизации маршрута инструмента для машин фигурной листовой резки с
ЧПУ.
Две первые главы образуют в своей совокупности первую часть настоящей работы, непосредственно связанную с решением инженерных задач, относящихся к листовой резке на машинах с ЧПУ. Здесь обсуждаются конкретные варианты весьма общей постановки, указываются характерные особенности и обозначаются на идейном уровне основные элементы этой общей постановки. Особую значимость приобретает обсуждение различных вариантов
осуществления резки, включая многие подробности, важные в инженерном
отношении, а также характерные ограничения. Последние существенно влияют на математическую постановку; учет некоторых ограничений оказывается
весьма затруднительным.
В первой главе подробно обсуждается стандартная техника резки (резка по замкнутому контуру), которая, как представляется, более близка к известным математическим постановкам задач о последовательном обходе мегаполисов с условиями предшествования (данное обстоятельство существенно
используется во второй части работы). Упомянутые условия играют важную
роль как на этапе инженерной постановки, так и на этапе математического
исследования. Их конкретный вариант состоит (в данной задаче) в необходимости более раннего вырезания внутренних контуров деталей и «внутрен
9

них» деталей, то есть деталей, располагаемых (после раскроя) внутри других
(объемлющих) деталей, что соответствует размещению по схеме «матрешки».
Само решение задачи является многоэтапным, и упомянутые условия предшествования касаются всей совокупности упомянутых этапов. В то же время
сам характер этих условий оказывается до некоторой степени удобным для
их последующего учета на этапе общей постановки; они касаются выбора очередности достаточно крупных фрагментов решения и имеют комбинаторный
характер.
В первой части монографии обсуждаются также различные варианты нестандартной техники резки (цепная резка, резка с перемычками, резка «змейкой» и др.). Вводятся важные понятия сегмента резки и базового
сегмента резки, определяющие общий взгляд на проблему классификации
вариантов резки (резка по замкнутому контуру, мультисегментная и мультиконтурная резки). Понятия сегмента резки и базового сегмента являются
по сути объединяющими различные варианты резки в естественные классы,
допускающие исследование соответствующих конкретных вариантов с единых позиций и существенно расширяющие имеющуюся классификацию задач
маршрутизации инструмента для машин листовой резки с ЧПУ.
Особое внимание уделено в монографии вопросам, связанным с формализацией и математической постановкой рассматриваемых инженерных
задач. Частично эти вопросы затрагиваются в первой части, где проблемы формализации обсуждаются с позиций инженерного исследования; решения трактуются как маршруты резки, являющиеся объектами выбора исследователя с целью максимального улучшения (совокупного) результата
при соблюдении комплекса разнообразных ограничений. Такой подход позволяет сформулировать определенные ориентиры, которые особенно полезны
при разработке эффективных эвристических алгоритмов. Само же применение эвристических методов для решения практических задач представляется неизбежным. Здесь же рассматривается задача точного вычисления целевых функций, в рамках решения которой исследуются практические вопросы определения зависимости фактической скорости резки от числа кадров
управляющей программы (на примере машины лазерной резки ByStar 3015),
описывается методика определения параметров для целевой функции стоимости лазерной резки с вычислением стоимостных параметров этой функции
для различных марок и толщин листовых материалов.

10