第1章 绪论
　　1.1 引言
　　排样问题也称为排料问题、套料问题，或二维装箱问题，国外也将其称为下料问题(cutting stock problem)，是指在给定的板材区域内找出待排零件的非重叠*优排布方案，使得材料利用率*高，或者浪费的材料*少。排样与切割问题广泛存在于机械、船舶、电气、轻工等行业中需要使用板材类原材料的生产加工领域，表1.1列出了排样问题的一些主要应用领域。通过排样优化可以提高材料利用率，减少材料浪费，从而带来巨大的社会效益和经济效益。因此，对优化排样技术的研究和应用开发一直是学术界和工业界关注的重点问题之一。
　　表1.1排样问题的主要应用领域
　　我国提出的“中国制造2025”战略中，以提高产业自动化程度、减少资源消耗为目标，并将单位国内生产总值能耗下降3.1%作为当年经济社会发展的主要目标任务之一。应用优化排样技术一方面可以降低员工劳动强度，大大提高排样效率和材料利用率，帮助企业缩减成本，从而带来可观的经济效益，另一方面也支持了绿色制造理念。通过智能优化排样，材料利用率即使有1%的提高，也会为企业节约大量成本，为全社会带来巨大的社会效益和经济效益。以机械制造业为例，我国是制造大国，也是各类钢材的消耗大国。据产业信息网提供的统计信息[ZYB1][d2]①，我国钢材消耗量每年增长接近10%，2017年钢材消耗量达7亿t，2018年前三季度钢材产量为8.2亿t，其中钢板占了大部分比重。尤其在工程机械、机车、船舶、桥梁等以钢结构件制造为主的重工业，钢板消耗量巨大。如何通过智能优化排样来提高钢板利用率以减少钢板消耗，不仅对降低这些行业的制造成本、提高经济效益具有重要意义，而且对于全社会的节材降耗和节能减排都具有十分重要的意义。
　　1.2 排样问题分类
　　 Wscher等[1]从排样维度、零件种类、原材料种类、零件形状、工艺约束等角度对排样问题进行了总结与归纳，如图1.1所示。根据该分类法则，纵向上将排样问题按排样维度划分为一维排样问题、二维排样问题、三维排样问题和多维排样问题，横向上将排样问题按其在实际工程应用中的特点又分别按排样零件种类、原材料种类、零件形状、工艺约束等多种维度划分成多个变种问题。在排样问题的研究中，将其按排样维度、零件形状、工艺约束来分类得到比较广泛的认可。
　　图1.1 排样问题分类
　　1.2.1 按排样维度分类
　　按排样维度，可将排样问题分为一维排样问题、二维排样问题、三维排样问题及多维排样问题。
　　1.一维排样问题
　　一维排样也称为线材排样，是指给定一定数量和长度规格的线材(如管材或型材)，要求从线材长度方向切割出一定数量和种类的毛坯(各类毛坯的长度不一，数量要求也不同)，如何进行优化排样，即确定各个毛坯在各根线材上的切割顺序，使消耗的线材总长度*少。
　　例如，给定根数不限的一批管材，其长度均为10m，现需要从上述管材中切割出一批长度分别为4m、3m和2m的三种毛坯，各种毛坯的数量分别为10件、20件、30件，通过优化排样确定这60件毛坯在每根用到的管材上的切割顺序，使消耗的管材总长度(或数量)*少。上述线材排样问题示意图如图1.2所示。
　　图1.2 线材排样问题示意图
　　2.二维排样问题
　　二维排样也称为板材排样，是指将若干二维平面形状的零件以一定的顺序并在合适的位置及角度方向依次排布于板材内部，排布的每个零件之间互不重叠且完全包含于板材区域之内，使得排样后的所有零件占用的板材总面积*小，即板材利用率*大。图1.3是一批二维异形零件在一张矩形板材内的二维排样示意图。
　　图1.3 板材排样示意图
　　二维排样是在生产实践中*广泛存在的一类排样问题，例如，生产制造中常见的金属板材切割下料、服装布料裁剪、皮革裁剪、板式家具开料等裁切加工都属于二维排样问题。显然，由于零件几何形状上的复杂性，二维排样问题比一维排样问题的求解难度更大，特别是对复杂不规则图形的二维排样一直以来都是学术界研究的热点问题之一。本书讨论二维排样问题。
　　3.三维排样问题
　　三维排样也称为装箱排样，近年来越来越受到学术界和工业界的重视。三维排样问题是指在一个给定的有限三维空间内，对于给定的若干三维形状的零件，确定每个零件的放置顺序、放置位置及方位，使得这些零件所占用的总空间*少。三维排样问题的典型应用场景是物流行业中的集装箱*大化装填问题。图1.4是装箱排样过程示意图。
　　图1.4 装箱排样过程示意图
　　除此之外，还有考虑除长宽高三维尺寸之外更多维度的排样问题，一般统称为多维排样问题。例如，航天飞机驾驶舱的仪器仪表布局问题，不仅需要考虑空间布局的紧凑性，还要考虑载重量、重心、稳定性、可拆卸等其他多个维度的问题，是一类典型的多维排样问题。
　　1.2.2 按零件形状分类
　　排样问题按排样零件的形状特点，可以分成两类：规则形状排样问题与不规则形状排样问题。其中，一维规则形状排样的零件的截口形状为直口，一维不规则形状排样的零件的截口形状为非直口异形；二维规则形状排样的零件形状为矩形，又称矩形排样或矩形件排样，二维不规则形状排样的零件形状为异形(或任意多边形)，且板材形状也可为异形，又称异形排样或异形件排样；三维规则形状排样的零件形状为直方体，三维不规则形状排样的零件形状为三维异形体，且三维装填空间也可为异形非直方体。本书讨论二维排样中的矩形排样问题及异形排样问题。
　　1.矩形排样问题
　　矩形排样问题可以描述为：设一组数量为n的待排样矩形零件为R1， R2， ， Rn，零件编号遵循有序自然序列，且零件之间有强互异性。每个矩形零件的宽高尺寸都确定，设第i(i=1，2， ， n)个零件的宽为wi，高为hi，则第i个零件Ri可以表示为(wi， hi)[ZYB3][d4]。将R1， R2， ， Rn按照某一序列排放到一定规格的矩形板材上，目标是使矩形板材的利用率*大，且在排样过程中需要满足以下约束条件：
　　(1)矩形零件需完全放入板材边界内；
　　(2)排放入板材边界内的矩形零件不相互重叠；
　　(3)矩形零件可以翻转90°或者不能翻转90°；
　　(4)板材内部矩形零件的边与板材边界平行。
　　矩形排样根据板材规格情况又可分为定长定宽的二维矩形装箱排样问题，以及定宽不定长的二维矩形带排样问题。在矩形不能排满板材的情况下，这两类排样问题是等效的。图1.5为一组20个矩形件的矩形排样示例，图中的每个矩形大小都不相同，且每个矩形在排样过程中不能翻转90°。
　　图1.5 矩形排样示例
　　矩形排样问题按工艺约束可进一步划分为一刀切(guillotine cutting)矩形排样问题和自由切(free cutting)矩形排样问题。一刀切也称为通裁通切或通裁通剪，是指由板材的一端沿直线方向(通常是沿水平或垂直方向)贯通切割或裁剪至另一端。自由切则无此限制，刀具可以沿着矩形边界自由切割。一刀切是板材切割中的一种常见工艺，广泛存在于板式家具开料、玻璃切割、金属薄板裁剪等加工中。图1.6是一刀切和自由切两种矩形排样情况的对比示例。
　　图1.6 一刀切和自由切两种矩形排样对比示例
　　2.异形排样问题
　　异形排样问题可以描述成将一组任意二维平面图形(简称异形件或零件) P1，P2， ， Pn以合理的次序和方位角排放在矩形或异形板材S上的适当位置，使板材利用率*高，同时满足如下约束条件：
　　(1)异形件Pi、Pj互不重叠(i≠j)；
　　(2)Pi必须完全包含于板材S内；
　　(3)异形件不能旋转或可在一定角度范围内旋转。
　　图1.7 为一组20个异形件在矩形板材内的排样示例，其中每个异形件可以任意旋转。图1.8为板材为异形时的排样示例。
　　图1.7 板材为矩形时的异形排样示例
　　图1.8 板材为异形时的排样示例
　　异形排样问题的计算复杂度与求解难度远远高于矩形排样问题。相比矩形排样，异形排样时每个零件的可选位置和方位角可在一定范围内连续变化，其搜索空间远大于矩形排样。
　　排样问题是一个典型的组合优化问题，广泛存在于生产实践中，因此排样下

