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

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

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

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

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

М о н о г р афия

 

Екатеринбург 
Издательство Уральского университета 
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

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

11

пучка, однозначно определяемого маршрутом. Критерий качества предполагается аддитивным. Это означает, что для каждого конкретного решения значение критерия получается суммированием стоимостей, характеризующих
все этапы перемещений, связанных с реализацией упомянутого решения в
виде пары маршрут – трасса.
Для задач, связанных с листовой резкой, исключительно важным является учет ограничений, связанных с тепловыми деформациями материала и порождаемыми этими деформациями эвристическими правилами (т. н.
«жесткостью» листа и деталей), сформулированными в первой главе монографии. Характерной особенностью таких ограничений является то, что все
они формируются по мере развития процесса резки и, по большому счету,
зависят от истории последнего, что определяет принципиальное отличие рассматриваемых задач от оптимизационных задач с фиксированными ограничениями. Здесь опять-таки оказывается уместным двухуровневое представление решения, поскольку целый ряд данных «динамических» ограничений
удается представить в терминах зависимостей от маршрута, определяемого
в виде перестановки индексов.
Учет динамических ограничений осуществляется в настоящей монографии посредством введения специальных функций стоимости, которые объективно играют роль штрафов. При этом, однако, возникают функции стоимости, включающие зависимость от списка заданий, уже выполненных на
момент соответствующего перемещения. Данная особенность существенно
осложняет конструкции на основе ДП; в этой связи в третьей главе рассматривается случай, когда вышеупомянутая зависимость от списка заданий
отсутствует, что позволяет привлечь для целей качественного исследования
более простую и понятную версию ДП.
Более общий случай, когда зависимость функций стоимости от списка заданий уже допускается, рассматривается в четвертой главе. С точки
зрения применения аппарата ДП оказывается более удобным использовать
при формализации задачи функции стоимости, допускающие зависимость от
списка еще не выполненных заданий. Кроме того, по постановке допускаются
условия предшествования, которые в задачах, связанных с листовой резкой,
имеют ясный содержательный смысл: внутренние контуры деталей должны
вырезаться раньше внешних; в случае расположения одних деталей «внутри»
других резка «внутренних» деталей должна осуществляться раньше, чем резка «внешних».

12

Для вышеупомянутой общей постановки в рамках концепции двухуровневого решения (определяемого всякий раз в виде пары маршрут – трасса) осуществляется построение специального расширения исходной задачи.
Потребность в данном расширении связана с учетом условий предшествования, которые порождают «неудобные» ограничения на маршрут в целом.
Эти ограничения удается, однако, эквивалентным образом преобразовать к
условиям, определяемым некоторым естественным правилом вычеркивания
заданий из списка. Итак, допустимость по предшествованию эквивалентным
образом заменяется допустимостью по вычеркиванию. Последняя более удобна для целей применения аппарата ДП, поскольку связывается с условиями
на отдельные этапы процесса перемещений. Одним словом, такая допустимость нужным образом локализуется, что и позволяет затем задействовать
конструкции широко понимаемого динамического программирования и получить затем уравнение Беллмана.
В связи с трудностями вычислительной реализации на основе этого
уравнения конструируется система преобразования так называемых слоев
функции Беллмана. Речь идет о том, чтобы при условиях предшествования (а это типичный случай в рассматриваемом классе задач) ограничиться
частичным построением массива функции Беллмана, а точнее, системы ее
слоев. Последние, в свою очередь, определяются соответствующими слоями
пространства позиций, в определении которых задействуются так называемые существенные списки заданий.
Разумеется, даже при использовании (вышеупомянутым способом) усеченного массива значений функции Беллмана практическое использование
(оптимальной) процедуры на основе ДП возможно лишь в задачах умеренной размерности. В то же время представляют интерес методы локального
улучшения маршрутных решений посредством применения оптимизирующих
вставок, при построении которых удается уже задействовать схему на основе
динамического программирования.
Важно отметить, что само применение оптимизирующих вставок в задаче маршрутизации с условиями предшествования и стоимостями, зависящими от списка заданий, потребовало серьезного теоретического обоснования,
которое приведено в четвертой главе.
В целях более глубокого воздействия на исходное эвристическое решение (имеется в виду решение задачи достаточно большой размерности)
предлагается использовать итерационные процедуры с варьированием нача
13