排样问题文献综述/教程

1 minute read

Published: March 17, 2020

An comprehensive introduction to solving nesting problem

1. 概述

排样问题主要研究的是如何将形状放置进入固定宽度的容器中，在保证没有重叠的情况下，使得容器的长度最小，其实也就是利用率最大化的问题。在服装业、皮革业等诸多行业中，材料成本是这些行业的主要成本，如果能够节约材料费用，便能够节约非常多的成本，这也是排样问题的重要性。

排样问题的最广泛应用的启发式算法就是是左底部排样算法，将形状逐一加入，放置到能够放到的最左底的位置，该方案可以获得初始解。基于此算法，也就有了两个主流算法，第一，基于序列检索，即修改形状加入的序列以获得更优解，第二，基于布局检索，即在获得初始解之后，直接对形状的位置进行修改，从而获得更优的解。同时，最新的研究中，也有通过直接几何法将其转化为整数规划问题、对边界非直线情况的解决、允许自由旋转的解决方案等。

在该篇文章中，我们将在下一节介绍基础的几何原理，在第3节介绍传统的基于序列的算法，第4第5节介绍如何直接对布局（layout）直接进行优化，第6节介绍如何应用整数规划解决该问题，第7节介绍用弧边表示形状的方式以及解决方案，第8节为最新研究方向，不限制旋转角度的排样，第10节介绍机器学习与排样问题的先有交集。

除了第7节外，默认的通过顶点表示形状，在Bennell/Elkeran的论文中，第4/5节全部被归类到了基于布局检索，我们考虑到二者的具体操作有较大区别，为了方便说明，分为两节解释。

2. 几何算法

…..

2.1 直接几何法

2.1.1 D-Function

2.2 重叠多边形（No-Fit Polygon）

2.2.1 Minkowski Sum

2.2.2 旋转方法

2.2.3 Phi-Function

3. 基于序列检索

3.1 左底部排样

3.1.1 基础说明

3.1.2 Exact Fit

3.2 优化算法

3.2.1 遗传算法

参考论文：

3.2.2 模拟退火算法

参考论文：

3.3 TOPOS

3.3.1 普通方法

3.3.2 Beam Search

4. 局部优化算法

局部优化算法在此处…..

4.1 压缩（Compaction）

4.2 拆分（Separation）

5. 基于布局检索

现阶段能够达到在较多数据集中获得最优解的算法——基于布谷鸟检索（Cuckoo Search）的排样算法——便属于该类，也是近些年对限制旋转角度的数据集的优化算法中，研究最多的算法类别。

该方法的基本操作是，压缩边界后，将有重叠的形状按照重叠面积或其他原则，逐一移到IFR中重叠最小/没有重叠的地方，直至可行，从而实现优化。然而IFR的可行域无法进行全部枚举，所以论文的核心也就在处理，如何通过切割检索范围、利用合适的检索方法，找到最合适的新位置。

5.1 快速局部检索 2007年

快速局部检索的由Egeblad在2007年第一次提出，应用了局部检索的算法。

该篇文章的最大贡献是，将寻找一个m条边的形状在由共有n条边的形状组合的区域中，寻找最小重叠面积的时间压缩到了$O(mnlog(mn))$，将平移导致的形状间的重叠区域的变化，转化为了平移导致的边与边的位置关系的变化；同时采用引导式局部检索（Guided Local Search），用参数调整后的的重叠面积作为选择参考，避免因为某个形状无法找到更优位置，导致陷入局部最优。

其核心思路是：压缩边界后，选择重叠最大（参数调整后）的形状，进行水平或垂直移动寻找重叠最小/没有重叠的位置（检索算法），或者旋转，重复该步骤，消除重叠后再次压缩边界。

5.1.1 两个形状间的重叠

在一个图形的水平检索中，我们定义边之间的重叠区域如下图所示，$e$为移动形状上的边，$f$为固定形状上的边，$t$为移动的距离，$e$与$f$之间的面积定为两条边的相交面积Area。我们可以看到，再$e$与$f$初次相交后，相交面积首先是三角形，后续变为平行四边形+三角形，面积Area是移动距离$t$的分段的二次函数。

其次，在水平移动中，我们定义左侧为Positive即正（+）边，右侧为Negative即负（-）边，如图所示，而阴影面积代表两个图形的交叉面积，是所有正/红边与负/绿边的交叉面积，减去正/红边与正/红边、负/绿边与负/绿边的交叉面积。 $Overlap=Area(A^+,B^-)+Area(A^-,B^+)-Area(A^-,B^-)-Area(A^+,B^+)$

其实简化一下，我们只需要看到围成阴影面积的四条边，A的绿边与B的红边的交叉面积，减去A的红边与B的红边之间的交叉面积（虚线与红边围城的区域），就是交叉面积。

5.1.2 断点检索

可以向上看到两条边的交叉面积和移动距离$t$之间的关系其实都是广义上的二次函数，在$e$和$f$两条边初次相交、不再相交的时候会发生变化，如上图Fig.8，而这就是所谓的断点。每次到达断点后，对所有处于断点时的面积通过上述的边与边之间的交叉面积函数进行求解，选择最值即可。

5.1.3 引导局部检索（Guided Local Search）

由于可能重叠区域$Area$最大的形状没有更优的临近位置，但是有其他未知的形状有临近最优，但是每次选择仍未$Area$最大的形状，这就陷入了局部最优，此时需要采用引导局部检索（Guided Local Search）来进行调整。