目录
前言
第1章 绪论 1
1.1 引言 1
1.2 排样问题分类 2
1.2.1 按排样维度分类 2
1.2.2 按零件形状分类 4
1.3 矩形排样国内外研究概况 7
1.3.1 精确算法 7
1.3.2 启发式算法 8
1.3.3 元启发式算法 10
1.4 异形排样国内外研究概况 13
1.4.1 规则形状包络法 13
1.4.2 真实形状法 14
1.5 本书主要内容 18
参考文献 19
第2章 矩形排样问题的混合遗传算法 25
2.1 矩形排样问题的数学模型与求解框架 25
2.1.1 问题描述与数学模型 25
2.1.2 矩形排样问题的求解框架 32
2.2 矩形排样问题的HGASA算法 33
2.2.1 矩形件定位策略 33
2.2.2 矩形件排序的HGASA算法 35
2.2.3 HGASA算法求解矩形件套料 37
2.2.4 算例验证与分析 41
2.3 带工艺约束的矩形排样问题的混合遗传算法 45
2.3.1 改进的剩余矩形填充算法 45
2.3.2 基于遗传算法的混合算法 51
2.3.3 算例验证与分析 55
2.4 本章小结 57
参考文献 58
第3章 矩形排样问题的和声搜索算法 60
3.1 和声搜索算法简介 60
3.1.1 算法原理与算法参数 60
3.1.2 算法流程 61
3.2 基于和声搜索的一般矩形排样混合求解算法 64
3.2.1 基于剩余矩形匹配度的矩形件定位策略 64
3.2.2 基于和声搜索的矩形件定序优化方法 65
3.2.3 算例验证与分析 71
3.3 带工艺约束的批量矩形排样问题的和声搜索算法 78
3.3.1 矩形件组合填充放置策略 79
3.3.2 基于种类编码的批量矩形排样算法 81
3.3.3 算例验证与分析 83
3.4 本章小结 87
参考文献 87
第4章 矩形排样问题的灰狼优化算法 89
4.1 灰狼优化算法简介 89
4.1.1 狼群捕猎模型 89
4.1.2 灰狼优化算法原理 90
4.2 基于灰狼优化算法的矩形带排样优化算法 92
4.2.1 基于复合评价因子的*低水平线定位算法 93
4.2.2 十进制灰狼定序算法 96
4.2.3 算例验证与分析 100
4.3 基于改进灰狼优化算法的矩形排样优化算法 106
4.3.1 改进的*低水平线定位算法 106
4.3.2 改进的十进制灰狼定序算法 110
4.3.3 算例验证与分析 113
4.4 本章小结 125
参考文献 125
第5章 矩形排样问题的布谷鸟搜索算法 127
5.1 布谷鸟搜索算法简介 127
5.1.1 布谷鸟搜索算法原理 127
5.1.2 基本布谷鸟搜索算法 129
5.1.3 布谷鸟搜索算法的应用 131
5.2 基于值评价的*低水平线定位算法 132
5.2.1 *低水平线定位算法基本原理 132
5.2.2 基于值评价的*低水平线定位算法设计 134
5.3 矩形装箱排样问题的离散布谷鸟搜索算法 136
5.3.1 离散布谷鸟搜索算法基本规则 136
5.3.2 基于学习和邻域搜索算子的莱维飞行机制 138
5.3.3 基于扰动因子的巢寄生更新机制 141
5.3.4 离散布谷鸟搜索算法流程 142
5.4 算例验证与分析 143
5.4.1 实验数据说明 143
5.4.2 计算结果及分析 145
5.5 本章小结 150
参考文献 150
第6章 矩形排样问题的布谷鸟迁移学习算法 152
6.1 强化学习与迁移学习技术简介 152
6.1.1 Q-学习算法原理 152
6.1.2 迁移学习算法原理 153
6.1.3 布谷鸟迁移学习算法求解矩形带排样问题 154
6.2 布谷鸟迁移学习算法的基本原理 156
6.2.1 布谷鸟学习模式 157
6.2.2 布谷鸟迁移学习算法知识迁移方式 163
6.2.3 布谷鸟迁移学习算法总体流程及性能分析 164
6.3 布谷鸟迁移学习算法求解矩形带排样问题 165
6.4 算例验证与分析 168
6.4.1 离散布谷鸟搜索算法求解矩形带排样问题 169
6.4.2 布谷鸟迁移学习算法求解矩形带排样问题 171
6.5 本章小结 179
参考文献 180
第7章 异形件智能排样算法 181
7.1 异形排样问题概述 181
7.1.1 问题描述 181
7.1.2 求解方法 182
7.2 异形件几何表达与几何计算 183
7.2.1 异形件的几何表达方法 183
7.2.2 异形件基本几何变换与计算 185
7.2.3 图形判交计算 187
7.2.4 临界多边形 190
7.3 遗传算法与禁忌搜索混合的求解算法 192
7.3.1 基于左下角方法的零件定位策略 192
7.3.2 HGATS算法 194
7.3.3 HGATS算法求解异形排样 195
7.3.4 算例验证与分析 198
7.4 集束搜索与禁忌搜索混合的求解算法 201
7.4.1 改进的临界多边形生成器 201
7.4.2 零件摆放定位方法 204
7.4.3 BS/TS混合搜索算法 205
7.4.4 算例验证与分析 209
7.5 超边界约束排样问题的求解方法 212
7.5.1 超边界约束排样问题描述及求解策略 212
7.5.2 超边界约束下的零件定位算法 214
7.5.3 基于粒子群优化的多约束排样算法 223
7.5.4 算例验证与分析 229
7.6 本章小结 230
参考文献 230
第8章 智能排样软件开发与应用 233
8.1 排样软件开发与应用概况 233
8.2 SmartNest钢板切割下料软件开发与应用 234
8.2.1 软件系统功能 234
8.2.2 软件系统架构 236
8.2.3 智能套料与切割优化子系统 237
8.2.4 应用案例 239
8.3 SmartNest板式家具开料软件开发与应用 247
8.3.1 板式家具开料工艺与设备 247
8.3.2 SmartNest板式家具开料软件开发 247
8.3.3 应用案例 251
8.4 SmartNest激光切割套料编程软件开发与应用 256
8.4.1 激光切割原理与设备 256
8.4.2 SmartNest激光切割套料编程软件开发 257
8.4.3 应用案例 261
8.5 本章小结 265
附录1 MHS算法排样结果(共14张) 266
附录2 CMHS算法排样结果(共14张) 268