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

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

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

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

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

М о н о г р афия

 

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