在此我们引入一个新的参数$\mu$取代重叠面积作为新的参考值，$\phi_{ij}$则是两个形状的调整参数，默认为0，初始情况下，$\mu_{ij}$就是两个形状之间的重叠区域。 $\mu_{ij}(p)=\frac{overlap_{ij}(p)}{1+\phi_{ij}}$

具体操作：在每次无法进行更优化时，找到$max(\Phi)$，$\phi_{ij}\Leftarrow\phi_{ij}+1$，此时，该陷入局部最优的的$\mu_{ij}$ 值将变小。

5.1.4 收缩算法（Shrink）

具体的收缩边界算法可以参考论文，或者参考后续的论文，基于Overlap的研究基本沿用了该收缩边界算法。

参考文献：Egeblad J, Nielsen B K, Odgaard A. Fast neighborhood search for two-and three-dimensional nesting problems[J]. European Journal of Operational Research, 2007, 183(3): 1249-1266.

5.2 迭代局部检索

5.3 延长局部检索

5.4 引导局部检索

5.5 基于布谷鸟检索的排样 2014年

布谷鸟检索算法是2009年提出的一种自然启发的随机优化算法（Nature Inspired Stochastic Optimization），该方案通过局部和全局随机游走，可以对解空间进行较为完整的检索，从而达到最优解，优化了先前检索的局部性问题，这是当前的最优算法。

主要思路：通过BLF获得初始解，收缩边界，寻找重叠面积最大的形状，通过布谷鸟检索选择重叠区域更小/没有的位置，逐步消除重叠，再重复收缩边界步骤；同时，采用引导检索算法，避免陷入局部最优

核心变化：采用全局随机游走解决二维区域检索问题

5.5.1 基本操作

按照$L= (1􏱆-r_{dec})L_{best}$ 收缩（$Shrink$）边界，$r_{dec}$是固定值如2%，调用$MinimizeOverlap$函数来去除重叠，如果最终的解可行，那么继续收缩，如果解不可行，调用 $L= (1+r_{inr})L_{best}$ 扩大边界后重新检索，$r_{inc}$同样为固定值如1%。

5.2.2 收缩后优化

收缩后，部分形状会突出容器（Container），需要将其平移到IFR内部，只需要计算该形状P与其他所有形状的NFP，将其放置在NFP的顶点、不同NFP边的交点、NFP与IFR的交点上，选择重叠区域最小的位置（重叠区域采用的是Penetration depth计算）。

随机选择一个有重叠的形状，通过检索策略寻找是否有更优的位置，直至没有重叠。

5.5.3 检索策略

选择某一个形状后，需要在二维空间内找一个合适的位置，使得重叠区域降低、去除重叠。然而 $overlap(x,y)$ 重叠面积与x，y的函数属于非凸函数，有多个局部最优解，如下图等高线。

Cuckoo Search就相当于在全局范围内生成随机的点，并通过游走策略寻找最优位置，很好的避免了先前算法的局部检索导致的局限性。

DAC9E3AC-72F3-4915-B81B-FC68726165F7_1_102_o

检索的具体操作为：

（1）生成n个nest/cuckoo/solution，三者是完全等同的，比如 $nest_i = cuckoo_i = solution_i = (x_i,y_i)$

（2）随机选择一个Cuckoo，全局游走到某一个位置，再随机选择一个Nest，比较与Cuckoo的优劣，如果Cuckoo游走后的结果更优，那么该下标的Nest/Cuckoo/Solution全部更换为Cuckoo游走后的结果，以避免局部最优

（3）一轮结束后，按照 $p_a(0,1)$ 的概率将部分较差的解丢弃，通过局部游走获得新的解填补空缺

（4）记录该轮计算出的最好位置

5.5.4 游走策略

局部游走：

全局游走：

步长计算：

大致原理即，随机选择一个方向，进行局部游走或者随机游走，以获得新的位置，具体的操作可以参考原文

5.5.5 引导局部检索

采用了Umetani et al. (2009)的引导算法，即在陷入局部最优的情况后，通过 $\mu_{ij}$ 调整Fitness，也就是进行优化后仍然无法获得可行解后，有重叠的形状对的 $\mu_{ij}$ 会增加，这样可以强制形状移动到新的位置，因为新位置的$\mu_{ik}$可能会更小，这就能避免陷入局部最优

备注：仅说明检索方式，Pairwish Clustering在此不做说明

原文文献：Elkeran A. A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering[J]. European Journal of Operational Research, 2013, 231(3): 757-769.

说明：该文章虽然是European Journal of Operational Research，但是涉嫌抄袭。Cuckoo可以参考Yang X S. Nature-inspired optimization algorithms[M]. Elsevier, 2014；惩罚算法建议参考原文，解释更加完整。

🔴 5.6 研究趋势

检索范围太广/形状过多的情况，检索的难度会非常大，比如Fast Nneighborhood Search算法需要把整个横纵向检索一遍。
Cuckoo随机游走策略会有非常多的冗余计算，在到某个位置后，其实可以直接通过周边检索几何计算，
启发式算法的适应性不强，面对不同的数据集，需要调整设计不同的参数

6. 整数规划/直接规划

采用整数规划方法求解排样也是今年来的一个研究热点，主要采用将目标区域横竖划分为光栅（Raster），将所有的多边形顶点放置在光栅上，从而实现将排样问题转化为整数规划问题；也有通过几何关系进行直接规划获得最优解的研究，但是也缩减了检索区域。

Yang Shan